L47. LCA in Binary Search Tree

Finding the Lowest Common Ancestor (LCA) in a Binary Search Tree (BST) is a classic algorithmic problem. Because a Binary Search Tree possesses an inherent ordering property—where all elements in the left subtree are smaller than the node, and all elements in the right subtree are greater—we can leverage this structural invariant to find the LCA much more efficiently than in a standard binary tree.

1. Defining the Problem: What is an LCA?

The Lowest Common Ancestor (LCA) of two nodes $P$ and $Q$ in a tree is defined as the lowest node in the tree that has both $P$ and $Q$ as descendants (where we allow a node to be a descendant of itself).

• Path to Root visualization: If you trace the path from node $P$ up to the root, and trace the path from node $Q$ up to the root, the two paths will overlap.
• Intersection Point: The LCA is the first intersection point when looking from the bottom up, or the last intersection point when looking from the top down.

2. Naive Approach vs. BST-Optimized Approach

The Naive Binary Tree Approach

If you treat the BST as a generic Binary Tree (ignoring the left-less, right-greater rule):

• You must traverse the entire tree to locate both nodes or use a recursive function visiting every node.
• Time Complexity: $\mathcal{O}(N)$, where $N$ is the total number of nodes in the tree.

The BST-Optimized Approach

Because it is a Binary Search Tree, we do not need to traverse every node blindly. We can navigate based on value comparisons, drastically cutting down our search space to the height of the tree.

• Time Complexity: $\mathcal{O}(H)$, where $H$ is the height of the tree (which is $\mathcal{O}(\log N)$ for balanced BSTs).
• Space Complexity: $\mathcal{O}(1)$ iterative auxiliary space (or $\mathcal{O}(H)$ recursive stack space).

3. Core Mental Model and Decision Possibilities

When standing at any current node during our traversal while searching for nodes $P$ and $Q$, there are four fundamental relative positioning possibilities:

1. Both nodes lie to the right: Both $P.\text{val}$ and $Q.\text{val}$ are strictly greater than the current node's value.
2. Both nodes lie to the left: Both $P.\text{val}$ and $Q.\text{val}$ are strictly smaller than the current node's value.
3. Split Path (LCA Found): One node lies on the left subtree and the other lies on the right subtree (or one of the nodes is the current node itself).
4. Current Node is $P$ or $Q$: The current node matches one of the target values.

Real-Life Analogy: Navigating a City Grid

Imagine looking for a meeting point between two friends coming from different neighborhoods. If both friends live strictly north of your current highway exit, you must drive further north. If both live south, you drive south. The exact moment their paths diverge—where one friend needs to go left (west) and the other right (east)—is your optimal meeting point (the LCA).

4. Step-by-Step Flow Walkthrough

Let us trace an example using a BST where we want to find the LCA of nodes 5 and 9.

          10
         /  \
        4    12
       / \
      2   8
         / \
        5   9

• Step 1: Start at root 10. We are looking for 5 and 9.
  • Are both values $< 10$? Yes ($5 < 10$ and $9 < 10$).
  • Action: Move to the left child (4).
• Step 2: At node 4.
  • Are both values $< 4$? No ($5 > 4$ and $9 > 4$).
  • Are both values $> 4$? Yes ($5 > 4$ and $9 > 4$).
  • Action: Move to the right child (8).
• Step 3: At node 8.
  • Are both values $< 8$? No ($5 < 8$, but $9 > 8$).
  • Are both values $> 8$? No ($5 < 8$, but $9 > 8$).
  • Path Split: The values have split across the current node. One is smaller ($5$), one is greater ($9$).
  • Conclusion: Node 8 is our Lowest Common Ancestor.

5. Comparative Strategy Table

6. Implementation Code (Recursive Java Solution)

Below is the clean, production-grade recursive implementation in Java as demonstrated in the lecture. The C++ implementation is structurally identical, substituting arrow operators (->) for dot notation (.) where applicable.

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

public class BSTLowestCommonAncestor {
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Base case: if root is null, return null
        if (root == null) {
            return null;
        }
        
        // If both nodes are greater than the current node, LCA lies in the right subtree
        if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        
        // If both nodes are smaller than the current node, LCA lies in the left subtree
        if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        
        // If neither condition is met, we have hit the split point (LCA)
        return root;
    }
}

Note on Iterative Optimization: While the recursion above takes $\mathcal{O}(H)$ stack space, you can easily rewrite this logic using a simple while (root != null) loop to achieve $\mathcal{O}(1)$ auxiliary space complexity by reassigning root = root.left or root = root.right dynamically.

7. Summary and Key Takeaways

• BST Invariant Utilization: Always look to exploit BST properties (left < node < right) to avoid unnecessary traversal.
• Definition of LCA: The lowest common ancestor is the exact divergence/split point where target nodes stop sharing the same subtree direction.
• Comparison Rules:
  • If p.val > root.val and q.val > root.val $\rightarrow$ Traverse Right.
  • If p.val < root.val and q.val < root.val $\rightarrow$ Traverse Left.
  • Otherwise $\rightarrow$ Current root is the LCA.
• Time Complexity: Bounded by the height of the tree: $\mathcal{O}(H)$, transforming worst-case linear time ($\mathcal{O}(N)$) into logarithmic time ($\mathcal{O}(\log N)$) for balanced trees.
• Space Complexity: Can be optimized from $\mathcal{O}(H)$ recursion stack down to $\mathcal{O}(1)$ space using a straightforward iterative while loop.