Lowest common ancestor
Return the found node upward; the first node that hears from both sides is the LCA.
A non-null return means 'p or q is in this subtree'.
01The intuition
Start with what you would do by hand
In a family tree the lowest common ancestor (LCA) of two people is the nearest person who is an ancestor of both. Take the tree with 3 at the top; 5 and 1 below it; 6 and 2 under 5; 0 and 8 under 1. The LCA of 6 and 2 is 5, because both sit under 5 and 5 is lower than 3.
By hand you would write the path from the root to 6 (3, 5, 6) and the path to 2 (3, 5, 2), then read the last node they share: 5. That needs two searches to find the paths, each possibly visiting the whole tree, and a comparison of the two lists. It works, and it is already linear, but it stores paths and makes two passes. The pattern below does it in one pass with nothing stored.
Build the structure, one piece at a time
Piece one: give every node a question to answer about its own subtree: "do you contain p or q?" The answer is not yes or no; it is a node. A subtree that contains neither returns nothing (null). A subtree that contains exactly one of them returns that node. A subtree that contains both returns their LCA.
Piece two: the shortcut. If a node is itself p or q, return the node at once without looking below it. Either the other target is below it, in which case this node is the LCA anyway, or it is elsewhere, in which case this node is the one thing to report upward.
Piece three: a node that is neither asks its left child and its right child. If both come back with something, the two targets are on different sides, so this node is the LCA: return it. If only one side reports, pass that report up unchanged. If neither does, pass up null.
| Node | Left report | Right report | Returns |
|---|---|---|---|
| 6 | skipped | skipped | 6 (is a target) |
| 2 | skipped | skipped | 2 (is a target) |
| 5 | 6 | 2 | 5, both sides reported: LCA |
| 0 | null | null | null |
| 8 | null | null | null |
| 1 | null | null | null |
| 3 | 5 | null | 5, passed up |
Why it is correct
The invariant: a non-null return from a subtree means that subtree contains at least one of the targets, and if it contains both, the returned node is their LCA. Check the three cases. A target node returns itself, which is correct for both readings. A node with reports from both sides contains both targets, on different sides, so nothing lower can be an ancestor of both, and this node is: it returns itself, the LCA. A node with one report contains exactly what that side contains, so forwarding the report keeps the statement true.
At the root the subtree is the whole tree, which contains both targets, so the root's return is the LCA. If a problem guarantees both exist, the first node to hear from both sides is the answer.
Why it is fast
Each node is visited at most once and does two comparisons, so O(n) time, and the shortcut stops below targets. Nothing is stored except the recursion stack, O(h). In a binary search tree you can do better: compare the two targets with the node's value and walk down one side, O(h) time with no recursion at all.
How to recognise it in an interview
"Lowest common ancestor", "nearest shared parent", "the node where the paths to p and q split", also "the smallest subtree containing all the deepest leaves". Say: "Each subtree reports whether it holds p or q; the first node hearing from both sides is the LCA." Lowest Common Ancestor of a Binary Tree is the direct form. Lowest Common Ancestor of a Binary Search Tree replaces the reports with value comparisons. Lowest Common Ancestor of a Binary Tree III gives parent pointers, which turns it into walking two chains upward to their meeting point.
02The idea in one line
Return the found node upward; the first node that hears from both sides is the LCA.
Reach for it when: LCA of binary tree, LCA with parent pointers, LCA of deepest leaves.
Cost: O(n) time.
03The walk-through, step by step
The video works one example: LCA of 5 and 1 in [3,5,1,6,2,0,8]. These are its captions in order, so you can follow without the video or check a step you missed.
- Ask each subtree: do you contain p or q?
- Node 3: ask left and right
- Node 5: ask left and right
- Node 6 is one of the targets: return itself without going deeper
- Node 2 is one of the targets: return itself without going deeper
- Node 5 hears from both sides: it is the LCA
- Node 1: ask left and right
- Node 0: ask left and right
- Node 0 hears nothing: pass null up
- Node 8: ask left and right
- Node 8 hears nothing: pass null up
- Node 1 hears nothing: pass null up
- Node 3 hears from one side: pass 5 up
- LCA of 6 and 2 is 5; one post-order pass: O(n)
04Asked at Google
6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.
| Problem | Difficulty | Frequency | Reported |
|---|---|---|---|
| Lowest Common Ancestor of a Binary Tree | Medium | 42 | last 6 months |
| Lowest Common Ancestor of a Binary Search Tree | Medium | 28 | last 6 months |
| Kth Ancestor of a Tree Node | Hard | 28 | last 6 months |
| Lowest Common Ancestor of Deepest Leaves | Medium | 15 | |
| Lowest Common Ancestor of a Binary Tree III | Medium | 15 | |
| Smallest Subtree with all the Deepest Nodes | Medium | 8 |
05Related patterns
Other patterns in Trees: Recursive DFS (post-order fold), Best path through each node, Level-order BFS, Root-to-leaf path carry, Build from traversals, Iterative traversal with a stack, Column / coordinate traversal, Rerooting DP (sum over all roots), Post-order deletion / pruning, Tree as a graph (parent pointers), Tree DP: take or skip this node, Serialize / deserialize by BFS.