20. Lowest Common Ancestor of a Binary Tree

Q: Why does the 5-line recursive version work?

At each node, we check whether p or q (or their descendants) appear in the left and right subtrees. If both sides return non-null, the current node is the LCA. If only one side does, the LCA is in that side. The recursion bubbles up the answer.

Q: What if p or q doesn't exist in the tree?

The problem guarantees both exist. If they don't, the 5-line version returns p or q (whichever it finds) — which is wrong. Add an explicit existence check if the guarantee is removed.

mediumAsked at Palantir

Given a binary tree, find the lowest common ancestor of two given nodes. Palantir asks this because it's the kernel of their ontology permission resolver — to determine the closest shared parent of two entities so row-level ACL checks can short-circuit at the right scope.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Palantir loops.

Glassdoor (2026-Q1)— Palantir FDE on-site — frame: 'common parent for permission inheritance'.
Blind (2025-10)— Reported with 'ontology' framing in the follow-up.
LeetCode Discuss (2026-01)— Tagged as a Palantir favorite.

Problem

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. The LCA of two nodes p and q is defined as the lowest node in the tree that has both p and q as descendants (where 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
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

Example 2

Input

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

Output

Explanation: Node 5 is an ancestor of itself by definition.

Example 3

Input

root = [1,2], p = 1, q = 2

Output

Approaches

1. Parent map + ancestor set

BFS to record each node's parent. Walk up from p collecting ancestors. Walk up from q; first hit in the set is the LCA.

Time: O(n)
Space: O(n)

function lowestCommonAncestor(root, p, q) {
  const parent = new Map();
  parent.set(root, null);
  const queue = [root];
  while (!parent.has(p) || !parent.has(q)) {
    const node = queue.shift();
    if (node.left) { parent.set(node.left, node); queue.push(node.left); }
    if (node.right) { parent.set(node.right, node); queue.push(node.right); }
  }
  const ancestors = new Set();
  let cur = p;
  while (cur) { ancestors.add(cur); cur = parent.get(cur); }
  cur = q;
  while (!ancestors.has(cur)) cur = parent.get(cur);
  return cur;
}

Tradeoff: Clear and iterative — survives deep trees. O(n) extra space for the parent map. Use when interviewer wants explicit ancestry tracking.

2. Recursive post-order short-circuit

Recurse left and right. If both subtrees return non-null, current node is the LCA. Else propagate the non-null upward.

Time: O(n)
Space: O(h) recursion 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, no extra data structures. The cleverness is the dual-non-null check that catches the split. This is the canonical Palantir answer.

Palantir-specific tips

Palantir wants the 5-line recursive solution AND the explanation of why it works in one pass. Articulate the invariant: 'if the LCA is in this subtree, both p and q live in it; otherwise at most one does.' Bonus signal: connect to row-level ACL — when checking if user U can access record R, you walk up R's ontology parents until you hit a node where U's permission is defined; the LCA pattern shows you understand that lookup shape.

Common mistakes

Returning the FIRST non-null without checking both sides — you'd return p or q instead of their common ancestor.
Comparing by value instead of reference — fails when the problem guarantees unique values but you wrote it to be safe.
Forgetting the early termination root === p || root === q — gives a stack overflow on degenerate inputs.

Follow-up questions

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

LCA of a BST (LC 235) — uses ordering, much simpler.
LCA with parent pointers (LC 1650) — two-pointer style, O(h) without extra space.
LCA of k nodes in a tree (generalized).

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 the 5-line recursive version work?

At each node, we check whether p or q (or their descendants) appear in the left and right subtrees. If both sides return non-null, the current node is the LCA. If only one side does, the LCA is in that side. The recursion bubbles up the answer.

What if p or q doesn't exist in the tree?

The problem guarantees both exist. If they don't, the 5-line version returns p or q (whichever it finds) — which is wrong. Add an explicit existence check if the guarantee is removed.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →