Trees & Binary Trees: Types, Operations, Applications & BSTs

TAKEAWAYS:

• A binary tree is a hierarchical structure where each node has at most two children (left/right), while a binary search tree (BST) enforces left < parent < right for efficient searching.
• Traversals (in-order, pre-order, post-order) visit nodes in different orders, critical for applications like expression evaluation and file system navigation.
• BST operations (insertion, deletion, search) run in O(h) time, where h is tree height—optimal for dynamic datasets like Daraz order queues or Ncell call logs.
• Balanced trees (e.g., AVL) guarantee O(log n) operations by maintaining height constraints, used in databases (e.g., NEPSE stock price indexing) and compilers.
• Complete vs. full trees differ in node placement: complete trees fill levels left-to-right, while full trees require all nodes to have 0 or 2 children.
• Real-world ties: eSewa’s transaction hierarchy (parent-child relationships), YouTube’s video recommendations (tree-based similarity), and Kathmandu’s traffic route optimization (minimum spanning trees).

1. Tree Basics: Definitions and Terminology

A tree is a nonlinear data structure representing hierarchical relationships. Key terms:

• Node: A data element (e.g., value, left, right pointers).
• Root: The topmost node (no parent).
• Leaf: A node with no children.
• Parent/Child: Nodes directly connected (parent → child).
• Subtree: A tree derived from a node (e.g., left subtree of root).
• Height: Longest path from root to leaf (e.g., height = 2 for root → child → leaf).

Binary Tree Definition

A tree where each node has at most two children (left and right). Examples:

• Full Binary Tree: Every node has 0 or 2 children.
• Complete Binary Tree: All levels filled except possibly the last, which is filled left-to-right.
• Perfect Binary Tree: All levels completely filled (e.g., height h has $2^{h+1}-1$ nodes).

graph TD
    A["Root"] --> B["Left Child"]
    A --> C["Right Child"]
    B --> D["Left Leaf"]
    B --> E["Right Leaf"]
    C --> F["Left Leaf"]

2. Binary Search Tree (BST): Properties and Operations

A BST is a binary tree with the BST property:

For any node, all left descendants ≤ node < all right descendants.

Key Operations

A. Insertion

1. Start at the root.
2. Compare the new value with the current node:
   • If smaller, move to the left child (recurse).
   • If larger, move to the right child (recurse).
   • If equal, insert as a duplicate (or ignore, depending on implementation).
3. Insert the new node where the path ends.

Example: Insert [47, 50, 25, 27, 17, 61, 5, 26] into an empty BST.

Step-by-Step Trace:

B. Search

1. Start at the root.
2. Compare the search key with the current node:
   • If equal, return the node.
   • If smaller, search the left subtree.
   • If larger, search the right subtree.
3. If the path ends without finding the key, return null.

Example: Search for 26 in the BST above.

• Path: 47 → 25 → 27 → 26 (found).

C. 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 the right subtree) or predecessor (largest in the left subtree), then delete the successor/predecessor.

Example: Delete 25 from the BST above.

• 25 has two children (17 and 27).
• In-order successor of 25 is 26 (leftmost in right subtree).
• Replace 25 with 26, then delete 26 (which has no children). Resulting BST:

graph TD
    A["47"] --> B["26"]
    A --> C["61"]
    B --> D["17"]
    B --> E["50"]
    D --> F["5"]

3. Tree Traversals

Traversals visit nodes in a specific order. Three primary methods:

Visual Trace of In-order Traversal: Steps:

1. Traverse left subtree of 47 → 25.
2. Traverse left subtree of 25 → 17.
3. Traverse left subtree of 17 → 5 (leaf, print).
4. Back to 17 (print).
5. Traverse right subtree of 17 → none.
6. Back to 25 (print).
7. Traverse right subtree of 25 → 27.
8. Traverse left subtree of 27 → 26 (leaf, print).
9. Back to 26 (print).
10. Back to 27 (print).
11. Back to 47 (print).
12. Traverse right subtree of 47 → 61 (print).

4. Types of Binary Trees

5. Applications of Binary Trees

In the Real World

1. eSewa Transaction Hierarchy:

   • Idea: BSTs store transaction records (e.g., user_id, amount, timestamp).
   • How: Each transaction is a node. Searching for a user’s transactions uses BST’s O(log n) search time.
   • Example: To find all transactions for user_12345, traverse the BST starting at the root, comparing user_id values.

2. YouTube Recommendations:

   • Idea: A trie (prefix tree) stores video categories (e.g., "Travel", "Gaming").
   • How: BSTs rank videos by views/likes. When you search "Nepal trekking", the system traverses the trie to fetch relevant videos efficiently.

3. Ncell Call Logs:

   • Idea: A binary search tree organizes call records by timestamp.
   • How: Inserting a new call (timestamp, duration, contact) maintains sorted order. To find calls in January 2023, perform a range search (e.g., 2023-01-01 to 2023-01-31).

