DSA Tracker

Visualize

Lowest Common Ancestor of a Binary Tree

time O(n)space O(h)

A postorder search asks each subtree "did you find p, did you find q?" before its parent decides anything. A node becomes the answer the instant both children report a find on different sides — that convergence point is, by definition, the lowest node with both underneath it.

Details

Animated on: Given the root of a binary tree and two nodes p and q, return the lowest common ancestor of the two nodes — the deepest node that has both p and q as descendants.

Problem:Lowest Common Ancestor of a Binary TreeMedium

Binary Trees

step 1 / 14

6
5
7
2
4
3
0
1
8

Call stack

lca(3)

Call lca(3). Not null and not one of the targets, so we still need both children's answers before we know anything about this node.

Pseudocode
1FUNCTION lca(node, p, q):
2  IF node = null 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 != null AND right != null:
7    RETURN node
8  IF left != null:
9    RETURN left
10  RETURN right

← / → step · space play · Home restart

Every step in words

Show all 14 steps
  1. Call lca(3). Not null and not one of the targets, so we still need both children's answers before we know anything about this node.
  2. Call lca(5). Not null and not one of the targets, so we still need both children's answers before we know anything about this node.
  3. 6 has no children, so neither 7 nor 4 live under it — it returns null with nothing found.
  4. Call lca(2). Not null and not one of the targets, so we still need both children's answers before we know anything about this node.
  5. Call lca(7). Node 7 IS one of the targets (p) — base case, return it immediately without looking further down this branch.
  6. Call lca(4). Node 4 IS one of the targets (q) — base case, return it immediately without looking further down this branch.
  7. Back at 2: the LEFT subtree found 7 and the RIGHT subtree found 4 — one target came up each side. That makes 2 the lowest common ancestor of this subtree.
  8. Back at 5: only the right side reported anything (2). Nothing was found on the left, so 2 is passed straight up through 5.
  9. Call lca(1). Not null and not one of the targets, so we still need both children's answers before we know anything about this node.
  10. 0 has no children, so neither 7 nor 4 live under it — it returns null with nothing found.
  11. 8 has no children, so neither 7 nor 4 live under it — it returns null with nothing found.
  12. Back at 1: neither side found 7 or 4. This whole subtree returns null.
  13. Back at 3: only the left side reported anything (2). Nothing was found on the right, so 2 is passed straight up through 3.
  14. lca(7, 4) = 2. Every node was visited at most once (some — the trivial leaves — were collapsed into one step above), so this runs in O(n) time and O(h) space for the recursion stack.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Lowest Common Ancestor of a Binary Tree in the editorAll Binary Trees problemsBack to roadmap