Lowest Common Ancestor of a Binary Search Tree

Problem

Organizational hierarchies, DNS zone delegation, and version control merge-base algorithms all reduce to finding the lowest common ancestor: the deepest shared ancestor of two nodes. Given a BST and two node values p_val and q_val that are guaranteed to exist in the tree, find their lowest common ancestor using the BST ordering property.

BST:     6
        / \
       2   8
      / \ / \
     0  4 7  9
 
lca_bst(root, 2, 8) → node 6  (split at root)
lca_bst(root, 2, 4) → node 2  (4 is in 2's subtree)
lca_bst(root, 3, 5) → node 4

Solution

Approach - BST-guided walk to the split point.

The lowest common ancestor is the deepest node from which p and q descend into different directions - the node where their paths from the root diverge. The BST ordering property lets you find it without ever searching both subtrees. At each node, compare both target values to root.val. If both are smaller, the LCA must lie entirely in the left subtree, so recurse left. If both are larger, recurse right. If they straddle the current node - one smaller, one larger, or one equal to root.val - then this node is the split point and is the LCA, so return it. A node counts as its own ancestor, which is why an equal value also stops the walk.

Trace the BST 6 -> (2 -> (0, 4 -> (3, 5)), 8 -> (7, 9)) with targets 2 and 8. At root 6, 2 < 6 but 8 > 6, so they diverge - return 6 immediately, the best case visiting a single node. Now targets 3 and 5: at root 6 both are smaller, go left to 2; both are larger than 2, go right to 4; now 3 < 4 and 5 > 4, they split, return 4. The walk follows exactly one root-to-split path, never branching. This only works because the BST property guarantees each target lives in exactly one subtree per node - on a general (unordered) binary tree you would need a full postorder DFS searching both sides.

Edge cases - When one target is an ancestor of the other, the walk reaches that ancestor (its value equals root.val), and the else branch returns it. Targets on opposite sides of the root return the root in one step.

Complexity - O(h) time, O(h) space - a single root-to-split descent, height-bounded; the recursion can be flattened to an iterative while loop for O(1) space.