The Lowest Common Ancestor problem looks scary on a general tree, but on a binary search tree it becomes one of the cleanest problems in interviews. The trick is to stop treating the tree as a maze and start using the one rule a BST always obeys: everything on the left is smaller, everything on the right is bigger.
Problem. Given a binary search tree and two nodes p and q, return their lowest common
ancestor (LCA) — the deepest node that has both p and q somewhere in its subtree (a node can be
its own descendant).
Example: in the tree below, the LCA of p = 3 and q = 5 is 4, because 3 is in 4's left subtree
and 5 is in 4's right subtree.
The idea
In a BST, every node splits the values: smaller ones go left, bigger ones go right. That single fact tells us which way to walk.
Start at the root and compare both targets to the current node:
- If both
pandqare smaller than the node, they must both live in the left subtree, so walk left. - If both are bigger, they both live in the right subtree, so walk right.
- Otherwise they split — one is
<=the node and the other is>=it (or one is the node). The current node is the deepest point where their paths separate, so it is the LCA.
The moment the two targets stop agreeing on a direction, you have found the answer. No recursion needed and no extra memory.
Walk through it
Step through the animation. The pointer starts at the root 6. Both targets are smaller, so we go left to 2. Both are bigger than 2, so we go right to 4. At 4 the targets disagree — 3 is smaller and 5 is bigger — so 4 is the split point and the LCA.
Pseudocode
node = root
loop:
if both p and q are smaller than node:
node = node.left # both targets are to the left
else if both p and q are bigger than node:
node = node.right # both targets are to the right
else:
return node # they split here → this is the LCAThe loop always makes progress: each turn moves us one level deeper, so it ends in at most the height of the tree.
The Python solution
def lowest_common_ancestor(root, p, q):
node = root
while node:
if p.val < node.val and q.val < node.val:
node = node.left
elif p.val > node.val and q.val > node.val:
node = node.right
else:
return nodenodeis our pointer, starting at the root.- Line 4: if both values are below
node, the whole answer is on the left, so move left. - Line 6: if both values are above
node, move right. - Line 9: the
elsefires the instant the targets disagree (or one equalsnode). That node is the lowest common ancestor, so we return it.
Because we only ever go one direction, the walk costs O(h) time, where h is the height of the tree, and uses O(1) extra space.
Complexity
| Case | Time | Notes |
|---|---|---|
| Balanced BST | O(log n) (fast) | height is about log n |
| Worst case (skewed tree) | O(n) (moderate) | a long chain has height n |
O(1) (fast)We walk a single path from the root down to the split point — never more than the height of the tree. The iterative version uses O(1) space because it keeps only one pointer (a recursive version would use O(h) stack space).
When this pattern shows up
Whenever a tree problem gives you a BST, the ordering rule is the whole point — let the values steer you left or right instead of searching blindly. The same compare-and-descend move powers BST search, insert, and "closest value" problems.
This trick relies on the BST property. On a plain binary tree there is no ordering, so you cannot
pick a direction — you must search both subtrees recursively instead. Also remember a node can be its
own ancestor: if p equals the current node, the else branch correctly returns it.
Practice
Walking for p = 3 and q = 5, after we move from the root 6 to node 2, which way do we go next and why?
1. How do we decide which way to walk at each node?
2. When is the current node the LCA?
3. What is the time complexity on a balanced BST?
4. Why does the iterative version use O(1) extra space?