Pattern visualizer
Lowest Common Ancestor of Binary Tree
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. 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..
Binary Trees
time O(n)space O(h)step 1 / 14
6
5
7
2
4
3
0
1
8
Call stack
lca(3)
line 2
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 node4 left <- lca(node.left, p, q)5 right <- lca(node.right, p, q)6 IF left != null AND right != null:7 RETURN node8 IF left != null:9 RETURN left10 RETURN right
← / → step · space play · Home restart