Lowest Common Ancestor of a Binary Search Tree
In a plain binary tree you'd have to search both subtrees and merge results. A BST's total ordering removes that: comparing p and q to the current node's value alone tells you which way the split point lies, so the search only ever walks straight down.
Details
Animated on: Given the root of a BST and two of its node values, p = 3 and q = 5, find their lowest common ancestor.
Problem:Lowest Common Ancestor of a Binary Search TreeMedium
Pattern:Binary Search Tree Problems
BST
step 1 / 8
0
2
3
4
5
6
7
8
9
Find the lowest common ancestor of p = 3 and q = 5. A BST's ordering means we can walk down from the root instead of searching both subtrees.
Pseudocode
1FUNCTION lowestCommonAncestor(root, p, q):2 cur <- root3 WHILE cur != null:4 IF p < cur.val AND q < cur.val:5 cur <- cur.left6 ELSE IF p > cur.val AND q > cur.val:7 cur <- cur.right8 ELSE:9 RETURN cur10 RETURN null11END FUNCTION
← / → step · space play · Home restart
Every step in words
Show all 8 steps
- Find the lowest common ancestor of p = 3 and q = 5. A BST's ordering means we can walk down from the root instead of searching both subtrees.
- p = 3 and q = 5 sit here in the tree. We never need to find them by searching — we just compare their VALUES to whatever node we're standing on.
- At node 6: compare p = 3 and q = 5 against it. Both are less than 6, so the split point (if any) must be further left.
- Move to the left child, 2.
- At node 2: compare p = 3 and q = 5 against it. Both are greater than 2, so the split point (if any) must be further right.
- Move to the right child, 4.
- At node 4: compare p = 3 and q = 5 against it. p and q are not both on the same side of 4 — one of them may even equal it — so 4 is exactly where their paths diverge.
- Node 4 is the lowest common ancestor of p = 3 and q = 5. Every step only ever moved in one direction, so the whole search cost O(h) — the height of the tree.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.