Where two branches meet
Find the lowest common ancestor of two nodes in a binary tree, by asking each subtree whether it contains either node and noticing the first node that hears yes from both sides. About 18 minutes.
Each call reports what it found
The lowest common ancestor of two nodes is the lowest node that has both of them in its subtree, counting a node as being in its own subtree. In a tree with no ordering, you cannot decide by comparing values, so search.
Let each call return a node or nothing. It returns nothing for an empty tree. It returns the node itself if the node is one of the two targets. Otherwise it asks both children.
if node is None:
return None
if node.val == target:
return node # found: report up- left
- 5
From the root 3, going left we reach 5, one of the targets. It reports itself without looking below.
Both sides said yes
If the left side and the right side both report something, one target was found on each side, so this node is where the paths split. It is the answer, and it is reported upward.
If only one side reports, pass that report up: it is either a lone target, or the answer already found lower down. If neither reports, there is nothing here.
both = node.left and node.right # a node with two children
A node gets a report from its left child only. What does it do?
- APasses that report up unchanged
- BDeclares itself the answer
- CReports nothing
Show the answer
Passes that report up unchanged. The left subtree holds a lone target or the answer already found lower down.
Lowest common ancestor of a binary tree
Given the root of a binary tree whose node values are all different, and two values p and q that both appear in the tree, return the value of the lowest common ancestor of the nodes holding p and q. The lowest common ancestor is the lowest node that has both as descendants, where a node may be a descendant of itself.
root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 4 → 5
2 ≤ number of nodes ≤ 5,000 · all values are different · p and q are different and both in the tree