4. File Systems (NTFS/FAT):

   • Idea: B-Trees index file locations on disks.
   • How: Each node stores file paths and pointers to child nodes. Searching for C:\Users\file.txt traverses the B-tree in O(log n) time.

5. Compiler Design (Expression Parsing):

   • Idea: Binary trees represent arithmetic expressions (e.g., 3 + 4 * 2).
   • How: The tree structure mirrors the order of operations (PEMDAS). Post-order traversal evaluates the expression:

         +
        / \
       3   *
          / \
         4   2
     

     Post-order: 3 4 2 * + → 3 + (4 * 2) = 11.

6. Time Complexity Analysis

Example: Inserting n sorted elements into a BST degrades to O(n²) time (degenerates to a linked list). Solution: Use self-balancing trees (AVL, Red-Black) to guarantee O(log n) operations.

7. Balanced Trees: AVL Trees

An AVL tree maintains balance by ensuring the heights of left and right subtrees differ by at most 1 (balance factor). Rotations restore balance:

1. Left Rotation: Right-heavy subtree.
2. Right Rotation: Left-heavy subtree.
3. Combined Rotations: Left-Right or Right-Left cases.

Example: Insert 10, 20, 30 into an AVL tree.

1. Insert 10 (root).
2. Insert 20 (right child of 10).
3. Insert 30 (right child of 20).
   • Imbalance detected: Right subtree of 10 has height 2, left has height 0.
   • Fix: Left rotation at 10. Result:

8. Worked Example: BST for Daraz Order Queue

Scenario: Daraz uses a BST to manage orders by order_id (e.g., ORD123, ORD456). Customers frequently check order statuses. Operations:

1. Insertion: New order ORD789 (value = 789).
   • Path: ORD123 (root) → right (ORD456) → left (ORD789).
2. Search: Check status of ORD456.
   • Path: ORD123 → right (ORD456, found).
3. Deletion: Cancel ORD123 (root with two children).
   • Replace with in-order successor ORD456, then delete ORD456 (leaf).

BST Before/After Deletion:

Exam Tip

1. Diagrams Are Mandatory: Always draw BSTs after each insertion/deletion step. Examiners deduct marks for missing intermediate states.
2. Traversal Order: Memorize the in-order output for BSTs (sorted order). For pre/post-order, use the mnemonic "Root First/Last" (pre: root → left → right; post: left → right → root).
3. Balanced vs. Unbalanced: Questions often ask about worst-case scenarios (e.g., "Why is BST search O(n) for sorted input?"). Answer: Degenerates to a linked list.
4. Applications: Link BSTs to real-world systems (e.g., "How would NEPSE use a BST to track stock prices?"). Use examples from the "In the real world" section.
5. Pseudocode + Trace: For algorithms (e.g., insertion), write pseudocode and provide a step-by-step trace table (like the one for BST insertion above).
6. Common Pitfalls:
   • Forgetting to update pointers during deletion (e.g., not linking the successor’s right subtree).
   • Misidentifying balance factors in AVL trees (always calculate as left_height - right_height).

Practice Questions (Exam-Style)

1. Describe the merits and demerits of a BST over a linear array for storing student records (roll_no, name, marks) at TU.

   • Merits: O(log n) search/insertion; dynamic size.
   • Demerits: Overhead of pointer management; worst-case O(n) for skewed trees.

2. Show the BST after inserting [15, 25, 10, 20, 30]. Perform in-order traversal.

   • BST:

         15
        /  \
      10    25
           /  \
         20    30
     

   • In-order: 10, 15, 20, 25, 30.

3. Why might a complete binary tree be preferred over a full binary tree for a file system?

   • Complete trees minimize height for a given number of nodes, reducing disk I/O latency. Full trees require all nodes to have 0 or 2 children, which is restrictive for variable data sizes.

4. Write pseudocode for BST deletion and trace deleting node 25 from the BST in the worked example.

   def delete(node, key):
       if node is None:
           return node
       if key < node.value:
           node.left = delete(node.left, key)
       elif key > node.value:
           node.right = delete(node.right, key)
       else:
           # Node with one child or no child
           if node.left is None:
               return node.right
           elif node.right is None:
               return node.left
           # Node with two children: get inorder successor
           temp = minValueNode(node.right)
           node.value = temp.value
           node.right = delete(node.right, temp.value)
       return node
   
   def minValueNode(node):
       current = node
       while current.left is not None:
           current = current.left
       return current
   

   Trace for deleting 25:

   Step	Action	BST State
   1	Find 25 (root’s right child).	Original BST.
   2	25 has two children (20, 30).	Replace 25 with successor 26.
   3	Delete 26 (leaf).	Final BST (see earlier example).

Code Example: BST Implementation in Python

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

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

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

# Example usage:
root = None
keys = [47, 50, 25, 27, 17, 61, 5, 26]
for key in keys:
    root = insert(root, key)
print("In-order traversal:")
inorder(root)  # Output: 5 17 25 26 27 47 61

Summary Table: BST Operations

Note: h = height of the tree. For balanced trees, h = O(log n).