Use the order to find the meeting point
Find the lowest common ancestor in a search tree by walking down from the root and stopping where the two values split to different sides. About 12 minutes.
Both smaller, both larger
A search tree keeps smaller values on the left and larger ones on the right. Stand at a node and look at your two target values.
If both are smaller than the node, both are in the left subtree, so move left. If both are larger, move right. There is no need to look at the other side at all.
if x < node.val:
node = node.left
else:
node = node.right- values
- 3 and 5
At 6, both 3 and 5 are smaller. Go left.
The split point
When one target is smaller than the node and the other is larger, they lie on different sides, so this node is the lowest node that has both below it. If the node equals one of the targets, it is an ancestor of the other, and is also the answer.
Stop at the first node where neither of the two moves applies, and return its value. This works with a loop, with no recursion.
both_left = p < node.val and q < node.val both_right = p > node.val and q > node.val split = not both_left and not both_right
At the node 7, the targets are 7 and 12. What do you do?
- AStop: the node equals one target, so 7 is the answer
- BGo right, because 12 is larger
- CGo left
Show the answer
Stop: the node equals one target, so 7 is the answer. Node 7 is an ancestor of every node in its right subtree, including 12.
Lowest common ancestor of a search tree
Given the root of a binary search tree (smaller values on the left, larger on the right, all values different) and two values p and q that both appear in it, return the value of the lowest common ancestor of the nodes holding p and q. A node may be a descendant of itself.
root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 3, q = 5 → 4
2 ≤ number of nodes ≤ 10,000 · it is a valid binary search tree · p and q are different and both in the tree