Lowest Common Ancestor of a BST
WHAT IT SAYS
Find the lowest common ancestor of two given nodes in a binary search tree.
WHAT IT'S REALLY ASKING
"In a plain binary tree you must EXPLORE to find where p and q live. In a BST you already know: compare them to the current node and the ordering tells you which subtree holds each. Both smaller — the split is somewhere left. Both larger — somewhere right. One on each side — you are STANDING on the split. The LCA is the first node your descent fails to get past."
Run the general binary-tree LCA
O(n) time — every subtree may be asked — O(h) stackUse the reports-collide recursion that works on any binary tree: each subtree reports which targets it contains; the node where two non-null reports meet is the LCA.
WHERE THE WORK IS WASTED — Correct, but it treats the tree as unordered and pays the full exploration price for that blindness: both children of every node get recursed into, because without ordering there is no telling where p and q are hiding. The BST invariant answers precisely that question — 'which side is it on?' — in one comparison, no descent. Using the general algorithm here discards a certificate the structure paid insertion-time costs to maintain. The word 'search' is in the tree's name; this solution never searches, it canvasses.
The LCA is where the two descents are forced apart.
Characterise the LCA by value rather than by structure: it is the unique node whose value lies BETWEEN p and q (inclusive of the endpoints — one target may be the other's ancestor). Why: the paths from the root to p and to q are identical until some node splits them, and at every shared node before the split, both targets steered the SAME way — both smaller, or both larger. At the split node they steered differently, meaning one target is ≤ the node ≤ the other. That node is the deepest shared ancestor by construction, and its value's betweenness is what forced the split. So the algorithm is a single steered descent, no recursion into both children, no reports: at each node, if both p and q are smaller, the split lies left — go left; if both larger, go right; otherwise (they straddle the value, or one equals it) STOP — you are at the split, which is the LCA. Each comparison discards an entire subtree from consideration, the signature move of every BST algorithm, and the walk touches exactly one root-to-LCA path: O(h), with O(1) space in the iterative form since nothing needs remembering — no backtracking can ever be required, because each step's direction was provably forced. Contrast with the general-tree version, because the contrast IS the lesson: there, the answer emerges bottom-up from information gathered below (post-order, reports colliding); here, it is decided top-down from information available at each node (the ordering). Structure with an invariant converts exploration into steering. The same collapse — O(n) canvass becomes O(h) descent — is exactly what the BST buys for search, insert, delete, successor: LCA just joins the list once you see its value-betweenness characterisation.
One loop, two comparisons per step
O(h) time — a single descent — O(1) iterative spacecursor = root. While both p and q are smaller than cursor, go left; while both larger, go right; the first cursor that neither condition moves is the LCA — return it. Recursion mirrors it in three lines if preferred, but the loop's O(1) space and impossibility of stack overflow make it the production choice.
Steer, Don't Explore
YOU'LL SEE IT AGAIN WHEN
- The structure maintains an ordering invariant, so 'which side is it on?' is answerable by comparison rather than by descent.
- The target has a value-based characterisation (between, smallest-above, largest-below) independent of tree shape.
- Each step's direction is provably forced, so no backtracking — hence no stack, no reports, O(1) space.