Trees: Types, Traversals, BSTs, AVL Trees & Applications

TAKEAWAYS:

• Trees represent hierarchical relationships (parent-child) and are used in databases, compilers, and AI.
• Binary trees have at most two children per node; BSTs enforce left ≤ root ≤ right for efficient searching.
• AVL trees self-balance to maintain $O(\log n)$ operations via rotations after insertions/deletions.
• Traversals (pre-order, in-order, post-order, level-order) visit nodes in different sequences for distinct tasks.
• Heap (priority queue) trees support efficient min/max extraction via complete binary tree properties.
• Real-world uses include Daraz’s product category trees, WhatsApp’s message thread hierarchy, and Nepal’s NTC’s network routing tables.

1. Introduction to Trees

A tree is a non-linear, hierarchical data structure with:

• Nodes: Data elements (e.g., value, left/right child pointers).
• Edges: Links between nodes (parent-child relationships).
• Root: The topmost node (no parent).
• Leaf: A node with no children.
• Subtree: A tree derived from a node (its children + descendants).

Key Properties:

• No cycles (acyclic).
• $n$ nodes have $n-1$ edges.
• Degree: Number of children of a node.
• Height: Longest path from root to leaf.

Example: File system directories (folders as nodes, files as leaves).

2. Types of Trees

A. Binary Trees

• Each node has at most 2 children (left/right).
• Types:
  1. Full Binary Tree: Every node has 0 or 2 children.
  2. Complete Binary Tree: All levels filled except possibly the last, which is left-filled.
  3. Perfect Binary Tree: All levels completely filled (height = ${\log }_{2}n$).

Example: WhatsApp’s message tree (threads as binary branches for replies).

B. Binary Search Trees (BST)

• Property: For any node:
  • Left subtree ≤ node < right subtree.
• Operations:
  • Search: $O(h)$ (height).
  • Insertion/Deletion: $O(h)$.
  • Traversals: In-order yields sorted order.

graph TD
    A["10"] --> B["5"]
    A --> C["15"]
    B --> D["2"]
    B --> E["7"]
    C --> F["12"]
    C --> G["20"]

Worked Example: Insert 8 into the BST above. Steps:

1. Start at root (10): 8 < 10 → go left.
2. At 5: 8 > 5 → go right.
3. Insert 8 as right child of 5. State after insertion:

graph TD
    A["10"] --> B["5"]
    A --> C["15"]
    B --> D["2"]
    B --> E["8"]
    C --> F["12"]
    C --> G["20"]

Code (C):

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Node* insert(Node* root, int data) {
    if (!root) return newNode(data);
    if (data < root->data) root->left = insert(root->left, data);
    else root->right = insert(root->right, data);
    return root;
}

Trace:

3. Tree Traversals

Traversals visit nodes in specific orders. Four types:

Example: In-order traversal of the BST above yields [2, 5, 7, 8, 10, 12, 15, 20].

Code (Level-order):

void levelOrder(Node* root) {
    Queue q;
    q.enqueue(root);
    while (!q.isEmpty()) {
        Node* temp = q.dequeue();
        printf("%d ", temp->data);
        if (temp->left) q.enqueue(temp->left);
        if (temp->right) q.enqueue(temp->right);
    }
}

Trace:

4. AVL Trees (Self-Balancing BSTs)

Problem: BSTs degrade to $O(n)$ if unbalanced (e.g., sorted input). Solution: AVL trees enforce balance factor (BF):

• $BF=\text{height(left)}-\text{height(right)}$.
• Constraint: $|BF|\le 1$ for all nodes.

Rotations (to rebalance):

1. Left Rotation: Right-heavy subtree.
2. Right Rotation: Left-heavy subtree.
3. Left-Right/Right-Left: Double rotations for zig-zag imbalances.

Example: Insert 1, 2, 3 into an AVL tree. Steps:

1. Insert 1 → root.
2. Insert 2 → right child of 1 (BF = 0).
3. Insert 3 → right child of 2 (BF = 1 for 2, 0 for 1). Imbalance detected at 1 (BF = -2) → Left Rotation at 1. Final Tree:

Code (AVL Insertion):

int height(Node* node) { ... }
int getBF(Node* node) { ... }
Node* rightRotate(Node* y) { ... }
Node* leftRotate(Node* x) { ... }

Node* insert(Node* root, int data) {
    if (!root) return newNode(data);
    if (data < root->data) root->left = insert(root->left, data);
    else root->right = insert(root->right, data);

    root->height = 1 + max(height(root->left), height(root->right));
    int BF = getBF(root);

    // Left Left Case
    if (BF > 1 && data < root->left->data)
        return rightRotate(root);
    // Other cases...
    return root;
}

5. Applications of Trees

Real-World Example 1: Daraz’s Product Categories

• Structure: Multi-level tree (Electronics → Mobiles → Samsung → Galaxy S23).
• Why Trees?:
  • Fast lookup (BST) for product searches.
  • Hierarchical navigation (parent-child relationships).
• Operation: When you click "Mobiles," Daraz traverses the tree to fetch subcategories.

Real-World Example 2: WhatsApp Message Threads

• Structure: Binary tree for replies (root = original message, children = replies).
• Why Trees?:
  • Pre-order traversal flattens threads for reading.
  • AVL-like balancing ensures quick reply insertion.

Real-World Example 3: NTC’s Network Routing

• Structure: Trie or tree for IP address prefixes (e.g., 192.168.1.*).
• Why Trees?:
  • Longest prefix match (e.g., 192.168.1.100 vs 192.168.*).
  • Efficient routing tables (AVL for dynamic updates).

6. Comparison: Trees vs. Other Structures

When to Use Trees?

• Need hierarchical data (e.g., org charts, file systems).
• Frequent search/insert/delete with ordering (BST/AVL).
• Priority-based operations (heaps).

7. Exam Tip

What Examiners Look For:

1. Definitions: Clearly define tree, BST, AVL tree, and traversals.
2. Visuals: Draw trees after each operation (insertion/deletion/rotation).
   • Example: Show the BST before and after inserting 8 (as above).
3. Time Complexity: State $O(h)$ for BST operations; $O(\log n)$ for AVL.
4. Code + Trace: Write pseudocode for traversals/rotations and trace with a table.
5. Real-World Links: Relate to Nepali apps (eSewa, Daraz, NTC) or global tech (Google, WhatsApp).
6. Common Pitfalls:
   • Forgetting to update heights in AVL trees.
   • Incorrect rotation cases (e.g., confusing left-right with right-left).
   • Off-by-one errors in traversal order.

Sample Exam Questions:

• "Insert 5, 3, 7, 2 into a BST and show the tree after each step."
• "Explain how AVL trees maintain balance with an example."
• "Compare the time complexity of searching in a BST vs. a hash table."
• "How would you implement a spell checker using a trie?"

Marks Distribution (Typical):

• 3 marks: Definitions/diagrams.
• 4 marks: Step-by-step operations (insertion/traversal).
• 3 marks: Code + trace.
• 2 marks: Real-world application.

Tree representation of folders/files (Image: Peter Flass, CC BY-SA 4.0, via Wikimedia Commons)