Trees crash course ↗ · 142

235. Lowest Common Ancestor of a Binary Search Tree

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.

● MediumBST PropertyTree WalkTypeScript

PROBLEM What we're solving

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).

KEY IDEA The LCA is where p and q first split

Insight → the BST ordering tells you which way each value lives. Starting at the root, if both 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.

RECIPE Walk down, turning toward both

  • 0 · Start at the root. Keep a single moving pointer node; no stack or recursion required.
  • 1 · Both bigger ⇒ go right. If p > node and q > node, both descendants are in the right subtree, so the ancestor must be too.
  • 2 · Both smaller ⇒ go left. If p < node and q < node, recurse left for the same reason.
  • 3 · Otherwise ⇒ split, return node.They straddle the node (or one equals it). You can't descend without dropping one of them, so this node is the LCA.
Classic confusion → you do not need to find 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.

COST Complexity & alternatives

Generic tree LCA (paths)
O(n) time / O(n) space
Find both root-to-node paths, compare. Ignores the BST order.
BST split-point walk
O(h) time / O(1) space
One descent; h = height (O(log n) if balanced).

Why O(h)

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.

Pattern transfer →the same "compare to node, turn toward the target" descent powers BST search, insert, floor/ceil, and range queries. Drop the BST assumption and LCA becomes the general LCA of a Binary Tree(LC 236), which needs the post-order "found in left and right" merge instead.

RUN IT Walk down the BST until p and q split

step 0 / 2
STARTWalk from the root looking for the split point of p=2 and q=8.
1class TreeNode {
2  val: number;
3  left: TreeNode | null;
4  right: TreeNode | null;
5  constructor(val: number) {
6    this.val = val;
7    this.left = null;
8    this.right = null;
9  }
10}
11 
12function lowestCommonAncestor(
13  root: TreeNode | null,
14  p: TreeNode,
15  q: TreeNode,
16): TreeNode | null {
17▶  let node = root;
18▶  while (node) {
19    if (p.val > node.val && q.val > node.val) {
20      node = node.right;          // both bigger -> LCA is on the right
21    } else if (p.val < node.val && q.val < node.val) {
22      node = node.left;           // both smaller -> LCA is on the left
23    } else {
24      return node;                // split (or node === p/q) -> this is the LCA
25    }
26  }
27  return null;
28}
State
6
node
2
p
8
q
path so farcurrent node / turnsplit point = LCA
slowfast

TYPESCRIPT The solution, annotated

lowestCommonAncestor.ts
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;
}

Reading it block by block

The loop pointer. 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.
Both bigger → right. 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.
Both smaller → left. The mirror case: both are less than the current value, so descend left. These two branches are the only times we keep walking.
Otherwise → return. If neither branch fires, the values split at this node (one on each side) or one of them equals it. Either way this is the deepest node with both as descendants — return it as the LCA.
Complexity → O(h) time where h is the tree height — O(log n) for a balanced BST, O(n) worst case. O(1) extra space for the iterative version (O(h) call stack if written recursively).

INTERVIEWFollow-ups they'll ask

  • "What if it isn't a BST?" Use the general binary-tree LCA (LC 236): recurse, and the LCA is the node where one target is found in the left subtree and the other in the right.
  • "Recursive vs iterative?" Same O(h) time; the iterative walk is O(1) space, the recursive one uses O(h) stack. Interviewers often prefer the iterative form here.
  • "Are p and q guaranteed to exist?"LC 235 guarantees both are in the tree. If not, you'd need to verify each is reachable before trusting the split node.
  • "Could p be an ancestor of q?" Yes — then the descent stops at pitself, since a node is its own descendant; the "otherwise" branch covers this.
  • "Nodes have parent pointers?" Then you can walk both up to equal depth and advance together, or use the depth difference — no tree traversal from the root needed.

OPTIMAL BST Property

lowestCommonAncestor.ts
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;
}
Complexity → O(h) time where h is the tree height — O(log n) for a balanced BST, O(n) worst case. O(1) extra space for the iterative version (O(h) call stack if written recursively).

ALT 1 Brute force — find both root-to-node paths

O(n) time · O(n) space

Search the tree (ignoring the BST property) to record the full path from the root to p and to q, then walk both paths together and return the last node they share.

approach-2.ts
function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode,
): TreeNode | null {
  // Build the root-to-target path; works for any binary tree.
  function findPath(target: TreeNode): TreeNode[] {
    const path: TreeNode[] = [];
    let node = root;
    while (node) {
      path.push(node);
      if (target.val === node.val) break;
      node = target.val < node.val ? node.left : node.right;
    }
    return path;
  }

  const pathP = findPath(p);
  const pathQ = findPath(q);

  // Last node common to both paths is the LCA.
  let lca: TreeNode | null = null;
  for (let i = 0; i < pathP.length && i < pathQ.length; i++) {
    if (pathP[i] === pathQ[i]) lca = pathP[i];
    else break;
  }
  return lca;
}
Note → This materialises both paths (O(n) extra space) and makes two descents. Because a BST tells you which way to turn by comparing values, you can find the split point in a single descent with O(1)space — the optimal solution.

MNEMONIC The one-liner

"Both bigger go right, both smaller go left, otherwise you have split — that's the LCA."

TRIGGERS When you see ___ → reach for ___

LCA in a BSTwalk from root, turn toward both
both p,q greater than nodego right
both p,q less than nodego left
they straddle node / one equals nodereturn node = LCA

SKELETON The reusable shape

skeleton.ts
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;

FLASHCARDS Tap to flip

What makes a node the LCA in a BST?
It is the first node (from the root) where p and q split to opposite sides, or where one of them equals the node.
tap to flip
1 / 6
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
In a BST, what defines the lowest common ancestor of p and q?
QUESTION 02
Both p.val and q.val are greater than node.val. You should:
QUESTION 03
Optimal time complexity of the BST approach?
QUESTION 04
Extra space for the iterative version?
QUESTION 05
If p is an ancestor of q, what does the walk return?
QUESTION 06
For the tree [6,2,8,0,4,7,9,null,null,3,5] with p=2, q=8, the LCA is:
QUESTION 07
Why does dropping the BST assumption (plain binary tree) break this method?
QUESTION 08
#235 · Lowest Common Ancestor of a Binary Search TreeIn a BST the lowest common ancestor of p and q is the first node where the two values split. Walk down from the root, turning toward both until they part ways — O(h) time, O(1) space.Which algorithmic approach does this primarily use?
QUESTION 09
#235 · Lowest Common Ancestor of a Binary Search TreeIn a BST the lowest common ancestor of p and q is the first node where the two values split. Walk down from the root, turning toward both until they part ways — O(h) time, O(1) space.Which implementation correctly solves it?