Binary Search Trees (BST)

1. Introduction: The Power of Order

Imagine looking up a contact in your phone. If your contacts were completely unsorted, you would have to scroll through every single name until you found the right one ($O(N)$ time). Because they are sorted alphabetically, you can instantly jump to the middle, see if the name comes before or after, and cut your search in half.

A Binary Search Tree (BST) takes this exact logic and maps it onto a Node-based tree structure. It is a Binary Tree where every node strictly obeys the BST Property:

• All nodes in the Left Subtree are strictly less than the root's value.
• All nodes in the Right Subtree are strictly greater than the root's value.
• (This applies recursively to every single node in the tree).

Because of this property, a BST allows for $O(\log N)$ average-time searches, insertions, and deletions. It perfectly bridges the gap between the rapid $O(1)$ insertions of a Linked List and the rapid $O(\log N)$ binary search of a sorted Array.

2. Core Concept: Traversal and Architecture

The Node Structure

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
    }
}

In-Order Traversal Magic

The most important mathematical property of a BST is that an In-Order Traversal (Left, Root, Right) always processes the nodes in strictly ascending sorted order. If you ever need to sort or validate a BST, an In-Order traversal is usually the answer.

3. Beginner Code Example: Search and Insertion

Search: Start at the root. If the target is smaller, go left. If it is larger, go right. Insertion: Same as search, but when you hit a null pointer, that is exactly where the new node belongs!

public class BSTBasic {
    
    // O(log N) average, O(N) worst case
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) return root;
        
        if (val < root.val) {
            return searchBST(root.left, val);
        } else {
            return searchBST(root.right, val);
        }
    }
    
    // O(log N) average, O(N) worst case
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        
        if (val < root.val) {
            root.left = insertIntoBST(root.left, val);
        } else if (val > root.val) {
            root.right = insertIntoBST(root.right, val);
        }
        
        return root; // Return the unchanged root pointer
    }
}

4. Intermediate Code Example: Validating a BST

Problem Statement: (LeetCode 98) Given the root of a binary tree, determine if it is a valid binary search tree (BST).

The Trap: Beginners often just check node.left.val < node.val && node.right.val > node.val. This is WRONG. The rule says ALL nodes in the left subtree must be smaller, not just the direct children!

The Solution: We must pass down Min and Max Boundaries as we recurse. When we go left, the current node's value becomes the new strict Maximum. When we go right, the current node's value becomes the new strict Minimum.

public class BSTValidator {
    public boolean isValidBST(TreeNode root) {
        // Use Long to avoid Integer.MIN_VALUE / MAX_VALUE edge cases
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean validate(TreeNode node, long min, long max) {
        // Base case: An empty tree is a valid BST
        if (node == null) return true;
        
        // If the node violates the min/max constraints, it's invalid
        if (node.val <= min || node.val >= max) {
            return false;
        }
        
        // Recurse left (update max boundary) AND recurse right (update min boundary)
        return validate(node.left, min, node.val) && validate(node.right, node.val, max);
    }
}

Complexity Analysis:

• Time Complexity: $O(N)$. We visit every node exactly once.
• Space Complexity: $O(H)$ where $H$ is the height of the tree (recursion stack).

5. Advanced Code Example: Lowest Common Ancestor (LCA)

Problem Statement: (LeetCode 235) Given a BST, find the lowest common ancestor (LCA) node of two given nodes in the BST. The LCA is the lowest node in the tree that has both p and q as descendants.

In a standard binary tree, LCA is a complex post-order traversal. In a BST, we can use the BST property to find the LCA in a single top-down pass without any complex backtracking!

The Insight:

• If both p and q are smaller than the root, the LCA must be in the left subtree.
• If both are larger, the LCA must be in the right subtree.
• If one is smaller and one is larger (or one equals the root), then the current root is exactly where the paths split! Therefore, the current root IS the Lowest Common Ancestor.

public class BSTLCA {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // We can do this iteratively to achieve O(1) space!
        TreeNode current = root;
        
        while (current != null) {
            if (p.val < current.val && q.val < current.val) {
                // Both are smaller, go left
                current = current.left;
            } else if (p.val > current.val && q.val > current.val) {
                // Both are larger, go right
                current = current.right;
            } else {
                // We found the split point (or one of the nodes itself)
                return current;
            }
        }
        return null; // Should not reach here if p and q exist in the tree
    }
}

Complexity Analysis:

• Time Complexity: $O(H)$, where $H$ is the height of the tree. (Average $O(\log N)$, Worst $O(N)$).
• Space Complexity: $O(1)$. Entirely iterative.

6. Common Mistakes Beginners Make

1. Local vs Global Validation

   • The Mistake: Validating a BST by only checking direct children (left.val < root.val && right.val > root.val).
   • Why it's wrong: A right child could have a left child that is incredibly small, violating the rule that it must be larger than the root.
   • The Fix: Use the Min/Max boundary parameters shown in the Intermediate example.

2. Not returning the node pointer during insertion/deletion

   • The Mistake: Writing insert(node.left, val) instead of node.left = insert(node.left, val).
   • Why it's wrong: When you allocate a new TreeNode at the bottom of the recursion, if you don't return it and reassign it to node.left, the new node instantly gets garbage collected, and the tree remains unchanged!

3. Assuming a BST is always $O(\log N)$

   • The Mistake: Thinking insertion and search are mathematically guaranteed to be $O(\log N)$.
   • Why it's wrong: If you insert sorted data (1, 2, 3, 4, 5) into a standard BST, it degrades into a Linked List. Time complexity becomes $O(N)$. To guarantee $O(\log N)$, you must use a Self-Balancing BST like an AVL or Red-Black Tree.

7. Interview Q&A

Q1: How do you delete a node in a BST? (LeetCode 450) Answer: Deletion has 3 cases:

1. Leaf Node: Simply return null to the parent.
2. One Child: Return the non-null child to the parent (bypassing the deleted node).
3. Two Children: Find the In-Order Successor (the minimum value in the right subtree). Copy its value to the current node, then recursively delete the In-Order Successor from the right subtree.

Q2: What is an In-Order Predecessor and Successor? Answer: In a sorted list of the tree's values, the Predecessor is the element immediately before a node, and the Successor is the element immediately after. In the tree structure:

• Predecessor: The maximum value in the left subtree (go left once, then right as far as possible).
• Successor: The minimum value in the right subtree (go right once, then left as far as possible).

Q3: How do you find the Kth smallest element in a BST? (LeetCode 230) Answer: Since an In-Order traversal visits nodes in ascending order, we just perform an In-Order traversal and maintain a counter. When the counter reaches $K$, we have found the $K$th smallest element! This takes $O(H + K)$ time.

8. Practice Problems

1. Validate Binary Search Tree (LeetCode 98)
   • Goal: Master the Min/Max boundary traversal.
2. Delete Node in a BST (LeetCode 450)
   • Hint: Focus on the 3 deletion cases, especially finding the in-order successor.
3. Kth Smallest Element in a BST (LeetCode 230)
   • Hint: Use a recursive in-order traversal with a global counter variable, or an iterative approach with a Stack.

9. Summary

• The Property: Left is smaller, Right is larger. Globally, not just locally.
• Traversal: In-Order traversal (Left-Root-Right) yields a perfectly sorted sequence.
• Time Complexity: Averages $O(\log N)$ because each decision halves the search space. Degrades to $O(N)$ in the worst case if the tree becomes unbalanced.
• Boundaries: When validating or constructing BSTs from arrays, strictly pass mathematical bounds (min, max) down the recursion tree.