• The number of nodes in the tree is in the range [2, 10⁵]
• -10⁹ <= Node.val <= 10⁹, and all values are unique
• p and q are distinct and both exist in the tree
• A node is considered a descendant of itself

Two nodes, each reachable from the root by exactly one downward route. Follow both routes from the top and they coincide for a while, then split. The last node they share is the lowest common ancestor — everything above it is also common but higher, and after the split neither branch contains both.

That description suggests an obvious method, and it is worth doing first because it is easy to get right: find the root-to-node path for p and for q — the technique from Root to Node Path — then walk the two lists side by side and take the last position where they agree. Correct, two traversals, and O(H) memory for the two lists. In an interview it is a perfectly respectable first answer.

But it stores whole paths in order to use only their divergence point. Can a single walk find that point directly?

Here is the reframe. In Root to Node Path each node returned a boolean, "is the target below me?", and the real output was kept in a shared list. Make the return value richer: instead of whether something was found, return what was found — a node, or null for nothing.

Define the recursion as: return a node from this subtree that is relevant to the answer, or null if this subtree is irrelevant. Then look at what a node sees when both its calls come back:

And the base case does double duty. A null node reports null, obviously. But a node that is p or q reports itself immediately, without even looking below it.

def lca(node, p, q):
    if node is None or node is p or node is q:
        return node                    # null, or "I am a target" — either way, report it
    left  = lca(node.left,  p, q)
    right = lca(node.right, p, q)
    if left and right:
        return node                    # the two targets split here: I am the LCA
    return left or right               # otherwise forward whichever side found something

Four lines, one traversal, no path lists. The work happens after both calls return, so this is a post-order shape — unavoidably, since a node cannot know whether it is the split point until both sides have reported.

The line that deserves scrutiny is the early return at node is p: we stop and report without checking whether q is somewhere below. Does that risk missing a lower ancestor?

No, and the reason is the self-ancestor rule. Suppose q does lie beneath p. Then every common ancestor of p and q is p or one of p's ancestors, and the lowest of those is p itself — exactly what we returned. Suppose q does not lie beneath p. Then p's subtree contains only one target, and reporting p upward simply means "the p-side found something"; some ancestor will eventually pair it with the report from q's side and correctly claim itself. Either way the early return is right, and it saves exploring p's subtree entirely.

Now the same tree with p = 7, q = 4. Node 2 receives 7 from its left and 4 from its right; both non-null, so 2 returns itself. Node 5 gets 2 from the left and null from the right, so it forwards 2. Node 3 gets 2 from the left and null from the right, and forwards it again. Answer: 2. Once a node claims the answer, every ancestor above it is in the one-sided case and simply passes it along untouched — which is exactly why the "lowest" ancestor wins rather than some higher one.

One visit per node in the worst case, constant work each: O(N) time, down from the two passes of the path-comparison method (still O(N), but twice the work and O(H) extra storage). Space here is just the recursion stack, O(H).

The move worth stealing is the upgrade from a boolean return to an informative one. When a recursion is about to answer "did I find it?", ask whether returning the thing itself — or the best candidate from this subtree — would let the parent decide something it otherwise could not. Here, "return a relevant node" let each parent distinguish the split point from a pass-through with a single null check, and that one decision is the entire algorithm. The same upgrade pays off in All Nodes Distance K, where the recursion returns a distance rather than a flag, and in Binary Tree Maximum Path Sum, where it returns the best downward sum.