Binary Search Trees (BST)

# CHAPTER 20

Binary Search Trees (BST) #

1. Introduction #

2. Learning Objectives #

• Define the absolute mathematical property of a BST.

• Execute the algorithm to manually trace and Insert data into a BST.

• Understand the O(log n) Searching mechanism.

• Discover the hidden magic of the In-Order Traversal on a BST.

• Identify the fatal architectural vulnerability of an "Unbalanced" BST.

3. The BST Property (The Golden Rule) #

1. 1. Left Subtree: All values in the entire left branch must be LESS THAN the parent node's value.

1. 2. Right Subtree: All values in the entire right branch must be GREATER THAN the parent node's value.

Visualizing a Valid BST:

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

*Notice how everything to the left of 50 is smaller, and everything to the right is larger. The rule cascades recursively! Everything left of 30 is smaller than 30.*

4. The Magic of Searching (O(log n)) #

1. 1. Start at the Root [50]. Is 60 > 50? Yes. We go Right.

1. 2. Now at [70]. Is 60 < 70? Yes. We go Left.

1. 3. Arrive at [60]. Found it!

Because we destroy half the remaining data on every single step down the tree, the algorithm scales logarithmically. If the tree has 1,000,000 nodes, we find the answer in approximately 20 steps. This is O(log n) Time Complexity.

// Java Example: Recursive O(log n) BST Search
public Node searchBST(Node root, int target) {
    // Base Cases: root is null (not found) or key is present at root
    if (root == null || root.data == target)
        return root;

    // Target is smaller than root's data? Dive LEFT!
    if (target < root.data)
        return searchBST(root.left, target);

    // Target is larger than root's data? Dive RIGHT!
    return searchBST(root.right, target);
}

5. Inserting Data into a BST #

# Python Example: Recursive BST Insertion
def insert_node(root, data):
    # Base Case: We found the empty spot! Plant the node.
    if root is None:
        return Node(data)
        
    # Recursive Routing Logic
    if data < root.data:
        root.left = insert_node(root.left, data) # Route Left
    elif data > root.data:
        root.right = insert_node(root.right, data) # Route Right
        
    return root # Return the unchanged node pointer

6. The "In-Order Traversal" Hack #

7. Deletion in a BST (The Nightmare Scenario) #

• Case 1 (Target is a Leaf): Easy. Just delete it.

• Case 2 (Target has 1 Child): Easy. Delete the target and wire its parent directly to its single child (bypassing the target).

• Case 3 (Target has 2 Children): Hard. If you delete the Root [50], what replaces it? 30 or 70? The rule is: You must replace it with its In-order Successor (the absolute smallest number in its Right subtree). In our diagram, if 50 dies, 60 is promoted to the Root!

8. The Fatal Flaw: The Unbalanced Tree #

  [10]
    \
    [20]
      \
      [30]
        \
        [40]
          \
          [50]

This is a disaster. It is no longer a Tree; it has violently degraded into a Singly Linked List! The Height of the tree is N. Searching for 50 now takes O(n) Worst-Case Time. A BST only guarantees O(log n) speed if the branches are relatively balanced (symmetrical).

9. Real-World Applications #

1. 1. Database Indexing: Relational databases utilize highly complex, self-balancing variations of BSTs (B-Trees) to ensure SELECT queries return in milliseconds.

1. 2. 3D Video Games: "Binary Space Partitioning" (BSP) trees sort geometric shapes to mathematically determine which walls the player's camera can see, discarding half the map instantly to save GPU power.

10. Common Mistakes #

• Validating a BST poorly: A junior dev will check node.left < node and node.right > node and think the tree is valid. This is wrong! The rule applies to the ENTIRE subtree. A node 10 levels deep on the Left branch MUST be smaller than the absolute Root. You must pass explicit MIN and MAX bounds recursively down the tree to validate it.

11. Exercises #

1. 1. Trace the insertion of these numbers into an empty BST: 100, 50, 150, 25, 75, 200. Draw the resulting Tree.

1. 2. Looking at your drawing, trace the path to search for the number 75.

12. MCQs with Answers #

13. Interview Preparation #

• *Algorithmic Coding:* "Find the Lowest Common Ancestor (LCA) of two given nodes in a Binary Search Tree." *(Answer: Start at the Root. If both target nodes are smaller than the Root, dive Left. If both are larger, dive Right. If they split (one is smaller, one is larger), you are sitting exactly on the LCA! O(log n) time!).*

Common Pitfalls:

• Panicking during the "Delete a Node" whiteboard question. Interviewers rarely ask you to code the 2-child deletion logic from scratch because it's too long. Focus heavily on flawlessly explaining the *theory* of the In-order Successor replacement.

14. FAQs #

15. Summary #

16. Next Chapter Recommendation #