Lesson 33 — Trees VI: Lowest Common Ancestor

~25 minutes · Day 38 · tree recursion · Python

Tonight's problem is Lowest Common Ancestor of a Binary Tree. Interviewers like it because the code is short, but the thinking is not: you must trust what each subtree reports back. The win is learning to stop searching the moment the two targets split across the current node.

The invariant

If the two targets are found in different subtrees of a node, you are standing on the answer.

A lowest common ancestor is the deepest node that has both targets below it, counting a node as its own descendant. In this LeetCode problem, both target nodes are present in the tree; your job is to return the node where their paths first meet.

The LCA is the lowest node where the two target paths meet.

The slow way first

The brute force idea is: at every node, ask “does this subtree contain p?” and “does this subtree contain q?”, then keep trying to go lower. That can become O(n^2) in the worst case, because the same subtrees get searched again and again.

def contains(node, target):
    if node is None:
        return False
    return (node == target or
            contains(node.left, target) or
            contains(node.right, target))

It works, but it wastes the most important thing recursion gives you: a return value. Each child can report whether it found nothing, one target, or the final answer.

The one-pass way

Run one DFS. If a subtree finds p or q, it returns that node upward. If a node receives one result from the left child and one result from the right child, the split happened here, so this node is the LCA.

The recursive call does not need parent pointers; it bubbles findings upward until both sides meet.

def lowestCommonAncestor(self, root, p, q):
    if root is None:
        return None                 # this subtree found nothing
    if root == p or root == q:
        return root                 # this subtree found a target
    left = self.lowestCommonAncestor(root.left, p, q)
    right = self.lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root                 # split: current node is LCA
    return left or right            # bubble up what was found

The line if left and right is the invariant becoming code. One target came from each side, so no lower node can contain both.

Transfer: same question, new costume

Variation: suppose one target might be an ancestor of the other. In the tree below, ask for p = 5 and q = 2. What should the call at node 5 return?

      3
     / \
    5   1
   / \
  6   2

Before opening the reveal, predict it out loud: does node 5 wait for both children, or does it return itself immediately?

What the trade buys you

Here h is the tree height. The important upgrade is not clever syntax; it is asking every node for its answer once.

Practice — answer before you scroll past

left = dfs(root.left)
right = dfs(root.right)
if left:
    return left
if right:
    return right
if root == p or root == q:
    return root

Your move (tonight)

Solve Lowest Common Ancestor of a Binary Tree, logging it in your Notion tracker with the cycle — predict → attempt → compare → encode.

1. Predict: name the pattern, state the brute force O(n^2) subtree-check idea, and say the invariant out loud.
2. Attempt: write the recursive return-value version without looking at the final code above.
3. Compare: watch the source below only after your attempt, and find the sentence where your reasoning differs.
4. Encode: write one line in Notion: when left and right both return something, the current node is the answer.