Lowest Common Ancestor of a Binary Tree (LeetCode 236)

The problem

You get the root of a binary tree (not a BST) and two values p and q that are both in the tree. Return their lowest common ancestor: the deepest node that has both in its subtree. A node counts as its own ancestor.

Input:  root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

            3
          /   \
         5     1
        / \   / \
       6   2 0   8
          / \
         7   4

Output: 3

5 is in 3’s left subtree and 1 is in its right, so the root is the deepest node above both.

How to think about it

Start with brute force. Find the path from the root to p and the path to q (two DFS runs, storing each path), then walk them together until they diverge. That’s O(n) time, but you need extra memory for the paths and two separate searches.

The key insight: let each subtree report what it found. Write a DFS that returns a target node if its subtree contains one, else None. Now look at a node after both children report:

• Both sides found something: one target is on the left and one is on the right, so this node is where they meet. It’s the LCA.
• Only one side found something: pass that up unchanged. It’s either one target still looking for its partner, or an LCA already found lower down.

Return early when you hit a target. If the current node is p or q, return it without searching below. If the other target is underneath, this node is the LCA anyway, and nothing above will see two reports and override it.

Which pattern is this? Tree DFS where results bubble up and are combined at each node. The tell is “ancestor” with no ordering to use, so you must search both sides.

Approach

1. If the node is empty, or its value is p or q, return the node.
2. Recurse into the left and right subtrees.
3. If both return a node, return the current node: it’s the split point.
4. Otherwise return whichever side is non-empty (or None).

Solution

def lca(root, p, q):
    if not root or root.val == p or root.val == q: return root   # empty, or found a target
    l = lca(root.left, p, q); r = lca(root.right, p, q)
    if l and r: return root                                       # one target on each side
    return l or r                                                 # bubble up whatever was found
# lca(tree[3,5,1,6,2,0,8], 5, 1).val -> 3

Here p and q are values and the function returns a node. On LeetCode they are nodes, so compare with root == p.

Dry run

The example (p = 5, q = 1) finishes in one step: both children of 3 are targets, so 3 sees l = 5, r = 1 and returns 3. A deeper query shows the bubbling better. With p = 7, q = 6, nodes report in this order:

The answer is 5.

Complexity

• Time: O(n). Each node is visited at most once.
• Space: O(h). The recursion stack goes as deep as the tree height: O(log n) balanced, O(n) skewed.

Edge cases and pitfalls

• One target is an ancestor of the other (p = 5, q = 4): the DFS stops at 5 and returns it, which is correct.
• Both targets must exist. This code assumes they do. If one might be missing, it returns the other one as the “LCA”. Count found targets separately if the problem allows that.
• Duplicate values break value-based comparison. LeetCode guarantees unique values; with duplicates, compare node identity.
• Don’t use the BST trick here. Comparing values to pick a side only works when the tree is ordered.

Related problems

• Lowest Common Ancestor of a BST (LeetCode 235): the ordered version, solved in O(h) with no recursion.
• Diameter of Binary Tree (LeetCode 543): another post-order DFS that decides at the node where two branches meet.
• Cousins in Binary Tree (LeetCode 993): another question about how two nodes relate in a tree.