Skip to main content

236. Lowest Common Ancestor of a Binary Tree

mediumAsked at Meta

Given a binary tree, find the LCA of two nodes. Meta asks this to test whether you grasp the canonical postorder recursion: 'if I find p in one subtree and q in the other, I'm the LCA.'

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

Source citations

Public interview reports confirming this problem appears in Meta loops.

  • Glassdoor (2026-Q1)— Meta E4 onsite reports cite this as a tree-recursion staple.
  • Blind (2025-12)— Recurring Meta interview question.

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
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output
5

Explanation: 5 is an ancestor of itself.

Approaches

1. Recursive postorder (optimal)

Recurse left + right. If both return non-null, current node is LCA. If only one returns non-null, propagate it up.

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 of code; elegant. The invariant: this function returns p, q, the LCA, or null. The 'both children returned non-null' case means p and q are split between the subtrees, so the current node is the LCA.

2. Iterative with parent pointers (alternative)

Build a parent map via BFS/DFS. Walk up from p collecting ancestors. Walk up from q; first shared ancestor is LCA.

Time
O(n)
Space
O(n)
function lowestCommonAncestorIter(root, p, q) {
  const parent = new Map();
  parent.set(root, null);
  const stack = [root];
  while (!parent.has(p) || !parent.has(q)) {
    const node = stack.pop();
    if (node.left) { parent.set(node.left, node); stack.push(node.left); }
    if (node.right) { parent.set(node.right, node); stack.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: More code, more memory, but iterative (no recursion stack). Useful if the tree could be deeper than the stack limit.

Meta-specific tips

Meta interviewers want the recursive version. It's five lines and the logic is profound: the function returns 'whatever I found in this subtree' (p, q, the LCA, or null). The 'both children returned something' case is where the LCA lives. Articulate that invariant before coding.

Common mistakes

  • Returning early on root === p without checking the other subtree — fine here because p is an ancestor of itself, but easy to mis-handle.
  • Forgetting the base case (root === null).
  • Treating this like LCA-in-BST — which has a much simpler solution and wrong recurrence.

Follow-up questions

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

  • LCA of BST (LC 235) — exploits ordering for O(h) without recursion.
  • LCA of multiple nodes — track count of found descendants.
  • What if the tree had parent pointers (no need for the postorder)?

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 'both children returned non-null' identify the LCA?

If left subtree contains p (or q) and right subtree contains q (or p), they're on different sides — so the current node is the lowest common ancestor.

What does it mean to return left || right?

If only one side found something, propagate it up. Either we found one of p/q in this subtree (parent will use this), or we found the LCA already in a deeper recursion (also propagate).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →