Lowest Common Ancestor of a Binary Tree

Problem

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

Examples

The brute-force approach

For each node, find the path from root to p and the path from root to q. Find the deepest node common to both paths.

def find_path(root, target, path):
    if not root: return False
    path.append(root)
    if root == target: return True
    if find_path(root.left, target, path) or find_path(root.right, target, path):
        return True
    path.pop()
    return False

path_p, path_q = [], []
find_path(root, p, path_p)
find_path(root, q, path_q)
# Find last common element
lca = None
for a, b in zip(path_p, path_q):
    if a == b: lca = a
return lca

O(n) but with two separate DFS passes and O(n) space for paths. The recursive single-pass approach below is cleaner.

Spotting the pattern

This is a Tree Traversal problem. The key question to ask yourself:

If left subtree DFS returns node A and right subtree DFS returns node B (both non-null), what does that tell you about the LCA?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.