236 · Lowest Common Ancestor of a Binary Tree

Six lines that hide a real proof. Returning a non-null from both sides means this node is the split point; returning the node itself on a match is correct even when one target is an ancestor of the other. Be able to say why — that second sentence is the interview question.

1 — The problem

Given two nodes p and q, both guaranteed present, find their lowest common ancestor — the deepest node having both as descendants, where a node counts as a descendant of itself.

The recursion returns a TreeNode, and the trick is that the returned value means two different things depending on what has been found:

The whole algorithm is then: if both children report a find, I am the split point. If only one does, pass its report upward. If neither, report nothing.

2 — Finding the split point

Targets 6 and 4. Watch node 5: it gets a non-null from its left (6) and a non-null from its right (4, relayed up through 2), which is the signal that the two targets are in different subtrees — so 5 is the answer.

Node 1 and its whole subtree return null — they contain neither target — so at the root the rule "only one side reported" fires and 5 passes through untouched. Once the answer exists, every ancestor is a relay.

2.1 Why line 2 is correct when one target is above the other

This is the part worth rehearsing. Suppose p = 5 and q = 4, so p is an ancestor of q and the answer is 5 itself.

Line 2 returns node 5 the moment the recursion touches it, without ever descending to look for 4. That looks like a bug — the code did not verify that q is below. It is correct anyway, and here is the argument:

• q is guaranteed to exist somewhere in the tree.
• If q is inside 5's subtree, then 5 is a common ancestor of both, and no node deeper than 5 can contain p = 5 — so 5 is the lowest. Correct.
• If q is outside 5's subtree, then some ancestor of 5 sees a non-null from the 5 side and a non-null from the q side, and that node returns itself. The early return of 5 was just a report of "p is down here", exactly the report that ancestor needed. Also correct.

Both branches of the argument work because the return value is overloaded: it means "the answer" when both were found and "a sighting" otherwise, and the caller can tell them apart from context it already has. Drop the guarantee that both nodes exist and this breaks — the code would report a lone p as the LCA. Handling absent targets needs a second piece of information travelling up, which is a strictly harder problem.

2.2 The other LCA shapes

3 — Complexity and edge cases

• Time O(n), space O(h). Every node is visited at most once; there is no short-circuit, because both subtrees must be interrogated before the split can be detected.
• One target is an ancestor of the other: the answer is the ancestor, delivered by line 2 — see above.
• p == q: the answer is that node, again by line 2.
• Targets in completely separate subtrees: the split point is found at their deepest common ancestor, which may be the root.
• Comparison by identity, not value: nd == p, not nd.val == p.val. LeetCode promises unique values here so both work, but the identity comparison is the one that survives duplicates.
• Common bug: returning L unconditionally on line 6 instead of "L if non-null else R". Half the tree's findings get dropped.
• Common bug: testing nd == p || nd == q after recursing. It still works, but it costs a full subtree walk in the ancestor case and obscures why the early return is legitimate.

4 — Reference implementation

public TreeNode lowestCommonAncestor(TreeNode nd, TreeNode p, TreeNode q) {
    if (nd == null || nd == p || nd == q) return nd;   // found, or nothing here
    TreeNode L = lowestCommonAncestor(nd.left,  p, q);
    TreeNode R = lowestCommonAncestor(nd.right, p, q);
    if (L != null && R != null) return nd;         // split point — this is the LCA
    return L != null ? L : R;                    // relay whichever side reported
}