BST
Walk down using the invariant
Why it matters
Common-ancestor queries support permission inheritance, directory navigation, and relationships inside ordered indexes. A general tree search inspects both subtrees even when key order has already ruled one side out. The lowest shared ancestor must be found without exploring branches that cannot contain either target.
Example
Lowest Common Ancestor of a BST
Find the lowest common ancestor of values p and q in a BST. Walk from the root: both smaller → go left, both larger → go right, otherwise this node is the split.
- Input
- root = [6, 2, 8, 0, 4, 7, 9, None, None, 3, 5], p = 3, q = 5
- Output
- 4
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Lowest Common Ancestor of a BST
root = [6, 2, 8, 0, 4, 7, 9, None, None, 3, 5], p = 3, q = 5→4
The baseline, Ignore the BST rule, is O(n) · O(h). The better model below keeps this exact input and removes that bottleneck.
For p = 3 and q = 5 in the tree rooted at 6, general DFS searches both sides. BST comparisons follow only 6 → 2 → 4: both targets choose the same side until they split at 4.
In [6, 2, 8, 0, 4, 7, 9, None, None, 3, 5], both targets 3 and 5 are below 6, so move left to 2. Both are above 2, so move right to 4.
At 4, target 3 belongs on the left and target 5 on the right. Their paths separate there, making 4 the deepest node whose subtree contains both. If one target equaled the current value, that node would also be the answer.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.