Skip to main content

236. Lowest Common Ancestor of a Binary Tree

mediumAsked at Apple

Lowest Common Ancestor is Apple's elegant tree recursion medium. The clean answer is dual: 'return p or q if found, else return whichever subtree returned non-null — if both subtrees return non-null, this node is the LCA.' Five lines that make Apple interviewers smile.

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

Source citations

Public interview reports confirming this problem appears in Apple loops.

  • Glassdoor (2026-Q1)— Apple SWE phone-screen reports list LCA of a Binary Tree as a recurring 25-minute tree medium.
  • Blind (2025-12)— Apple ICT3/ICT4 reports cite LCA with the 'now without parent pointers' or 'now with parent pointers' variants.

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

Explanation: The LCA of nodes 5 and 1 is 3.

Example 2

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

Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself.

Approaches

1. Recursive: return p or q (optimal)

Base case: if node is null or matches p or q, return node. Recurse into both subtrees. If both returns are non-null, this node IS the LCA. Otherwise return whichever is non-null.

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. The interpretation: 'left returns one node IF it found p or q somewhere in its subtree.' If both subtrees report finding one, the current node must be the LCA. Apple grades on whether you can ARTICULATE this dual interpretation.

2. Path-finding + compare prefixes

Find the root-to-p and root-to-q paths. Walk both prefixes; the last common ancestor is the LCA.

Time
O(n)
Space
O(n)
function lowestCommonAncestor(root, p, q) {
  function path(node, target, acc) {
    if (!node) return false;
    acc.push(node);
    if (node === target) return true;
    if (path(node.left, target, acc) || path(node.right, target, acc)) return true;
    acc.pop();
    return false;
  }
  const pp = [], qq = [];
  path(root, p, pp);
  path(root, q, qq);
  let lca = root;
  for (let i = 0; i < Math.min(pp.length, qq.length); i++) {
    if (pp[i] === qq[i]) lca = pp[i];
    else break;
  }
  return lca;
}

Tradeoff: Two passes plus the compare. O(n) extra space. Useful when you need MORE than just the LCA (e.g., distance between nodes). Apple accepts but the recursive version is cleaner.

Apple-specific tips

Apple is grading whether you can dual-purpose the recursion: same function, two interpretations of the return value. Say it out loud BEFORE writing: 'the return value is the LCA of p and q within this subtree IF both are present; otherwise it's whichever of p or q was found; otherwise null.' That paragraph is the entire interview.

Common mistakes

  • Forgetting the 'a node can be a descendant of itself' clause — produces wrong answer when one of p, q is an ancestor of the other.
  • Comparing values when the problem says compare references — node values are unique here so it works either way, but be explicit.
  • Returning the wrong subtree when one of them returns null (must return the NON-null one, not always left).

Follow-up questions

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

  • Lowest Common Ancestor of a BST (LC 235) — exploit BST ordering for O(log n).
  • Lowest Common Ancestor with Parent Pointers (LC 1650) — walk up from both, like the Y-intersection of two linked lists.
  • K nodes' LCA — generalize to a set of nodes.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

What's the trick to the recursive solution?

Same function returns one of three things based on context: (1) null if neither p nor q is in this subtree, (2) p or q if only one is found, (3) the LCA if both are found. The if/else at the end disambiguates.

What if the tree had parent pointers?

Walk up from p and q, marking visited. The first time the other side hits a marked node, that's the LCA. O(d) where d is depth.

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 Apple interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →