Binary Search Trees (BST)

# CHAPTER 8

Binary Search Trees (BST) #

1. Introduction #

2. Learning Objectives #

• Define the absolute mathematical Property that separates a BST from a standard Binary Tree.

• Execute a blistering fast $O(\log N)$ search algorithm.

• Understand the extreme danger of Degenerate (Unbalanced) BSTs.

• Identify the connection between Inorder Traversal and sorted arrays.

3. The BST Property (The Golden Rule) #

1. 1. The Left Subtree Constraint: Every single node residing anywhere in the entire Left Subtree must have a numerical value Strictly Less Than ($<$) the Root's value.

1. 2. The Right Subtree Constraint: Every single node residing anywhere in the entire Right Subtree must have a numerical value Strictly Greater Than ($>$) the Root's value.

1. 3. Recursive Reality: This exact law must apply perfectly to every sub-level node acting as its own localized root.

Valid BST Example:

        10
       /  \
      5    15
     / \   / \
    2   7 12 20

*(Notice: Everything to the left of 10 is smaller. Everything to the right of 10 is larger. And under 15, 12 is smaller, 20 is larger. Flawless execution!).*

4. Blistering Fast Searching ($O(\log N)$) #

1. 1. Start at the Root (10).

1. 2. Is 7 == 10? No. Is 7 < 10? Yes.

1. 3. The Magic: Because $7$ is smaller, the algorithm permanently deletes and ignores the entire Right Subtree (15, 12, 20). In one single CPU cycle, we just eliminated 50% of the entire database!

1. 4. Jump down to Left Child (5).

1. 5. Is 7 == 5? No. Is 7 > 5? Yes.

1. 6. Jump down to Right Child (7). Found it!

In a perfectly balanced tree of 1 Billion nodes, a BST slices the data in half continuously ($1B \rightarrow 500M \rightarrow 250M \rightarrow 125M$). It will find the exact data point in a maximum of exactly 30 steps. This logarithmic scaling is the backbone of all global software.

5. Inorder Traversal = Sorted Output #

6. The Danger: Degenerate Trees #

• Insert 10 (Root).

• Insert 20 (Larger, goes Right).

• Insert 30 (Larger, goes Right).

• Insert 40 (Larger, goes Right).

You just created a right-leaning straight line. You created a Degenerate Tree. The BST lost its geometric branching. If you search for 40, you cannot cut the data in half. You must scan sequentially. The magnificent $O(\log N)$ Time Complexity has violently degraded into horrific $O(N)$ Linear Time.

7. Code Execution: Search Algorithm #

def search_bst(root, target):
    current = root
    
    while current is not None:
        if current.val == target:
            return True # Target Found!
        elif target < current.val:
            current = current.left # Slice matrix left
        else:
            current = current.right # Slice matrix right
            
    return False # Hit a dead end (null), target does not exist.

8. Complexity Analysis #

• Time Complexity (Best/Average): $O(\log N)$ (Perfect logarithmic geometric slicing).

• Time Complexity (Worst Case): $O(N)$ (The tree structurally degrades into a straight-line Linked List).

• Space Complexity: $O(1)$ for Iterative Search, $O(\log N)$ for Recursive Search.

9. Common Mistakes #

• Checking only immediate children: A massive novice error is validating a BST by simply checking if the Left Child $< $ Root $<$ Right Child. That is FALSE. You must verify that the *entire Left Subtree* deeply nested below the left child is smaller than the Root. If a value 99 is hiding deeply at the bottom of the Left Subtree, the entire global BST is mathematically invalid!

10. Exercises #

1. 1. Determine if the following tree is a valid BST: Root(20), LeftChild(10), RightChild(30), LeftChild's RightChild(25).

1. 2. Trace the search path execution to locate the value 12 in the Valid BST shown in Section 3.

11. MCQs with Answers #

12. Interview Preparation #

• *Algorithmic Validation:* "Write an algorithm to definitively check if a Binary Tree is a valid BST." *(Answer: Do NOT just check if Left < Parent. Write a recursive function passing a MinValue and MaxValue boundary parameter downward. def isValid(node, min, max): if node.val <= min or node.val >= max: return False. It ensures deeply nested outliers are instantly flagged!)*

13. Summary #

14. Next Chapter Recommendation #