Lowest Common Ancestor of a BST
MediumThe problem
In a binary search tree, find the lowest node that has both p and q somewhere below it (a node counts as being below itself). Return that node.
- Example 1Input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8Output: 6
2 is on the left side of 6 and 8 is on the right side, so 6 is the lowest node above both.
- Example 2Input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 4Output: 2
4 sits below 2, and 2 counts as an ancestor of itself.
- 2 ≤ number of nodes ≤ 100,000
- All values are different
- p and q are different nodes that both exist in the tree
- It is a valid BST: smaller values on the left, bigger on the right
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
In a BST, left is smaller and right is bigger. When do p and q stop going the same direction?
The idea
Start at root: if both values are smaller go left, if both bigger go right, otherwise the current node is the LCA.
Target: O(h) time, O(1) space
Go function shape
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNodeReference solution
Tested with go test. Try it yourself first, then compare.
// LowestCommonAncestorBST uses the BST ordering: if both values are smaller go left, if both are larger go right.
// The first node where they split (or equal one of them) is the lowest common ancestor.
func LowestCommonAncestorBST(root, p, q *TreeNode) *TreeNode {
for root != nil {
switch {
case p.Val < root.Val && q.Val < root.Val:
root = root.Left
case p.Val > root.Val && q.Val > root.Val:
root = root.Right
default:
return root
}
}
return nil
}