Pattern visualizer
Lowest Common Ancestor of a BST
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. Animated on: Given the root of a BST and two of its node values, p = 3 and q = 5, find their lowest common ancestor..
BST
step 1 / 8
0
2
3
4
5
6
7
8
9
line 1
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