236. Lowest Common Ancestor of a Binary Tree

Q: Why does the simple recursive return work?

The return value is overloaded: at leaf or matching nodes, it's the matching node. At nodes where both subtrees return non-null, it's the LCA. Above the LCA, one subtree returns the LCA and the other returns null, so we propagate the LCA upward.

Q: Why does Pinterest care about LCA?

It tests the 'overloaded recursive return value' pattern that shows up in tree problems across Pinterest's hierarchical data (board nesting, comment threads). Master this and dozens of variants become trivial.

mediumAsked at Pinterest

Lowest Common Ancestor is Pinterest's go-to tree-recursion problem: given two nodes in a binary tree, return their deepest common ancestor. The interviewer wants the postorder 'return target nodes upward and join at the split point' pattern.

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

Source citations

Public interview reports confirming this problem appears in Pinterest loops.

Glassdoor (2026-Q1)— Pinterest SWE onsite reports cite LCA as a 30-minute tree-recursion round.
LeetCode Pinterest tag (2026-Q1)— On the Pinterest company-tagged problem list.

Problem

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. 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

Example 2

Input

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

Output

Explanation: A node can be a descendant of itself.

Approaches

1. Parent pointers + path comparison

BFS to build a parent map. Walk from p up to root collecting ancestors in a Set. Walk from q up; first hit in the Set is the LCA.

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

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

Tradeoff: Two passes, O(n) extra space. Easy to reason about but verbose. The recursive version is shorter and the canonical Pinterest answer.

2. Recursive postorder (optimal)

DFS returns: the LCA if found in the subtree, else p or q if exactly one is found, else null. At each node, if both left and right subtree returns are non-null, this node is the LCA.

Time: O(n)
Space: O(h) recursion

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. The trick: the recursive return value overloaded as both 'found node' and 'LCA found'. Once both children return non-null, the current node is the split point. Above the split point, one child returns the LCA itself and the other returns null.

Pinterest-specific tips

Pinterest interviewers love the recursive version because it's elegant — but they will probe whether you understand WHY it works. The invariant: 'the return value is p, q, or the LCA if both have been seen below.' Narrate this before writing. They may follow up with 'what if p or q might NOT be in the tree?' — then you need a separate found-counter, otherwise you might return a non-existent ancestor.

Common mistakes

Returning root === p OR root === q as null — should return the matching node so the parent sees it.
Going DFS preorder and stopping too early — you must process both subtrees before deciding.
Not handling the 'one node is ancestor of the other' case — the recursive version handles it naturally because that node returns itself.
Confusing this with the BST variant (LeetCode 235) which has a cleaner solution using value ordering.

Follow-up questions

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

LCA in a BST (LeetCode 235) — use value ordering instead of recursion.
What if p or q might not be in the tree?
LCA of multiple nodes (more than 2).
LCA with parent pointers but no root reference.

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 simple recursive return work?

The return value is overloaded: at leaf or matching nodes, it's the matching node. At nodes where both subtrees return non-null, it's the LCA. Above the LCA, one subtree returns the LCA and the other returns null, so we propagate the LCA upward.

Why does Pinterest care about LCA?

It tests the 'overloaded recursive return value' pattern that shows up in tree problems across Pinterest's hierarchical data (board nesting, comment threads). Master this and dozens of variants become trivial.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →