Q36: Lowest Common Ancestor of a Binary Search Tree
Given a Binary Search Tree (BST), find the lowest common ancestor (LCA) node of two given nodes p and q.
BST Lowest Common Ancestor Iterative Search
function lowestCommonAncestor(root, p, q) {
let curr = root;
while (curr) {
if (p.val < curr.val && q.val < curr.val) {
curr = curr.left;
} else if (p.val > curr.val && q.val > curr.val) {
curr = curr.right;
} else {
return curr; // Divergence node found
}
}
return null;
}💡 Traverses tree using BST value properties. If both values are less than
curr.val, move left. If both are greater, move right. Otherwise curr is the LCA.Key Takeaways
- Exploit BST properties: if both values are smaller than root, LCA lies in left subtree; if larger, in right subtree.
- The split node where
pandqdiverge to opposite sides is the LCA.
Knowledge Check
What is the time complexity of LCA search on a balanced Binary Search Tree?