Lowest Common Ancestor of a Binary Tree — Solution

Problem

Given a binary tree and two nodes p and q, find their lowest common ancestor — the deepest node that has both p and q as descendants, where a node is considered a descendant of itself.

[3,5,1,6,2,0,8,null,null,7,4]

• Input: p = 5, q = 1
• Output: 3
• Explanation: Node 3 is the deepest node that has both 5 and 1 as descendants.

Counter-example: If p = 5 and q = 4, the LCA is 5 itself — because 5 is an ancestor of 4, and a node counts as its own ancestor.

Intuition

At each node during a DFS, ask two questions: does p or q appear somewhere in my left subtree? Does it appear in my right? If the answer is yes to both, then the current node sits exactly at the split point — it's the LCA. If only one subtree contains a target, the answer is deeper on that side, so we propagate that result upward. The recursion naturally bubbles the right answer all the way to the root.

Solution — Recursive DFS

Search both subtrees simultaneously. The moment we find a target node, return it to the caller. The first node that sees non-null results coming back from both children is the LCA.

1. If the current node is null, return null — nothing here.
2. If the current node is p or q, return it immediately; the other target may be in its subtree, but the parent will handle that.
3. Recurse into the left subtree; store the result.
4. Recurse into the right subtree; store the result.
5. If both sides returned something non-null, the current node is the LCA — return it.
6. Otherwise, return whichever side found something (or null if neither did).

1class Solution:
2    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
3        if root is None:
4            return None
5        if root == p or root == q:
6            return root  # found a target; parent decides if this is the LCA
7
8        left_result = self.lowestCommonAncestor(root.left, p, q)
9        right_result = self.lowestCommonAncestor(root.right, p, q)
10
11        if left_result and right_result:
12            return root  # p and q are on opposite sides, so this node is the LCA
13        return left_result or right_result  # propagate whichever side found a target

Time: O(n) — every node is visited exactly once in the worst case.
Space: O(h) — the recursion stack grows as deep as the tree height; O(log n) for balanced trees, O(n) for a skewed tree.

Complexity Summary

Common Mistakes

• Searching the subtree after finding a target — returning immediately when root == p or root == q is intentional. If the other node is a descendant, the parent will receive only one non-null result from its left or right call and correctly propagate it; no extra subtree search is needed.
• Confusing this with the BST variant — in lowest-common-ancestor-of-a-binary-search-tree you can compare values and navigate directionally; here there is no ordering, so both subtrees must always be searched.
• Thinking the early return for root == p is wrong when q is below p — it is correct. The problem guarantees both nodes are in the tree, and since p is its own ancestor, returning p when we find it means the parent will propagate 5 upward, and the other subtree will return null, so the final answer is 5. Trace it through the example with p=5, q=4 to convince yourself.
• Using value equality instead of reference equality — node identity (root == p) is what matters, not root.val == p.val. Two distinct nodes could share a value in a general binary tree, though the standard problem guarantees unique values; stick to reference comparison to be safe.
• Forgetting the null base case — the recursion calls itself on null children of leaf nodes. Without the if root is None: return None guard, every leaf's children would crash.

Related Problems

• lowest-common-ancestor-of-a-binary-search-tree — same problem but the BST ordering lets you skip one subtree at each step
• binary-tree-maximum-path-sum — same bottom-up DFS pattern where each node aggregates results from both children
• diameter-of-binary-tree — bottom-up DFS combining left and right depths at each node
• path-sum — DFS on a tree tracking accumulated state as we descend
• balanced-binary-tree — bottom-up DFS where each node returns height information to detect imbalance