Lowest Common Ancestor of a Binary Search Tree
The Prompt
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST. The lowest common ancestor is defined between two nodes `p` and `q` as the lowest node in `T` that has both `p` and `q` as descendants.
Understanding the Problem
The lowest common ancestor of p and q is the deepest node that has both as descendants — and a node counts as its own descendant, so p can be the LCA of p and q if q lives in its subtree.
In a plain binary tree you would need to search both sides. In a BST the ordering does the searching for you: at any node, comparing p and q against the node's value tells you which single direction to go — no backtracking, no visiting both subtrees.
The Interview Flow
Interviewer
Given a Binary Search Tree and two nodes, how do you find their Lowest Common Ancestor?
Candidate
The fact that it's a BST is a huge hint. The properties of a BST (left child is smaller, right child is larger) can guide the search.
Interviewer
How so?
Candidate
I can start at the root. At any given node, I compare its value with the values of the two target nodes, `p` and `q`. If both `p` and `q` are smaller than the current node's value, it means their LCA must be in the left subtree. If both are larger, the LCA must be in the right subtree.
Interviewer
What happens if they are not both on the same side?
Candidate
That's the key. If one target node is smaller and the other is larger than the current node (or if the current node is one of the targets), then the current node is the "split point". It's the first ancestor that has `p` and `q` in different subtrees. Therefore, it must be the Lowest Common Ancestor.
Interviewer
Can this be done iteratively?
Candidate
Yes, very easily. I can just use a while loop instead of recursion. I start a pointer at the root and keep moving it left or right based on the comparisons until I find the split point. This avoids the recursion overhead and uses O(1) space.
Interviewer
Excellent. The iterative solution is very efficient. Please implement it.
Why does the first "split point" have to be the answer?
Walk down from the root with this invariant: both p and q live in the current subtree. If both values are smaller than the current node, both targets are in the left subtree, so the LCA is too; if both are larger, go right. The first node where they no longer agree — one on each side, or the node equals p or q — is a common ancestor, and no deeper node can contain both. That makes it the lowest.
Each step descends one level, so time is O(h) — O(log n) balanced, O(n) skewed — and the iterative walk needs O(1) space. This beats the generic binary-tree LCA precisely because the BST property replaces exploration with comparison.
Iterative Solution Leveraging BST Properties
- Start with a pointer `curr` at the `root` of the BST.
- Enter a `while` loop that continues as long as `curr` is not null.
- Inside the loop, compare the values of `p` and `q` with `curr.val`.
- If both `p.val` and `q.val` are greater than `curr.val`, it means the LCA must be in the right subtree. Move the pointer: `curr = curr.right`.
- If both `p.val` and `q.val` are less than `curr.val`, the LCA must be in the left subtree. Move the pointer: `curr = curr.left`.
- If neither of the above conditions is met, it means we have found the split point. The current `curr` node is the LCA. Break the loop and return `curr`.
Try it yourself
Write your solution and run it against 2 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function lowestCommonAncestor(root, p, q) {
let curr = root;
while (curr) {
if (p.val > curr.val && q.val > curr.val) {
curr = curr.right;
} else if (p.val < curr.val && q.val < curr.val) {
curr = curr.left;
} else {
return curr;
}
}
}Explanation
Find the LCA of p = 2 and q = 4 in the BST [6, 2, 8, 0, 4, 7, 9] — a straight walk down from the root.
1At 6: both p = 2 and q = 4 are less than 6, so both live in the left subtree. The LCA must be there too — descend left.
2At 2: the targets split — p equals the current node and q = 4 is greater, sitting in its right subtree. This is the split point.
3Node 2 is an ancestor of both (a node is its own descendant), and nothing deeper can contain both 2 and 4. Answer: 2. Two comparisons, no backtracking.
Complexity Analysis
TIME
O(log n)
SPACE
O(1)
Finished working through this one?
Mark it complete to track it on your Data Structures path.