What is the Lowest Common Ancestor?
The Lowest Common Ancestor (LCA) of two nodes p and q in a tree is the lowest (i.e. deepest) node that has both p and q as descendants. Note that a node can be a descendant of itself.
Visual Example
Node 5 is the deepest node that is an ancestor to both 6 and 2.
Algorithm Strategy
1. Search Down
Start at the root and recursively search the left and right subtrees. If you hit a null node, return null. If the current node matches either p or q, return the current node.
2. Bubble Up
As recursion unwinds, pass the found nodes back up the tree. At any given node, look at what was returned from its left and right children.
3. Evaluate
If both left and right return a non-null node, then the current node is the LCA! Otherwise, return whichever child is non-null.
Complexity Analysis
Where N is the number of nodes, and H is the height of the tree (recursion stack).
Time Complexity: O(N)
Key Takeaways
- LCA naturally relies on a bottom-up (post-order) traversal. You need information from children before deciding if the current node is the LCA.
- If a node is an ancestor of the other (e.g., p is ancestor of q), the algorithm returns p directly without needing to explore its subtree.