In a binary search tree, why must the first node whose key sits between two target keys be their lowest common ancestor?

## What the question is really about The lowest common ancestor (LCA) of two nodes in a rooted tree is the deepest node that has both of them in its subtree, counting a node as an ancestor of itself. That definition works on *any* rooted tree. What makes a **binary search tree** special is not the definition but the shortcut: ordering lets you find the LCA by descending once from the root, comparing keys, without ever searching a subtree you do not enter. A concrete setting: a catalogue service keeps its category IDs in a search tree used as an index. Two IDs arrive, and you want the smallest indexed subtree that contains both — the node you can hand a range scan so it never touches keys outside the pair's span. That node is the LCA of the two keys, and it is often called the **split node** for exactly this reason. ## The ordering invariant In a binary search tree, for every node `v`: every key in `v`'s left subtree is smaller than `v.key`, and every key in `v`'s right subtree is larger. That single property is what turns a comparison into a routing decision. If a target key `a` satisfies `a < v.key`, then `a` cannot be anywhere in `v`'s right subtree — not because you looked, but because the invariant forbids it. ## The argument, step by step Stand at some node `v` that is known to contain both targets `a` and `b` in its subtree (true at the root, assuming both are present). - If `a < v.key` **and** `b < v.key`, both must live in the left subtree. So the left child also contains both, and it is deeper. `v` is therefore not the *lowest* common ancestor — descend left. - Symmetrically, if both keys exceed `v.key`, descend right. - Otherwise the keys straddle `v.key` (one below, one above), or one of them equals `v.key`. Now no single child of `v` can hold both: one target sits on the left side, the other on the right (or is `v` itself). `v` contains both and no descendant does, so `v` is the LCA. Each loop iteration either descends one level or terminates, so the loop runs at most `h + 1` times where `h` is the height. It keeps one cursor, so extra space is `O(1)`. ## Costs, stated precisely The cost is `O(h)`, not `O(log n)`. Those coincide **only when the tree is balanced**. A search tree built by inserting already-sorted IDs degenerates into a chain, and then `h = n - 1` and this descent is `O(n)` — the same order as searching an unordered tree. "Search tree" is a shape claim about ordering, never a promise about height; only a self-balancing variant makes the `O(log n)` claim honest. ## The boundary cases interviewers probe **One target is an ancestor of the other.** If `a` sits above `b`, the descent reaches the node holding `a` and stops there, because `a == v.key` no longer routes in a single direction. The answer is `a` itself — correct, because a node is its own ancestor. Candidates who define ancestry as *strictly* above get this wrong and start hunting for a parent. **A target is missing from the tree.** The loop still stops somewhere: at the deepest node whose key lies between the two search keys, or it runs off the bottom and finds nothing. That stopping node is the split point of the two *search paths*, which is a meaningful object for a range scan, but it is not the LCA of two existing nodes. If your caller needs the guarantee that both nodes exist, verify presence — you can do it during the same descent by remembering whether each key was matched. **Duplicate keys.** If the tree admits duplicates, "the node with key `a`" is ambiguous and so is its ancestor. Pin down the duplicate policy before claiming the shortcut applies. ## Why it evaporates without ordering On a binary tree with no key order, comparing a target key to `v.key` yields no information about which side holds the target, so no subtree can be skipped. You are forced into a full traversal, and the LCA is found by a different technique entirely: recurse into both children and look for the node where the two targets surface from different sides. That is `O(n)`, and it is the price of losing the invariant — which is the real lesson of this question. The shortcut is not a property of trees; it is a property of *ordered* trees, and it is worth exactly as much as the invariant you can prove still holds.