Lowest Common Ancestor of a BST
Find where two nodes' paths split, using the ordering of a BST to walk straight there without any searching
Problem Statement
Given a binary search tree and two nodes p and q that both exist in it, return their lowest common ancestor — the deepest node that has both as descendants.
A node counts as a descendant of itself.
6
/ \
2 8
/ \ / \
0 4 7 9
/ \
3 5
p = 2, q = 8 → 6 (their paths split at the root)
p = 2, q = 4 → 2 (2 is an ancestor of itself)Intuition
In a plain binary tree this is real work: you must search both subtrees and reason about what came back. But this is a search tree, and that changes everything.
Stand at any node and compare it against both targets. There are only three possibilities.
| Situation | What it means | What to do |
|---|---|---|
Both p and q are smaller | Both live in the left subtree | Go left |
Both p and q are larger | Both live in the right subtree | Go right |
| They fall on opposite sides (or one is this node) | The paths part here | This is the answer |
The key insight
The lowest common ancestor is exactly the first node where the two targets stop agreeing on a direction.
While both say "go left", they are still travelling together. The moment one says left and the other says right, they have separated — and the node they separated at is their deepest shared ancestor.
There is no searching, no backtracking and nothing to compare on the way back up. You walk down once and stop.
Why the first split is the lowest ancestor
It sounds backwards that the first node you meet is the lowest ancestor. Here is why it holds.
Everything above the split point is also a common ancestor — but higher up, and so not the lowest. Everything below the split point lies on one side only, so it cannot contain both.
That makes the split point the unique deepest node containing both.
The real-world version
Two people follow the same road out of a city. They stay together through every junction where their directions match. The moment their directions differ, they part — and that junction is the last place they were together.
Approach
Start at the root
The root is always a common ancestor, since every node is below it. The job is to get as deep as possible.
If both targets are smaller, move left
Neither can be in the right subtree, so the whole right half is discarded — exactly like binary search.
If both targets are larger, move right
The mirror image.
Otherwise, stop and return this node
Either the targets straddle it, or one of them is it. Both cases mean the split happens here.
The 'or one of them is this node' case comes free
If p is the current node, then p is not strictly less and not strictly greater than itself. Both branch conditions fail, so the loop stops and returns the node.
That is exactly right, because a node is its own descendant. No special case is needed.
Watch it run
Solution
class TreeNode:
def __init__(self, val: int = 0, left: "TreeNode | None" = None,
right: "TreeNode | None" = None):
self.val = val
self.left = left
self.right = right
def lowest_common_ancestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
"""Walk down until p and q disagree about which way to go."""
node = root
while node:
if p.val < node.val and q.val < node.val:
node = node.left # both on the left
elif p.val > node.val and q.val > node.val:
node = node.right # both on the right
else:
return node # they split here, or one IS here
return root # unreachable when both nodes are guaranteed present
def lowest_common_ancestor_recursive(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
"""Same logic expressed recursively. The iterative form is preferred:
it uses O(1) space because nothing happens after the recursive call."""
if p.val < root.val and q.val < root.val:
return lowest_common_ancestor_recursive(root.left, p, q)
if p.val > root.val and q.val > root.val:
return lowest_common_ancestor_recursive(root.right, p, q)
return rootComplexity Analysis
Time Complexity
O(h)
Space Complexity
O(1)
- Time — one step per level, so the height of the tree. That is
O(log n)when balanced, andO(n)for a tree shaped like a chain. - Space — the iterative version keeps a single variable. Nothing is stored, and nothing is revisited.
Why this is really binary search
Look at the loop again: compare, discard half, repeat. That is the same move as Binary Search, with tree links instead of array indices.
The ordering guarantee is what both rely on. Take it away — an ordinary binary tree — and the problem becomes genuinely harder, because you must search both sides and combine the results.
Edge Cases
Related Problems
- Validate Binary Search Tree — checking the property this problem relies on
- Binary Search — the same discard-half move, on an array
- Maximum Depth of Binary Tree — where recursion genuinely is needed