LC 236 · Medium · Post-order · report findings upward
Lowest Common Ancestor of a Binary Tree
Two nodes, and a question about where their paths join.
Recognise it
Before any code, what in the question tells you this is the pattern?
Two nodes and a question about where they meet, join, or diverge. More broadly, any problem where a node decides something based on what was found in each subtree rather than on its own value.
The brute force
Always have this one ready. It is the honest starting point, and it is what the real solution improves on.
Find the root-to-node path for each target, then walk the two paths from the start and return the last node they have in common.
O(n) time and O(h) space for the two paths.
This is a perfectly good solution and is easier to explain than the recursive one. It is also two passes and needs a path-finding helper that itself has a fiddly base case. The recursive version does the same work in one pass with no auxiliary structure, and understanding it teaches the pattern of reporting findings upward, which several harder problems need.
The approach
The idea in plain language, before it becomes syntax.
Turn the question around. Instead of asking where the paths meet, ask each subtree a simpler question: did you contain either target? Let the answer travel back up the tree.
Now the logic at a node is short. If both children report a find, then one target is below the left and the other below the right, so this node is where they join and it is the answer. If only one child reports, both targets are on that side, so pass its report upward unchanged. If neither reports, this subtree is irrelevant and reports nothing.
The base case does double duty and that is the elegant part. Returning the node itself when it matches means the same value serves as "I found one" and as "here is the answer". It also silently handles the case where one target is an ancestor of the other: the search stops at the ancestor and reports it, which is correct.
The algorithm
The same idea again, as steps you could follow with a pencil.
The solution
Now the code, and why each decision in it is the way it is.
def lowestCommonAncestor(root, p, q):
if root is None or root is p or root is q:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left and right: # found on both sides, so this node is the meeting point
return root
return left or right # one side, or neither: pass the report upThe first node to receive reports from both sides is necessarily the lowest such node, because any node above it receives only one combined report. That is the whole correctness argument, and it is worth being able to state in a sentence.
The Python <code>left or right</code> and the Java ternary do the same thing: return whichever side reported, or null if neither did. Reading it as "pass the report up" rather than as a boolean trick makes the code easier to reconstruct later.
This assumes both nodes are actually present. If they might not be, returning a node no longer proves both were found, and you need a pair of flags alongside the walk. Interviewers often add this as the follow-up, so it is worth naming the assumption before they do.
Where people slip
- The base case returns the node itself when it matches, not
true. Returning a node is what lets the same value serve as both "found it" and "here is the answer". - A node that is an ancestor of the other is still the answer. The base case handles this for free by returning early, which is why there is no special case for it.
- This assumes both nodes exist in the tree. If they might not, the same walk needs a pair of flags, because a lone match would otherwise be reported as the answer.
Your notes
What tripped you up here? Write it in your own words.