Binary Trees, BSTs, AVL Trees, and Applications

TAKEAWAYS:

• A binary tree is a hierarchical structure where each node has at most two children, enabling efficient traversal (in-order, pre-order, post-order) and recursive operations.
• A BST maintains the property that left ≤ parent < right, allowing O(h) search/insert/delete (where h is tree height), but degrades to O(n) if unbalanced.
• AVL trees guarantee O(log n) operations by enforcing balance (height difference ≤ 1) via rotations (LL, RR, LR, RL), making them ideal for dynamic datasets.
• Traversals (in-order, pre-order, post-order) produce different orderings: in-order yields sorted output for BSTs, while pre-order/post-order are used in serialization.
• Applications include database indexing (BSTs for fast lookups), file systems (directory trees), and network routing (trie-based trees for IP lookup).
• Exam focus: Derive traversal outputs, trace BST insertions/deletions, identify imbalance cases, and compare BST vs. AVL performance.

1. Binary Trees: Structure and Traversals

A binary tree is a finite set of nodes where each node has at most two children (left and right). It is not necessarily a binary search tree (BST) unless it satisfies the BST property.

Key Properties

• Root: The topmost node.
• Leaf: A node with no children.
• Height: The longest path from root to leaf (edges counted).
• Degree: Number of children (0, 1, or 2 for binary trees).

Traversals (Visiting Nodes in Order)

Traversals define the sequence in which nodes are visited. There are three primary traversals:

1. Pre-order (Root → Left → Right)
   • Visit root, then left subtree, then right subtree.
   • Use case: Copying a tree (e.g., serialization).
2. In-order (Left → Root → Right)
   • Visit left subtree, then root, then right subtree.
   • Use case: BSTs yield sorted output.
3. Post-order (Left → Right → Root)
   • Visit left subtree, then right subtree, then root.
   • Use case: Deleting a tree (children before parent).

Example: Pre-order Traversal of the Above Tree Output: A, B, D, E, C, F, G

Worked Example: In-order Traversal of a BST Consider the BST:

      50
     /  \
   30    70
  / \   / \
 20 40 60 80

In-order traversal:

1. Traverse left of 50 → 30.
2. Traverse left of 30 → 20 (leaf, print 20).
3. Back to 30, print 30.
4. Traverse right of 30 → 40 (leaf, print 40).
5. Back to 50, print 50.
6. Traverse right of 50 → 70.
7. Traverse left of 70 → 60 (leaf, print 60).
8. Back to 70, print 70.
9. Traverse right of 70 → 80 (leaf, print 80). Output: 20, 30, 40, 50, 60, 70, 80 (sorted order).

2. Binary Search Trees (BSTs): Operations and Properties

A BST is a binary tree where for every node:

• All nodes in the left subtree ≤ node’s value.
• All nodes in the right subtree > node’s value.

Operations

Insertion

1. Start at the root.
2. If the tree is empty, insert as root.
3. Otherwise, compare the new value with the current node:
   • If less, go to the left child.
   • If greater, go to the right child.
4. Repeat until an empty spot is found.

Example: Insert 50, 30, 70, 20, 40 into an empty BST

Steps:

1. Insert 50 → root.
2. Insert 30 < 50 → left of 50.
3. Insert 70 > 50 → right of 50.
4. Insert 20 < 30 → left of 30.
5. Insert 40 > 30 → right of 30.

Search

1. Start at the root.
2. Compare the search key with the current node:
   • If equal, found.
   • If less, go left.
   • If greater, go right.
3. If reach null, the key is absent.

Example: Search for 40 in the above BST Path: 50 → 30 → 40 (found).

Deletion

Three cases:

1. Node is a leaf: Simply remove it.
2. Node has one child: Replace it with its child.
3. Node has two children: Replace it with its in-order successor (smallest in right subtree) or in-order predecessor (largest in left subtree), then delete the successor/predecessor.

Example: Delete 30 from the BST above

• 30 has two children (20 and 40).
• In-order successor of 30 is 40.
• Replace 30 with 40, then delete 40 (which is a leaf). Resulting BST:

      50
     /  \
   40    70
  /      /
20     60
      /
    80

3. Time Complexity of BST Operations

Worst Case: Occurs when the BST degenerates into a linked list (e.g., inserting sorted data). Example: Inserting [10, 20, 30, 40, 50] in order:

10 → 20 → 30 → 40 → 50

Search time becomes O(n).

4. Self-Balancing BSTs: AVL Trees

AVL trees maintain balance by ensuring the height difference (balance factor) between left and right subtrees is at most 1 for every node. This guarantees O(log n) operations.

Balance Factor (BF)

• BF = height(left subtree) - height(right subtree)
• Valid BF values: -1, 0, 1.

Rotations (Restoring Balance)

Four cases of imbalance, each requiring a specific rotation:

1. Left-Left (LL) Case
   • Right rotation on the unbalanced node.

graph TD
    A["Unbalanced Node (BF = +2)"] --> B["Left Child"]
    B --> C["Left-Left Grandchild"]
    A -->|"Right rotation"| D["Balanced Node"]
    D --> E["New Left Child"]
    D --> C

LL rotation: Unbalanced node (BF=+2) → Right rotation Rotation:

2. Right-Right (RR) Case
   • Left rotation on the unbalanced node.

graph TD
    A["Unbalanced Node (BF = -2)"] --> B["Right Child"]
    B --> C["Right-Right Grandchild"]
    A -->|"Left rotation"| D["Balanced Node"]
    D --> B
    D --> C

RR rotation: Unbalanced node (BF=-2) → Left rotation Rotation:

3. Left-Right (LR) Case
   • Left rotation on the left child, then right rotation on the unbalanced node.

graph TD
    A["Unbalanced Node (BF = +2)"] --> B["Left Child"]
    B --> C["Right Grandchild"]
    A -->|"1. Left rotate B"| D["New Left Child"]
    D --> C
    A -->|"2. Right rotate A"| E["Balanced Node"]
    E --> D
    E --> C

LR rotation: Left child → Right rotation → Unbalanced node → Left rotation Rotations:

1. Left rotate on B → C becomes new left child of A.

2. Right rotate on A.

3. Right-Left (RL) Case

   • Right rotation on the right child, then left rotation on the unbalanced node.

graph TD
    A["Unbalanced Node (BF = -2)"] --> B["Right Child"]
    B --> C["Left Grandchild"]
    A -->|"1. Right rotate B"| D["New Right Child"]
    D --> C
    A -->|"2. Left rotate A"| E["Balanced Node"]
    E --> D
    E --> C

RL rotation: Right child → Left rotation → Unbalanced node → Right rotation Rotations:

1. Right rotate on B → C becomes new right child of A.
2. Left rotate on A.

Example: AVL Insertion and Rotation

Insert [10, 20, 30, 40, 50, 25] into an AVL tree:

1. Insert 10, 20, 30 → balanced.
2. Insert 40 → LL case at 30.
   • Right rotate on 30. Tree after rotation:

      30
     /  \
   20   40
     /     /
   

10 50

3. Insert 25 → LR case at 30.
- Left rotate on 20 → 25 becomes left child of 30.
- Right rotate on 30.
**Final AVL Tree**:

  30
 /  \

20 40 \ / 25 50 / 10

---
### **5. Applications of Binary Trees and BSTs**
#### **In the Real World**
1. **eSewa (Nepal Government)**
- **BSTs for User Authentication**: When a user logs in, eSewa’s backend uses a BST to quickly verify credentials (e.g., username/password pairs stored in a BST for O(log n) lookup). The system also uses AVL trees to maintain balance in frequently accessed data (e.g., transaction logs) to ensure fast retrieval during peak hours (e.g., during festival seasons like Dashain or Tihar).

2. **Khalti (Digital Payment System)**
- **AVL Trees for Fraud Detection**: Khalti processes thousands of transactions per second. Suspicious transactions (e.g., unusually large amounts or rapid successive payments) are flagged using BSTs. The system inserts transaction IDs into an AVL tree and checks for anomalies (e.g., a node with BF > 1 might indicate a botnet attack). Rotations keep the tree balanced, ensuring O(log n) fraud checks even during Diwali sales.

3. **Daraz (E-Commerce)**
- **BSTs for Product Search**: When you search for a product (e.g., "Nike shoes"), Daraz’s backend uses a BST to index products by price or popularity. For example, if you filter products priced between ₹5,000 and ₹10,000, the BST allows Daraz to quickly retrieve all products in that range (in-order traversal of a subtree). During the Great Indian Sale, BSTs ensure fast filtering even with millions of products.

4. **Ncell (Telecom)**
- **Trie Trees for Phonebook Lookup**: Ncell’s phonebook uses a **trie** (a specialized tree) to store and search contact names. For example, searching for "Sagar" involves traversing the trie from root to the node labeled 'S' → 'A' → 'G' → 'A' → 'R'. This reduces lookup time compared to linear search, especially useful for Ncell’s 20+ million subscribers.

5. **NEPSE (Nepal Stock Exchange)**
- **BSTs for Stock Price Tracking**: NEPSE uses BSTs to maintain a dynamic list of stock prices. When a stock’s price updates (e.g., NMB Bank’s share price changes from Rs. 200 to Rs. 210), the BST is updated in O(log n) time. Traders querying the "top 10 stocks by price" trigger an in-order traversal to fetch sorted results.

6. **Google Maps (Global)**
- **Quad Trees for Route Optimization**: Google Maps uses **quad trees** (a variant of binary trees) to divide geographical regions into four quadrants for efficient route planning. For example, when you search for "restaurants near Thamel," the quad tree quickly narrows down the search to Kathmandu’s central quadrant, reducing the number of locations to check.

---
### **6. Comparison: BST vs. AVL Tree**
| Feature          | BST                          | AVL Tree                     |
|------------------|------------------------------|-------------------------------|
| **Balance**      | Unbalanced (can degrade to O(n)) | Self-balancing (O(log n) guaranteed) |
| **Insertion**    | O(h) (h = height)           | O(log n) + rotations          |
| **Deletion**     | O(h)                         | O(log n) + rotations          |
| **Search**       | O(h)                         | O(log n)                      |
| **Use Case**     | Static data, infrequent updates | Dynamic data, frequent updates |
| **Example**      | File system directories      | Databases, real-time systems  |

```figure
{"type":"bar","labels":["BST (Avg. Case)","BST (Worst Case)","AVL Tree"],"values":[1.5,5,1.5],"ylabel":"Time Complexity (log n)","caption":"Time complexity comparison for search operations"}

7. Exam Tip

1. Traversals:

   • Memorize the order of pre-order, in-order, and post-order traversals. For BSTs, in-order always gives sorted output.
   • Practice: Given a BST, derive the traversal output without drawing the tree (e.g., "What is the post-order traversal of a BST with root 10, left child 5, and right child 15?").

2. BST Operations:

   • Insertion/Deletion: Draw the tree step-by-step. For deletion, identify whether the node is a leaf, has one child, or two children.
   • Common Mistake: Forgetting to update the BST property after deletion (e.g., replacing a node with its successor/predecessor but not adjusting the tree).

3. AVL Trees:

   • Rotations: Know when to apply LL, RR, LR, and RL rotations. Practice identifying the imbalance case by calculating the balance factor.
   • Exam Question: "Insert 10, 20, 30, 15 into an AVL tree and show the tree after each insertion, including rotations."

4. Time Complexity:

   • Always analyze BST operations in terms of height (h). For AVL trees, h = O(log n).
   • Worst Case: A skewed BST (e.g., inserting sorted data) has h = O(n).

5. Applications:

   • Relate BSTs to databases (indexing), file systems (directories), and routing algorithms (IP lookup).
   • For AVL trees, mention real-time systems (e.g., stock exchanges, fraud detection).

8. Worked Example: BST Insertion and Search

Question: Insert the values [5, 3, 7, 2, 4, 6, 8] into an empty BST. Then, search for the value 4 and show the path.

Solution:

1. Insertion Steps:

   • Insert 5 → root.
   • Insert 3 < 5 → left of 5.
   • Insert 7 > 5 → right of 5.
   • Insert 2 < 3 → left of 3.
   • Insert 4 > 3 → right of 3.
   • Insert 6 < 7 → left of 7.
   • Insert 8 > 7 → right of 7. Final BST:

        5
       / \
      3   7
     / \ / \
    2 4 6 8
   

2. Search for 4:

   • Start at 5 (4 < 5 → go left).
   • At 3 (4 > 3 → go right).
   • At 4 (found). Path: 5 → 3 → 4.

Code Implementation (Python):

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.val:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

def search(root, key):
    if root is None or root.val == key:
        return root
    if key < root.val:
        return search(root.left, key)
    return search(root.right, key)

# Example usage:
root = None
keys = [5, 3, 7, 2, 4, 6, 8]
for key in keys:
    root = insert(root, key)
result = search(root, 4)
print("Found:", result.val if result else "Not found")

Trace Table for Insertion of 4:

9. Worked Example: AVL Insertion with Rotation

Question: Insert [10, 20, 30, 40, 50, 25] into an AVL tree and show the tree after each insertion, including rotations.

Solution:

1. Insert 10 → root.

   10
   

2. Insert 20 > 10 → right of 10.

     10
      \
       20
   

3. Insert 30 > 20 → right of 20.

       10
        \
         20
          \
           30
   

   • Check Balance: BF of 20 = height(10) - height(30) = 1 - 1 = 0.
   • BF of 10 = height(20) - height(None) = 2 - 0 = 2 → LL Case.
   • Right rotate on 20:

       20
      /  \
      10   30
     

4. Insert 40 > 30 → right of 30.

       20
      /  \
    10   30
         \
          40
   

   • BF of 30 = 0 - 1 = -1 (balanced).
   • BF of 20 = height(10) - height(30) = 1 - 2 = -1 (balanced).
5. Insert 50 > 40 → right of 40.

       20
      /  \
    10   30
         \
          40
           \
            50
   

   • BF of 40 = 0 - 1 = -1 (balanced).
   • BF of 30 = height(40) - height(None) = 2 - 0 = 2 → LL Case at 30.
   • Right rotate on 40:

       20
      /  \
      10   40
         /  \
       30   50
     

6. Insert 25 > 20 → right of 20.

       20
      /  \
    10   40
     \   /  \
     25 30   50
   

   • BF of 20 = height(10) - height(40) = 1 - 2 = -1 (balanced).
   • BF of 40 = height(30) - height(50) = 1 - 1 = 0 (balanced).
   • Final AVL Tree:

         20
        /  \
      10   40
       \   /  \
       25 30   50
     

Code for AVL Insertion (Python):

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

def height(node):
    if not node:
        return 0
    return node.height

def update_height(node):
    node.height = 1 + max(height(node.left), height(node.right))

def balance_factor(node):
    if not node:
        return 0
    return height(node.left) - height(node.right)

def right_rotate(y):
    x = y.left
    T2 = x.right
    x.right = y
    y.left = T2
    update_height(y)
    update_height(x)
    return x

def left_rotate(x):
    y = x.right
    T2 = y.left
    y.left = x
    x.right = T2
    update_height(x)
    update_height(y)
    return y

def insert(node, key):
    if not node:
        return AVLNode(key)
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)
    update_height(node)
    bf = balance_factor(node)
    # Left Left Case
    if bf > 1 and key < node.left.key:
        return right_rotate(node)
    # Right Right Case
    if bf < -1 and key > node.right.key:
        return left_rotate(node)
    # Left Right Case
    if bf > 1 and key > node.left.key:
        node.left = left_rotate(node.left)
        return right_rotate(node)
    # Right Left Case
    if bf < -1 and key < node.right.key:
        node.right = right_rotate(node.right)
        return left_rotate(node)
    return node

# Example usage:
root = None
keys = [10, 20, 30, 40, 50, 25]
for key in keys:
    root = insert(root, key)

Trace Table for Insertion of 25:

10. Common Pitfalls and How to Avoid Them

1. Forgetting to Update Heights in AVL Trees:

   • After rotations, always recalculate the height of affected nodes.
   • Fix: Call update_height() after every rotation.

2. Incorrect Rotation Cases:

   • Mixing up LL with LR or RR with RL.
   • Fix: Draw the tree and calculate BF for each node before deciding the rotation.

3. BST Property Violations:

   • After deletion, not ensuring the BST property is maintained (e.g., replacing a node with its successor but not adjusting the tree).
   • Fix: Always verify the BST property after deletion.

4. Off-by-One Errors in Traversals:

   • Misremembering the order (e.g., pre-order as root → right → left).
   • Fix: Use mnemonics:
     • Pre-order: "Root first, then Left, Right" (like a preface).
     • In-order: "Left, Root, Right" (like reading a book from start to finish).
     • Post-order: "Left, Right, Root" (like cleaning a room: children before parent).

11. Summary Table: Binary Trees vs. BSTs vs. AVL Trees