On this page
Description
The lowest common ancestor (LCA) of two nodes is the deepest node that has both of them below it, counting a node as its own ancestor. In a general tree, finding it means searching both sides of every node (see Binary Tree LCA Search). In a BST, the values tell you which way to go. So the answer is a single walk down from the root: move left while both targets are smaller, move right while both are larger, and stop where they split.
We'll go from simple to more technical:
- The pattern: walk down until the two targets split.
- A second flavor: the distance between two nodes, measured from the LCA.
- Where the split point shows up (range scans in ordered indexes).
- What breaks it:
<=instead of<, missing keys, and measuring from the root.
The approach
In a BST, smaller keys are on the left and larger ones on the right. So at every node you can tell whether both targets are on one side. If they are, the child on that side is also a common ancestor, and a deeper one, so move to it. The first node where they're not on the same side is the LCA. That happens when one target is smaller and the other larger, or when one of them is the node.
The LCA of 4 and 6:
| At | 4 and 6 compared with it | Go |
|---|---|---|
| 7 | both smaller | left |
| 3 | both larger | right |
| 5 | 4 smaller, 6 larger | stop: the LCA is 5 |
Java
int lowestCommonAncestor(TreeNode root, int p, int q) {
TreeNode cur = root;
while (cur != null) {
if (p < cur.val && q < cur.val) {
cur = cur.left; // both targets are smaller - the LCA is further left
} else if (p > cur.val && q > cur.val) {
cur = cur.right; // both targets are larger - the LCA is further right
} else {
return cur.val; // they split here, or one of them IS this node
}
}
return -1; // unreachable when p and q are guaranteed to exist
}
Python
def lowest_common_ancestor(root: TreeNode, p: int, q: int) -> int:
cur = root
while cur is not None:
if p < cur.val and q < cur.val:
cur = cur.left # both targets are smaller - the LCA is further left
elif p > cur.val and q > cur.val:
cur = cur.right # both targets are larger - the LCA is further right
else:
return cur.val # they split here, or one of them IS this node
return -1 # unreachable when p and q are guaranteed to exist
It's one walk down one path: no recursion and no revisiting, O(h) time and O(1) space.
A second flavor: the distance between two nodes
Once you have the split point, other two-node questions follow. The number of edges between p and q is the distance from the LCA down to p plus the distance from the LCA down to q. Each is found with the same compare-and-step walk. Between 4 and 1, the LCA is 3, so the distance is 2 (3 to 5 to 4) plus 1 (3 to 1), which is 3.
Java
int distanceBetween(TreeNode root, int p, int q) {
TreeNode lca = /* split walk above */;
return edgesDown(lca, p) + edgesDown(lca, q);
}
int edgesDown(TreeNode node, int target) {
int edges = 0;
while (node.val != target) { node = (target < node.val) ? node.left : node.right; edges++; }
return edges;
}
Python
def distance_between(root: TreeNode, p: int, q: int) -> int:
lca = ... # the split walk above
return edges_down(lca, p) + edges_down(lca, q)
def edges_down(node: TreeNode, target: int) -> int:
edges = 0
while node.val != target:
node = node.left if target < node.val else node.right
edges += 1
return edges
Measuring from the root instead counts the stretch above the LCA twice. depth(p) + depth(q) overshoots by 2 * depth(lca), unless the LCA is the root.
Where you'll see it
An ordered index finds the smallest region holding two keys the same way: narrow toward both until they split. That region is where a range scan between the two keys starts.
Which tool for which job?
| You need | Use |
|---|---|
| The LCA of two keys in a BST | the split walk, O(h), O(1) space |
| The LCA in a general binary tree | search both subtrees, O(n) |
| The distance between two nodes | edges from the LCA down to each |
| An LCA when a key might be missing | two searches first, then the split walk |
| Many queries on a deep, static tree | parent pointers plus binary lifting |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
Testing "both smaller" with <= | steps past a target that is the LCA (returns 1 instead of 3 below) | strict < and >; equality means stop |
| Using the general-tree algorithm | correct, but O(n) instead of O(h) | the split walk |
| Assuming both keys exist | a missing key still returns a node, with no error | search for both first |
| Measuring distances from the root | overshoots by 2 * depth(lca) | measure down from the LCA |
The (cur - p) * (cur - q) > 0 shortcut in Java | the product overflows and the walk stops early | two plain comparisons |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. In the tree above, what is the LCA of 3 and 5, and where does the walk stop?
Show answer
- At 7 both targets are smaller, so the walk moves left to 3. At 3, one target equals the node, so neither "both smaller" nor "both larger" holds, and the walk returns 3. That's right: 5 is below 3, and a node counts as its own ancestor.
2. The first test is written p <= cur.val && q <= cur.val. What does it return for 3 and 1 in the same tree?
Show answer
1 instead of 3. At 3, both 3 <= 3 and 1 <= 3 hold, so the walk steps left to 1. At 1 the targets aren't both smaller or both larger, so it returns 1, one node past the real LCA. Strict < and > let equality stop the walk at the right node.
3. Why is the distance edgesDown(lca, p) + edgesDown(lca, q) and not depth(p) + depth(q)?
Show answer
The path between two nodes goes up from p to the LCA and back down to q. It never goes above the LCA. Depths measured from the root include the stretch from the root to the LCA twice, once for each node.
Key takeaways
- While both targets are smaller, go left; while both are larger, go right.
- The first node where they split, or where one of them equals the node, is the LCA. Use strict
<and>. - It's one O(h) walk with O(1) space and no recursion.
- The general-tree algorithm also works on a BST, but it's O(n) where O(h) is possible.
- The distance between two nodes is measured down from the LCA.