Skip to main content

92. Lowest Common Ancestor of a Binary Tree

mediumAsked at Vercel

Find the lowest common ancestor of two nodes in a binary tree. Vercel asks this because LCA is the natural primitive for their route-tree common-segment resolution — exactly how they find the shared prefix between two dynamic routes.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel routing-team onsite; recursive split expected.
  • Blind (2026-Q1)— Listed in Vercel platform engineer screen.

Problem

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: 'The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to 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
  • p and q will exist in the tree.

Examples

Example 1

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

Example 2

Input
Same tree, p = 5, q = 4
Output
5

Explanation: A node can be a descendant of itself.

Approaches

1. Find paths to both, compare prefixes

DFS to find path-to-p and path-to-q; the LCA is the last common node.

Time
O(n)
Space
O(h)
// Two DFSes plus path comparison. Works but more code than the single-pass recursion.

Tradeoff: Two passes.

2. Single recursion (optimal)

If root is null or matches p or q, return root. Recurse left and right. If both return non-null, root is the LCA. Else return whichever is non-null.

Time
O(n)
Space
O(h) stack
function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left || right;
}

Tradeoff: Five lines, O(n) time. The recursion implicitly finds both nodes and returns the split point in one pass.

Vercel-specific tips

Vercel grades the single-recursion approach. Bonus signal: explaining the three possible return values (null = neither found in this subtree, p or q = exactly one found, root = both found via a split) and noting that 'a node is its own ancestor' is the base case allowing root === p || root === q.

Common mistakes

  • Returning root.val instead of root — LC expects the node, not the value.
  • Forgetting the 'one of them IS p or q' base case — recursion never terminates.
  • Not realizing the recursion finds both nodes implicitly — adding redundant 'find' calls.

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

  • LCA of a BST (LC 235) — exploit ordering.
  • LCA of n nodes — generalize the split detection.
  • What if nodes might not exist? Need explicit found-flags.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why does this work?

If both p and q are in the same subtree, the recursion returns one of them and the other null at this level — passing the answer up. If they're in different subtrees, both sides return non-null AT THIS NODE, which means we've found the split point.

What if p or q isn't in the tree?

The function would return p or q (whichever IS in the tree) — incorrect. For the LC constraint, both are guaranteed present; for the general case, add explicit flags.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →