Binary Trees, BSTs, Traversals, Operations & Real-World Uses

TAKEAWAYS:

• Understand the strict left/right child rule of binary trees and how it enables efficient traversals and searches.
• Master BST properties (left ≤ parent < right) and how they enable O(h) search/insert/delete operations.
• Visualize traversals (in-order, pre-order, post-order) as recursive tree walks and their real-world uses (e.g., expression evaluation, file system directories).
• Trace BST operations step-by-step to identify edge cases (duplicates, unbalanced trees, empty subtrees).
• Compare BSTs with other structures (e.g., hash tables) using time/space complexity tables.
• Apply BSTs to real-world scenarios like database indexing, autocomplete systems, and hierarchical data (e.g., organizational charts).

1. Binary Trees: Definition and Properties

A binary tree is a hierarchical data structure where each node has at most two children:

• Left child
• Right child

Key Properties

• Root: The topmost node (no parent).
• Leaf: A node with no children.
• Parent/Child: Relationship between connected nodes.
• Height: Longest path from root to leaf (edges counted).
• Depth: Distance from root to a node (edges counted).

Visual: Binary Tree Structure

graph TD
    A["Root (10)"] --> B["Left (5)"]
    A --> C["Right (15)"]
    B --> D["Left (3)"]
    B --> E["Right (7)"]
    C --> F["Left (12)"]
    C --> G["Right (20)"]

Caption: A sample binary tree with 7 nodes.

Why Binary Trees?

• Hierarchical data: Organizes data in parent-child relationships (e.g., file systems, organizational charts).
• Efficient traversals: In-order, pre-order, and post-order traversals enable systematic processing.
• Dynamic operations: Insertion/deletion without shifting elements (unlike arrays).

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

A BST is a binary tree with an ordering property:

• Left subtree ≤ Parent node < Right subtree.

Key Properties

Visual: BST Insertion Steps

Step 1: Insert 10 (root).

Step 2: Insert 5 (left of 10).

Step 3: Insert 15 (right of 10).

Step 4: Insert 3 (left of 5).

3. Traversals: In-order, Pre-order, Post-order

Traversals visit nodes in a specific order. Each uses a recursive approach:

1. Pre-order: Root → Left → Right.
2. In-order: Left → Root → Right (BSTs yield sorted output).
3. Post-order: Left → Right → Root.

Visual: In-order Traversal of a BST

Tree:

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

In-order Output: 3, 5, 7, 10, 12, 15, 20 (sorted).

Code Example: In-order Traversal (Python)

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

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val, end=" ")
        inorder(root.right)

# Example usage:
root = Node(10)
root.left = Node(5)
root.right = Node(15)
inorder(root)  # Output: 5 3 7 10 12 15 20

Trace Table for In-order Traversal

4. BST Operations: Insertion and Deletion

Insertion Algorithm

1. Start at the root.
2. Compare the new key with the current node:
   • If smaller, go left.
   • If larger, go right.
3. Insert at the first None position.

Visual: Insert 12 into the BST Above

Before Insertion:

After Insertion (12 < 15, so left of 15):

Deletion Algorithm

Three cases:

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

Visual: Delete 10 (Root with Two Children)

Step 1: Find in-order successor (12). Step 2: Replace 10 with 12. Final BST:

5. Applications of BSTs

In the Real World

1. Databases (e.g., MySQL, PostgreSQL)

   • Use: Indexing tables for fast search (BSTs enable O(log n) lookups).
   • Example: When you search for a customer ID in a bank’s database, the system uses a BST-based index to retrieve records quickly.

2. File Systems (e.g., Windows Explorer, Linux find command)

   • Use: Directory structures are often represented as BSTs for efficient file navigation.
   • Example: Navigating folders in your computer uses a BST-like hierarchy to list files in alphabetical order.

3. Autocomplete Systems (e.g., Google Search, WhatsApp)

   • Use: BSTs store dictionaries to predict words as you type.
   • Example: Typing "dat" in Google suggests "data" or "database" by traversing a BST of words.

4. Nepal Stock Exchange (NEPSE) Trading System

   • Use: BSTs manage buy/sell orders for stocks, ensuring trades are matched efficiently.
   • Example: When you place a buy order for a stock, the system uses a BST to find the best matching sell order in O(log n) time.

5. eSewa and Khalti Payment Systems

   • Use: Transaction logs are stored in BSTs for audit trails and fraud detection.
   • Example: When you check your transaction history, the system retrieves records in sorted order using in-order traversal.

6. Worked Example: BST for Loan Interest Calculation (Bank Scenario)

Scenario: A bank uses a BST to store loan interest rates for different tenures. Customers query rates based on tenure (e.g., 1 year, 5 years, 10 years).

BST Structure:

Operations:

1. Insertion: Add a new tenure (e.g., 3 years at 6%).
   • Compare 3 with 5 → left of 5.
   • Compare 3 with 1 → right of 1.
   • Insert 3 years (6%) as right child of 1 year. Updated BST:

2. Search: Find the rate for 5-year tenure.

   • Start at root (5 years) → match found. Rate = 8%.

3. Deletion: Remove the 1-year tenure.

   • 1 year has one child (3 years) → replace 1 year with 3 years. Final BST:

7. Comparison: BST vs. Other Data Structures

When to Use BSTs?

• Data is dynamic (frequent insertions/deletions).
• You need sorted output (e.g., leaderboards, dictionaries).
• Data is hierarchical (e.g., file systems, organizational charts).

When to Avoid BSTs?

• Data is static (use arrays or hash tables).
• You need O(1) average time (hash tables are better).
• Memory is constrained (BSTs use more pointers than arrays).

8. Exam Tip

Common Pitfalls

1. Forgetting BST Property: Always ensure left ≤ parent < right after insertions/deletions.

   • Example: Inserting 5 into a BST with root 5 violates the property (duplicates must be handled separately).

2. Incorrect Traversal Order:

   • Mistake: Writing pre-order as Left → Root → Right.
   • Correct: Root → Left → Right.

3. Deletion Edge Cases:

   • Mistake: Deleting a node with two children by simply replacing it with the right child.
   • Correct: Replace with the in-order successor/predecessor.

High-Score Strategies

1. Draw the Tree: For every insertion/deletion question, sketch the BST before and after the operation.

   • Example: If asked to delete 10 from a BST, draw the tree, identify the successor (12), and show the restructured tree.

2. Pseudocode + Trace Table:

   • Write the algorithm in clear steps (e.g., "If node has no left child, replace with right child").
   • Include a trace table showing variable changes (e.g., parent, current).

3. Real-World Links:

   • Relate BSTs to databases, file systems, or autocomplete in your answers. Examiners love practical connections!

4. Time Complexity:

   • Always state whether the BST is balanced or unbalanced when discussing time complexity.
   • Example: "For a balanced BST, search is O(log n). For an unbalanced BST, it degrades to O(n)."

Past Exam Questions Solved

Q1: How does binary search differ from linear search? Answer:

Q2: Write a function to traverse a binary tree in Preorder. Answer:

def preorder(root):
    if root:
        print(root.val, end=" ")  # Visit root
        preorder(root.left)       # Traverse left
        preorder(root.right)      # Traverse right

Trace for Tree:

Output: 1 2 4 3

Q3: Write an algorithm to perform insertion in a BST. Answer:

1. Start at the root.
2. If the tree is empty, insert the new node as root.
3. Otherwise, compare the new key with the current node:
   • If smaller, move to the left child.
   • If larger, move to the right child.
4. Repeat until an empty spot is found. Insert the new node there. Pseudocode:

INSERT(BST, key):
    current = BST.root
    while current != NULL:
        if key < current.val:
            if current.left == NULL:
                current.left = new Node(key)
                return
            current = current.left
        else:
            if current.right == NULL:
                current.right = new Node(key)
                return
            current = current.right
    BST.root = new Node(key)  # Tree was empty

Final Note: BSTs are fundamental to efficient searching and sorting. Master the traversals, insertion/deletion steps, and real-world ties (e.g., databases, autocomplete) to ace this unit!