Skip to main content

28. Lowest Common Ancestor of a Binary Search Tree

easyAsked at Box

Find the deepest node that is an ancestor of two given nodes in a BST — Box uses LCA logic when computing the nearest shared parent folder for two files to determine the effective permission scope for a sharing operation.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes p and q. The LCA is defined as the lowest node in the tree that has both p and q as descendants (a node can be a descendant of itself).

Constraints

  • The number of nodes in the tree is in the range [2, 10^5]
  • -10^9 <= Node.val <= 10^9
  • All Node.val are unique
  • p != q, and both p and q will exist in the BST

Examples

Example 1

Input
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output
6

Explanation: The LCA of nodes 2 and 8 is the root node 6.

Example 2

Input
root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output
2

Explanation: Node 2 is an ancestor of node 4, so LCA is 2.

Approaches

1. Brute force — record ancestors path

Find the path from root to p and root to q as arrays, then walk from the end until they diverge — the last common node is the LCA.

Time
O(n)
Space
O(n)
function lowestCommonAncestor(root, p, q) {
  function pathTo(root, target) {
    if (!root) return null;
    if (root.val === target.val) return [root];
    const left = pathTo(root.left, target);
    if (left) return [root, ...left];
    const right = pathTo(root.right, target);
    if (right) return [root, ...right];
    return null;
  }
  const pathP = pathTo(root, p);
  const pathQ = pathTo(root, q);
  let lca = null;
  for (let i = 0; i < Math.min(pathP.length, pathQ.length); i++) {
    if (pathP[i].val === pathQ[i].val) lca = pathP[i];
    else break;
  }
  return lca;
}

Tradeoff:

2. Optimal — BST property traversal

Exploit the BST invariant: if both p and q are less than current node, go left; if both greater, go right; otherwise the current node is the split point — that is the LCA.

Time
O(h) where h = tree height
Space
O(1) iterative
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; // split point = LCA
    }
  }
  return null;
}

Tradeoff:

Box-specific tips

Box rates this as an easy problem but uses it to test whether you can articulate the BST property clearly under pressure — many candidates jump to general binary tree LCA logic (LC 236) and miss the O(h) shortcut. Connect it to Box's product: finding the nearest common parent folder between two shared files determines which permission group is authoritative, a computation Box's sharing service performs millions of times per day.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Lowest Common Ancestor of a Binary Search Tree and other Box interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →