Lowest Common Ancestor of a BST
Problem
Given a BST and two nodes p and q in it, return their lowest common ancestor (a node counts as its own descendant). Use the BST ordering instead of searching the whole tree.
Example 1
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6
Example 2
Input: same tree, p = 2, q = 4 Output: 2
Test cases
Case 1
Input: [6,2,8,0,4,7,9,null,null,3,5], 2, 8 Expected: 6
Case 2
Input: [6,2,8,0,4,7,9,null,null,3,5], 2, 4 Expected: 2
Case 3
Input: [2,1], 2, 1 Expected: 2
View solutionHide solution1 approach
1. Walk down using ordering
Time O(h)Space O(1)
Both values smaller → go left; both larger → go right; otherwise this node splits them and is the LCA.
function lowestCommonAncestor(root, p, q) { let node = root; while (node) { if (p.val < node.val && q.val < node.val) node = node.left; else if (p.val > node.val && q.val > node.val) node = node.right; else return node; } return null;}