On this page
Description
The lowest common ancestor (LCA) of two nodes is the deepest node that has both of them in its subtree. It's the point where their paths from the root split. One recursive pass finds it. Each subtree reports whether it found a target, and the first node where both sides report one is the answer. A second approach records each node's path from the root and compares the two.
We'll go from simple to more technical:
- The pattern: one pass, each side reports up.
- A second flavor: compare the two root-to-node paths.
- Where "closest shared parent" questions appear in production.
- The assumption the one-pass version depends on - that both nodes exist.
The approach
Ask every subtree one question: "did you find p or q?" A subtree with neither returns null. A node that is p or q returns itself right away. Every other node passes up whatever its children found. The first node to hear back from both sides is where the two targets split: the LCA.
Finding the LCA of 1 and 5:
| Node | Left reports | Right reports | Returns |
|---|---|---|---|
| 1 | itself: it's a target | ||
| 3 | nothing | nothing | null |
| 5 | itself: it's a target | ||
| 4 | null | 5 | 5, passed up |
| 2 | 1 | 5 | 2: both sides found one, so 2 is the LCA |
| 9 | nothing | nothing (11 isn't a target) | null |
| 6 | 2 | null | 2, passed up |
Java
TreeNode find(TreeNode node, int p, int q) {
if (node == null || node.val == p || node.val == q) return node;
TreeNode left = find(node.left, p, q);
TreeNode right = find(node.right, p, q);
if (left != null && right != null) return node; // found one on each side - this IS the LCA
return (left != null) ? left : right; // otherwise, pass up whichever side found something
}
Python
def find(node: TreeNode | None, p: int, q: int) -> TreeNode | None:
if node is None or node.val in (p, q):
return node
left = find(node.left, p, q)
right = find(node.right, p, q)
if left is not None and right is not None:
return node # found one on each side - this IS the LCA
return left if left is not None else right # otherwise, pass up whichever side found something
Returning a target without searching inside it is safe when both targets are guaranteed to exist. If the other target is below it, the found node is the LCA anyway, since a node counts as its own ancestor. For 4 and 5 above, the answer is 4.
A second flavor: comparing two root-to-node paths
A more explicit way: build each target's path from the root (the search from Binary Tree DFS Traversal Orders), then walk both paths from the front. The last place they still agree is the LCA. For 1 and 5, the paths are 6, 2, 1 and 6, 2, 4, 5. They agree on 6 and 2, so the LCA is 2.
Java
List<Integer> pathToP = rootToNodePath(root, p); // reuse the root-to-node-path technique
List<Integer> pathToQ = rootToNodePath(root, q);
int lca = pathToP.get(0); // the root, guaranteed to be common to both
for (int i = 0; i < Math.min(pathToP.size(), pathToQ.size()); i++) {
if (!pathToP.get(i).equals(pathToQ.get(i))) break;
lca = pathToP.get(i);
}
return lca;
Python
def lca_by_paths(root: TreeNode, p: int, q: int) -> int:
path_to_p = root_to_node_path(root, p) # reuse the root-to-node-path technique
path_to_q = root_to_node_path(root, q)
lca = path_to_p[0] # the root, guaranteed to be common to both
for a, b in zip(path_to_p, path_to_q):
if a != b:
break
lca = a
return lca
This is easier to trust at a glance but does more work: two searches plus a comparison, against one pass.
Where you'll see it
The closest shared folder of two files is an LCA. So is the most specific category two products share in a store's catalog tree. Both ask where two paths from the root stop agreeing.
Which tool for which job?
| You need | Use |
|---|---|
| One LCA query, both nodes guaranteed present | the one-pass recursion |
| One query, a node might be missing | the recursion without early return, counting found targets |
| Nodes with parent pointers | equalize depths, then walk up together |
| Many queries on the same tree | binary lifting (O(log n) per query) |
| LCA in a BST | walk down by comparing values (no recursion over both sides) |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Trusting the result when a target may be missing | returns the target that was found | count both targets, or check existence first |
| Searching inside a found target | wasted work | return as soon as a target is found |
| Comparing by value with duplicate values | the wrong node matches | compare node references |
| One full search per query, many queries | O(n) each | preprocess: binary lifting |
| Comparing paths built by copying lists | O(n h) memory | push and pop one path |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. What does the one-pass version return if q isn't in the tree at all?
Show answer
Most likely the node for p, with no warning. The algorithm assumes both targets exist and has no way to check. If a target might be missing, count the targets found, or check that both exist first.
2. Why is the first node to hear back from both sides the lowest common ancestor, not just some ancestor?
Show answer
Higher ancestors also contain both targets, but there both targets sit on the same side, so only one child reports back. The node where the targets are on different sides is the deepest one that still has both. That's the definition of the lowest common ancestor.
3. Why is the LCA the last place the two root-to-node paths agree, not the first?
Show answer
Every shared ancestor appears in both paths, in the same order, from the root down. The paths only differ once the targets head into different children. The last shared entry, just before that split, is the deepest common ancestor.
Key takeaways
- The node where both recursive calls find something is the lowest common ancestor.
- Returning a target early is safe only when both targets are sure to exist.
- Comparing two root-to-node paths finds the same node: the last place they agree.
- Both approaches answer one question: where do the paths to the two targets split?