Lowest Common Ancestor of a BST: The Split-Point Walk
Find the lowest common ancestor in a binary search tree in O(h) time by walking down until p and q split. Intuition, JavaScript code, and a full walkthrough.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Finding the lowest common ancestor (LCA) of two nodes in a general binary tree is fiddly — you usually recurse into both subtrees and reconcile what you find. But a binary search tree hands you a shortcut that most people miss on the first try: the BST ordering property tells you which way to go without ever looking at both subtrees.
The whole solution collapses into one idea: walk down from the root, and the first node that sits between p and q is your answer. No auxiliary arrays, no second pass, no comparing return values from left and right.
Get this and you get the mental model behind half the "search the BST" problems — the same downward walk that powers lookup, insertion, and range queries.
The problem
Given the root of a binary search tree and two nodes p and q that both exist in it, return their lowest common ancestor: the deepest node that has p in one subtree and q in the other. A node counts as a descendant of itself, so if p is an ancestor of q, then p is the LCA.
Here's the tree the visualizer defaults to:
6
/ \
2 8
/ \ / \
0 4 7 9
/ \
3 5
Input: root = above, p = 2, q = 8
Output: 6 // 2 sits in the left subtree, 8 in the right — they split at 6Because it's a BST, every value in the left subtree of a node is smaller than that node, and every value in the right subtree is larger. That single invariant is the whole game.
The brute force baseline
Without using the BST property, you'd treat it like any binary tree: find the root-to-node path for p, find the path for q, then walk both paths in lockstep and return the last node they share.
function lca(root, p, q) {
const pathTo = (node, target, path) => {
if (!node) return null;
path.push(node);
if (node.val === target) return path;
return pathTo(node.left, target, path) || pathTo(node.right, target, path)
|| (path.pop(), null);
};
const pPath = pathTo(root, p.val, []);
const qPath = pathTo(root, q.val, []);
let ancestor = null;
for (let i = 0; i < pPath.length && i < qPath.length; i++) {
if (pPath[i] === qPath[i]) ancestor = pPath[i];
else break;
}
return ancestor;
}This works on any binary tree, but it wastes what the BST gives you. Building each path can visit every node — that's O(n) time and O(n) extra space for the two path arrays. On a tree of 10⁵ nodes you're touching all of them twice and allocating two lists, when a BST lets you never look at a node you don't need.
The key insight: let the ordering pick the direction
At any node, compare it against both targets and there are exactly three cases:
- Both
pandqare smaller than the current node. Both must live in the left subtree, so move left. - Both
pandqare larger. Both must live in the right subtree, so move right. - Otherwise — one is smaller and one is larger, or one equals the current node. This is the split point:
pandqdiverge here (or one of them is this node). The current node is the LCA.
That third case is the answer. The deepest node where the two targets stop agreeing on direction is, by definition, the lowest node with one target on each side. This is the BST Split Point pattern: you never explore, you just descend until the paths fork.
The optimal solution
The visualizer teaches the recursive form. It reads directly off the three cases above:
var lowestCommonAncestor = function(root, p, q) {
if (p.val < root.val && q.val < root.val) {
return lowestCommonAncestor(root.left, p, q);
} else if (p.val > root.val && q.val > root.val) {
return lowestCommonAncestor(root.right, p, q);
} else {
return root;
}
};Three branches, one comparison of directions per level. The else fires the moment the targets split — no explicit "is this the answer?" check needed, because reaching else is the check.
Because the recursion is a single tail call, you can flatten it into a loop with O(1) space and no stack frames:
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;
}Same logic, same decisions, but nothing on the call stack. Interviewers love it when you offer the iterative version unprompted — it shows you understand the recursion is just a walk.
Walkthrough
Trace p = 3, q = 5 on the default tree. Both live under node 4, so the LCA is 4 — a non-root internal node, which makes the descent interesting.
| Step | current node | p=3 vs node | q=5 vs node | Decision | Move to |
|---|---|---|---|---|---|
| 1 | 6 | 3 < 6 | 5 < 6 | both smaller | left → 2 |
| 2 | 2 | 3 > 2 | 5 > 2 | both larger | right → 4 |
| 3 | 4 | 3 < 4 | 5 > 4 | split | return 4 |
Step 1: both targets are below 6, so the entire right subtree (8, 7, 9) is pruned without a visit. Step 2: at 2, both targets are above it, so 0 and everything left is pruned. Step 3: at 4, one target goes left and the other goes right — they've split, so 4 is the deepest shared ancestor. Three comparisons, three nodes touched, out of eleven.
Contrast with the default p = 2, q = 8: at the root 6, 2 < 6 but 8 > 6, so they split immediately and 6 is returned in a single step.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Path-building (any tree) | O(n) | O(n) | may visit every node; stores two full paths |
| Recursive split walk | O(h) | O(h) | one hop per level; h stack frames |
| Iterative split walk | O(h) | O(1) | one hop per level; no stack, single pointer |
Here h is the height of the tree — O(log n) when balanced, O(n) in the worst case of a degenerate (linked-list-shaped) BST. The iterative version is the tightest: it does at most one comparison per level and carries a single pointer, so space never grows with the input.
Common mistakes
- Recursing into both subtrees. That's the general-binary-tree LCA. In a BST the ordering tells you the one direction to go — exploring both throws the advantage away and turns O(h) into O(n).
- Forgetting a node is its own descendant. If
p = 6(the root) andq = 4, the answer is6. Theelsebranch handles it automatically becausep.val === node.valfails both the "both smaller" and "both larger" tests — but only if you don't add a specialnode === pguard that returns early and breaks the definition. - Using strict
<on one side and<=on the other. Keep both comparisons strict (<and>). The equality case must fall through toelseso that a target equal to the current node correctly stops the walk. - Assuming p and q are ordered. The algorithm never needs
p < q; it compares each target independently against the node. Sorting them first is wasted work. - Not exploiting the tree shape. If you find yourself building a hash set of ancestors or doing a full traversal, step back — the BST invariant removes the need for any of it.
Where this pattern shows up next
The "let the ordering steer the walk" move is the backbone of BST problems:
- Search in a Binary Search Tree — the same downward walk, stopping when you hit the target value.
- Insert into a Binary Search Tree — walk to the correct empty slot using the identical comparison logic.
- Validate Binary Search Tree — the flip side: verify the ordering invariant that makes all these shortcuts legal.
- Kth Smallest Element in a BST — leans on the ordering through an in-order traversal instead of a direct descent.
You can also step through the LCA search interactively to watch the split point light up as the walk descends, one node at a time.
FAQ
Why is the BST version of LCA so much simpler than the general binary tree version?
In a general binary tree you have no way to know which subtree a node lives in, so you must search both and reconcile the results — that's an O(n) traversal. A BST's ordering invariant tells you, at every node, exactly which direction each target lies. You descend along a single path and stop the moment the targets split, which is O(h) time and needs no reconciliation step.
What is the time and space complexity of the LCA-in-a-BST solution?
Time is O(h), where h is the tree's height: you do at most one comparison per level as you walk down. For a balanced BST that's O(log n); for a degenerate, list-shaped BST it's O(n). The recursive version uses O(h) space for the call stack, while the iterative loop version uses O(1) space because it carries a single pointer and never recurses.
How do I know when I've found the lowest common ancestor?
You've found it at the first node where p and q stop agreeing on direction — the split point. If both targets are smaller than the current node you go left, if both are larger you go right, and if neither holds (one is smaller and one larger, or one equals the node) then the current node has p on one side and q on the other. That is the deepest node ancestral to both, which is precisely the LCA.
Does the solution handle the case where one node is an ancestor of the other?
Yes, automatically. Suppose p is an ancestor of q. When the walk reaches p, one comparison is an equality (p.val equals the node's value), so neither the "both smaller" nor "both larger" branch fires. Control falls to the else branch and returns the current node — which is p. No special-casing is required, because a node is defined to be a descendant of itself.
Should I use the recursive or iterative version in an interview?
Both are correct, but the iterative loop is the stronger answer. It's O(1) space instead of O(h), avoids any risk of stack overflow on a deeply skewed tree, and demonstrates that you understand the recursion is really just a single downward walk. Lead with the recursive form to explain the three cases clearly, then mention you can flatten it into a loop since it's a pure tail call.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.