Lowest Common Ancestor of a Binary Tree

Medium#236tree nodes

You get the root of a binary tree and two different nodes of it, p and q. Find their lowest common ancestor: the deepest node that has both p and q in its subtree; a node counts as part of its own subtree. Our tree: 5 with children 8 and 2; 8 has children 4 and 1; 1 has a left child 7; 2 has a right child 9. p = 4, q = 7 — the answer is 8.

236 Lowest Common Ancestor of a Binary TreeWalkthrough · 1×

Example: find the lowest node that has both 4 and 7 below it: each call returns p or q if it found one, and the first node that hears back from both sides is the answer.

p = 4, q = 7nonenonenonenonenonenonenonenone5824179call stacktop on the right5
not visitedp or q, not reached yetwaiting on the call stackcurrent callreturned a node, ↑ which onereturned none: neither p nor q below

5 is not none, and it is neither p nor q: search both of its subtrees

01/47
restart · back · play · step
Speed
1function lca(node, p, q):
2 if node is none or node == p or node == q:
3 return node
4 left = lca(node.left, p, q)
5 right = lca(node.right, p, q)
6 if left is not none and right is not none:
7 return node // p and q split here
8 if left is not none:
9 return left
10 return right
state
p
4
q
7
node
5
left
–
right
–
click a step to go back

← → step · space play/pause

Why it works

  1. A call returns none exactly when its subtree holds neither p nor q, so at every node left and right say which sides hold them.
  2. If both sides found something, p and q are split between them, and no node lower down holds both: this node is the lowest. Every call above it hears back from one side only and just passes it up.
  3. If p were above q, the call on p would return p at once without looking below, and that is right: q is somewhere under p, so p is the answer.

Complexity

Time O(n): each node is visited at most once. Memory O(h), where h is the height of the tree: the call stack holds one path.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.