Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Lowest Common Ancestor of a Binary Tree

LeetCode #236Medium
Post-order DFS, bubble a target up — split point wins

Given the root of a binary tree and two nodes p and q, return their lowest common ancestor: the deepest node that has both p and q as descendants (a node may be a descendant of itself).

Asked atAmazonMetaMicrosoft
step 1 / 9
binary tree
6
5
7
2
4
3
0
1
8
call stack ↓
(returned)
Recursive DFS (bubble up)
▸
1lca(node):
2    if node is null: return null
3    if node is p or node is q: return node   // found a target
4    left  = lca(node.left)
5    right = lca(node.right)
6    if left and right: return node           // split → LCA
7    return left or right                     // carry target up
8// answer = lca(root)
state
  • p5
  • q1
  • goaldeepest common ancestor

line 1We want the Lowest Common Ancestor of p = 5 and q = 1: the deepest node that has BOTH as descendants (a node may be its own descendant). Both targets stay highlighted so you can watch us locate them. The trick is one post-order DFS that "bubbles up" a signal: each call returns a target it has seen, and the FIRST node that hears back a non-null from BOTH sides is the answer.