The problem
Given a binary tree (no ordering) and two nodes p and q, return their lowest common ancestor — the deepest node having both as descendants (a node counts as its own descendant).
Stuck? Reveal hints one at a time
How to approach it
- 1Recurse: lca(node) returns null if the subtree has neither target, or a non-null "evidence" node.
- 2Base case: node is null, p, or q → return node.
- 3Recurse left and right. If both return non-null, the current node separates p and q → it is the LCA.
- 4If only one side is non-null, pass that result up.
Key insight
The first node where the two searches "meet" — both sides non-null — is by construction the deepest separator, which is exactly the LCA.
The solution
Watch out for
- This relies on both nodes existing in the tree — if one may be absent, you must verify separately.
- An ancestor can be one of p/q itself: returning early at root === p is correct, not a bug.