Lowest Common Ancestor: The Bubble Up Argument

This one is a Medium-rated classic reported from Meta, Amazon, LinkedIn interviews: "Lowest Common Ancestor of a Binary Tree". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Tree DFS pattern on sight. Part 9 of 11 in the Tree DFS arc.

The Problem

Given a binary tree (not a BST) and two nodes p and q guaranteed present, return their lowest common ancestor — the deepest node having both as descendants, where a node may be its own descendant. A Meta perennial with a recursion whose correctness argument is the interview.

Input:  root = [3, 5, 1, 6, 2, 0, 8], p = 5, q = 1
Output: 3
For p = 5, q = 4 (4 under 5), the answer is 5 — a node can be its own ancestor.

Recognizing the Tree DFS Pattern

Depth-first search commits to one branch before trying siblings — recursion (or an explicit stack) whose call structure mirrors the tree itself. Its natural questions are about paths (root to leaf), subtree properties (computed bottom-up from children), and exhaustive exploration (islands, connected regions). The recurring design decision is what each recursive call returns versus what it accumulates in shared state.

Post-order information flow: each subtree reports what it contains (p, q, neither, or the LCA already found), and the first node where both sides report something is the split point. Bottom-up aggregation of where things are is a DFS-return-value design problem.

The Approach

Base: None returns None; a node equal to p or q returns itself. Recurse both sides. Both non-None means p and q split here — return this node. One non-None propagates upward — it is either the LCA (both targets below it) or a lone target awaiting its partner.

The subtle case the argument must cover: when one target is the other's ancestor, the ancestor returns itself before exploring deeper, and the guarantee that both exist makes that early return sound. Rehearse saying it.

Python Solution

class TreeNode:
    def __init__(self, val: int = 0, left: "TreeNode | None" = None,
                 right: "TreeNode | None" = None):
        self.val = val
        self.left = left
        self.right = right


def lowest_common_ancestor(
    root: TreeNode | None, p: TreeNode, q: TreeNode
) -> TreeNode | None:
    """Deepest node with both p and q as descendants."""
    if root is None or root is p or root is q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        return root                        # p and q split at this node
    return left or right                   # bubble the non-empty side up

Complexity

• Time: O(n) — single post-order traversal
• Space: O(h) — recursion stack

Interview Tips and Follow-Ups

• If existence is not guaranteed, this returns a wrong answer silently (a lone found node bubbles to the root) — the fix counts found targets. Interviewers love this probe.
• BST version: walk from the root using value comparisons — O(h) with no recursion. Know both, and which applies.
• With parent pointers it becomes intersection of two upward paths — the linked list intersection trick from the fast-slow arc, reused.

That wraps part 9 of the Tree DFS arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.