46. Lowest Common Ancestor

Problem

Model configs at a research lab are organized as an inheritance tree: a base config sits at the root, and each child node overrides some subset of its parent's fields for a more specific use case (e.g. a family config overriding a base, and a per- experiment config overriding the family). Given two specific config nodes, find their lowest common ancestor — the most specific config both ultimately inherit from — so a diff tool can show only the fields that actually differ between the two, relative to their shared base.

p and q are guaranteed to exist in the tree and are passed as actual node references (not values). A node counts as its own ancestor.

Source: src/46_lowest_common_ancestor.py

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

def lowest_common_ancestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode: ...

>>> base = TreeNode("base")
>>> base.left = TreeNode("vision")
>>> base.left.left = TreeNode("vit-s")
>>> base.left.right = TreeNode("vit-l")
>>> lowest_common_ancestor(base, base.left.left, base.left.right).val
'vision'

Step-by-Step Approach

1. Recognize this needs at most one pass over the tree — no need to compute paths to p and q separately and compare them.
2. Write a recursive function that, given a node, returns that node itself if it IS p, IS q, or is None — these are the base cases where no further search below this node is needed.
3. Otherwise, recurse into both children and collect what each subtree search returns.
4. If BOTH the left and right recursive calls return something non-None, that means p and q were found in different subtrees — which makes the current node exactly their lowest common ancestor.
5. If only one side returned non-None, propagate that result upward unchanged — it means both targets (or the one found so far) live entirely within that subtree, so the answer must come from further up, not from this node.
6. The value returned by the outermost call is the LCA.

The key insight is that a single post-order traversal can find the LCA in one shot: a node "becomes" the answer at the exact moment its two child recursions report finding p and q on opposite sides — before that point, the search just percolates whichever single target it's found upward without commitment.

Reference solution

def lowest_common_ancestor(
    root: "TreeNode | None", p: "TreeNode", q: "TreeNode"
) -> "TreeNode | None":
    # single post-order pass, O(n) time, O(h) space: a node is the LCA the
    # moment p and q are found on different sides of it (or it IS one of them)
    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 is not None and right is not None:
        return root  # p and q split across both subtrees -> root is the LCA
    return left if left is not None else right  # both live on one side

Key Functions & Tricks

• Identity check (is, not ==) — p and q are node references, so identity comparison is both correct and avoids relying on values being unique.
• Early return on hitting p, q, or None — collapses three base cases into one line.
• "Both sides non-None" test — the single condition that identifies the split point, i.e. the LCA itself.
• Propagating a single non-None result upward — lets a node found deep in one subtree "bubble up" through ancestors until it either meets its counterpart or reaches the true LCA.
• Post-order structure (children visited before the parent's own logic runs) — required so a parent can inspect what both of its children already discovered.

How to Recognize This Pattern