2
p
In a BST the lowest common ancestor of p and q is the first node where they split — walk down from the root, turning toward both values until they part ways, no recursion or parent pointers needed.
Given a BST and two nodes p and q, return their lowest common ancestor — the deepest node that has both as descendants (a node is a descendant of itself). For the tree [6,2,8,0,4,7,9,null,null,3,5] with p=2, q=8 the answer is 6; with p=2, q=4 it is 2 (an ancestor of itself).
p and q are greater than the current node, the answer is strictly to the right; if both are smaller, strictly to the left. The very first node where they disagree — one on each side, or one equal to the node — is the lowest node that still has both beneath it. That node is the LCA.node; no stack or recursion required.p > node and q > node, both descendants are in the right subtree, so the ancestor must be too.p < node and q < node, recurse left for the same reason.p and q separately or compute two root-to-node paths. The BST property collapses the search into one descent — and the case where one value equalsthe current node is already handled by the "otherwise" branch, since that node is an ancestor of itself.Each step drops one level, so the work is bounded by the tree's height h — about log n for a balanced BST, but nfor a degenerate "linked list" tree. The iterative form uses constant extra space; the recursive form costs O(h) stack.
p=2 and q=8.class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val: number) {
this.val = val;
this.left = null;
this.right = null;
}
}
function lowestCommonAncestor(
root: TreeNode | null,
p: TreeNode,
q: TreeNode,
): TreeNode | null {
let node = root;
while (node) {
if (p.val > node.val && q.val > node.val) {
node = node.right; // both bigger -> LCA is on the right
} else if (p.val < node.val && q.val < node.val) {
node = node.left; // both smaller -> LCA is on the left
} else {
return node; // split (or node === p/q) -> this is the LCA
}
}
return null;
}node starts at the root and walks downward. Because we only ever move to one child, the whole search is a single straight-line descent — no recursion or auxiliary structures.p.val > node.val && q.val > node.val means both targets live in the right subtree, so any common ancestor must also be on the right. Move node = node.right.pitself, since a node is its own descendant; the "otherwise" branch covers this.| LCA in a BST | walk from root, turn toward both |
| both p,q greater than node | go right |
| both p,q less than node | go left |
| they straddle node / one equals node | return node = LCA |
let node = root;
while (node) {
if (p.val > node.val && q.val > node.val) node = node.right;
else if (p.val < node.val && q.val < node.val) node = node.left;
else return node; // they split here -> LCA
}
return null;