Lowest Common Ancestor of Binary Tree
Lowest Common Ancestor of Binary Tree: find the lowest node that has both p and q in its subtree (a node counts as its own ancestor).
- The number of nodes in the tree is in the range [2, 10⁵].
- -10⁹ <= Node.val <= 10⁹
- All Node.val are unique.
- p != q
- p and q will exist in the tree.
Intuition
The lowest common ancestor of a binary tree is the deepest node having both p and q somewhere in its subtree, where a node counts as its own ancestor. Unlike the BST version, there is no ordering to exploit — you cannot tell which subtree holds a target without looking inside it.
So the recursion has to ask both sides, and the elegance is in what each call returns. Rather than returning a boolean and combining flags, have each call return the most useful node it found below:
- Null if neither target is in this subtree.
- p or q if exactly one was found and no split has happened yet.
- The lowest common ancestor once a split has been detected.
Those three cases collapse into one rule. If both child calls return something non-null, the two targets lie in different subtrees, so the current node is the split point and therefore the answer. If only one child returns something, pass that result upward unchanged.
The single-return convention is what makes this work without extra state. Once an ancestor is found, it keeps being propagated up by the "only one side answered" branch, arriving at the root intact.
The case that looks like it needs special handling — p being an ancestor of q — does not. The recursion stops at p and returns it, the other side returns null, so p propagates up as the answer, which is correct.
This is the template for "ask both subtrees, then decide here" — post-order recursion. You'll reach for it whenever a node's answer needs results from below rather than context from above. The return value does double duty: it means found one of the targets on the way up, and found the LCA once both sides report back. When a single recursive function has to carry two meanings like that, post-order is usually why it works.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(h) space.
Return a node, not a boolean
Each call returns the most significant node found in its subtree: null, one of the targets, or the answer once known. This single convention removes the need for separate found-flags and is what keeps the function to a few lines.
Stop at null or at a target
An empty subtree returns null. A node equal to p or q returns itself immediately, without searching below it — anything deeper cannot be a lower common ancestor than a target itself.
Recurse into both subtrees
With no ordering to exploit, both sides must be searched. This is the essential difference from the BST version, and it is why the cost is O(n) here rather than O(h).
A non-null on both sides means this is the answer
If the left and right calls both return something, p and q sit in different subtrees, so the current node is the deepest node containing both. Return the node itself — and because the parent will see only one non-null side, this answer propagates upward untouched.
Otherwise forward the single result
If only one side is non-null, return it. That value is either the already-found ancestor being carried up, or a lone target still looking for its partner — both need to travel to the caller, and the same line handles both.
Note that the ancestor case needs no special code
When p is an ancestor of q, the recursion returns p on reaching it and null from the other side, so p becomes the answer. This is correct by the problem's definition and is the case people wrongly add extra handling for.
Cost of the search
Every node is visited once in the worst case, giving O(n) time — unavoidable without ordering information. Space is O(h) for the recursion stack, which is O(n) on a degenerate tree.
Solution & live demo
Common pitfalls
Comparing values instead of identity
if root.val == p.val or root.val == q.val:
if root is p or root is q:
The problem hands you node references, and general binary trees may repeat values — matching on val can latch onto a different node that merely looks the same. Identity is what was actually asked about.
Returning early when only one side is non-null
left = self.lowestCommonAncestor(root.left, p, q) if left: return left
left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) if left and right: return root
Short-circuiting skips the right subtree entirely, so the case where the two targets are split across the children — the only case that makes the current node the LCA — is never detected. You'd return the first target found instead of the ancestor. Both sides must be evaluated before deciding.
Checking for the targets after recursing
left = ... right = ... if root is p or root is q: return root
if not root or root is p or root is q:
return rootWhen one target is an ancestor of the other, the answer is the higher node — and stopping there is what produces it. Recursing first lets the deeper target be returned past its own ancestor.
Edge cases
Recursion stops at p without exploring below — p returns as its own LCA, correct by the definition.
Only that child returns non-None; the answer bubbles from within it.