STEP 13 · BINARY TREES · REPORT WHAT YOU FOUND BELOW · MEDIUM

Lowest Common Ancestor of a Binary Tree

WHAT IT SAYS

Given a binary tree and two nodes p and q, find the deepest node that has both of them in its subtree.

WHAT IT'S REALLY ASKING

"Walk down from the root toward both targets at once. For a while they pull you the same way — then comes a node where they split into different children, and every step past it abandons one of them. The LCA is not something you search FOR; it is the point where the two searches part company."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Record both root-to-target paths, then compare

O(n) time, O(h) space for two stored paths, up to three traversals

Find the path from the root to p and store it. Find the path from the root to q and store it. Walk the two lists in parallel from the front; the last node where they still agree is the answer.

WHERE THE WORK IS WASTED — The two path-finding searches walk the same tree and, near the root, the same nodes — the shared prefix of the two paths is traversed twice and then compared a third time, element by element, to rediscover that it is shared. But the sharing was knowable DURING a single walk: at every node, a subtree either contains p, contains q, contains both, or contains neither, and one traversal can learn which. Materialising the paths defers to a post-processing step a question the recursion could have answered on the way up.

KEY OBSERVATION — THE UNLOCKlink

The LCA is where the two reports first meet.

Design the recursion around one question, asked of every subtree: what do you contain? Give each call this contract — searching a subtree returns p if it contains p (and not q), q if it contains q (and not p), the LCA if it contains both, and null if it contains neither. If that contract holds for the children, watch what the parent can conclude. Ask both children. If both come back non-null, then p is in one subtree and q is in the other — they are in DIFFERENT children, so this node is the deepest point containing both. This node is the LCA, and the contract says: return it. Every ancestor above will see it come up from one side and null from the other, and by the contract's other clause will pass it along unchanged — which is exactly right, because the answer is already found. If exactly one child reports non-null, everything interesting lives on that side; forward its report upward untouched. If both report null, report null. One clause remains: what if the current node IS p or q? Return it immediately, without even looking below — and this is not laziness but correctness. If the other target is somewhere underneath, then this node is an ancestor of both, hence the LCA, and returning it is the right answer. If the other target is elsewhere, some ancestor will see this report on one side and the other target's report on the other side, and that ancestor will correctly crown itself. Either way, returning self is safe — the case analysis closes. The elegance worth internalising: the function never explicitly computes 'the LCA'. It only ever reports what it found, and the LCA emerges as the unique node where two non-null reports collide. The answer is a property of how information flows upward, not of any search step.

One post-order walk with the found-below contract

O(n) time — every node asked once — O(h) stack space

If the node is null or equals p or q, return it. Recurse into both children. If both returns are non-null, return the current node. Otherwise return whichever child's report is non-null (or null). The value that surfaces at the root is the LCA.

WHAT YOU TRADED — This solution assumes both targets exist in the tree — if q might be absent, the recursion happily returns p as a false LCA, and you must either verify existence first or fatten the return value into (node, foundP, foundQ). Note also what having no BST ordering costs: with a BST, comparisons steer you down one path in O(h) without visiting the rest; here every subtree must be asked. The transferable lesson: when the answer is defined by where two searches diverge, run them as one traversal and let each subtree report upward what it found.

WATCH THE IDEA RUN

CALL STACK

stack empty — every branch explored

targets p = 6, q = 4

LCA not yet

The brute force finds the two root-to-node paths and compares them. But nobody needs a path — watch what a single post-order pass can carry instead.

step 1 / 20

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Reports Collide at the Answer

YOU'LL SEE IT AGAIN WHEN

The answer is defined relative to two (or more) marked elements — their meeting point, split point, or shared ancestor.
Each subtree's relationship to the marked elements is summarisable in a small enum: neither, one, the other, both.
The answer node is characterised by a condition on its children's summaries (both non-null), so it identifies itself during the upward pass.

SAME BLUEPRINT, DIFFERENT PROBLEM

LCA of a Binary Search Tree (ordering replaces the search)LCA of Deepest LeavesDistance Between Two Nodes in a BTSmallest Subtree with All the Deepest Nodes

The bar isn't "solved it once." It's "could rebuild it from the observation."