Frontend Beauty
ESC

Type to search the knowledge base.

Lowest Common Ancestor BST

Find LCA of two nodes in a BST — walk from the root using ordering, O(h) time, iterative or recursive.

intermediate3 min read
  • dsa
  • tree
  • interview
  • Google
  • Meta
  • Amazon
  • Microsoft

The problem

Given a BST and two nodes p and q, return their lowest common ancestor — the deepest node that has both as descendants (a node can be a descendant of itself).

        6
       / \
      2   8
     / \ / \
    0  4 7  9
      / \
     3   5

p = 2, q = 8 → 6
p = 2, q = 4 → 2

Key: BST order. If both keys are left of current, go left. Both right, go right. Otherwise current splits them → LCA.

Node shape

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

Brute force (general binary tree)

Find path root→p and root→q; last common node on both paths. Works without BST property; O(n) time and O(h) path space. Mention, then use BST.

Optimal: walk using order

function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode
): TreeNode | null {
  let cur = root;
  while (cur) {
    if (p.val < cur.val && q.val < cur.val) {
      cur = cur.left;
    } else if (p.val > cur.val && q.val > cur.val) {
      cur = cur.right;
    } else {
      return cur; // split point or one equals cur
    }
  }
  return null;
}

Recursive one-liner style:

function lcaRec(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  if (!root) return null;
  if (p.val < root.val && q.val < root.val) return lcaRec(root.left, p, q);
  if (p.val > root.val && q.val > root.val) return lcaRec(root.right, p, q);
  return root;
}
Time O(h) — height; O(log n) balanced, O(n) skewed
Space O(1) iterative / O(h) recursive

Edge cases

  • p is ancestor of q (or reverse) — return p
  • p and q are the same node (if allowed)
  • Root is LCA
  • Skewed tree — still correct, linear height

Common bugs

  • Using general-tree LCA code that DFS both sides when BST walk is enough
  • Comparing nodes by reference when values matter (problem usually gives nodes)
  • Forgetting one of p/q can equal the LCA

Interview delivery

  1. Confirm BST + nodes exist in tree.
  2. Explain split-point rule.
  3. Code iterative.
  4. Trace p=2, q=4 → answer 2.
  5. O(h) time, O(1) space.

Further reading