Skip to main content

236. Lowest Common Ancestor of a Binary Tree

mediumAsked at Broadcom

Find the lowest common ancestor of two nodes in a binary tree. Broadcom asks this because LCA is the basis for tree-based network topology analysis — finding the common aggregation point of two hosts in a hierarchical data-center topology or spanning tree.

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

Source citations

Public interview reports confirming this problem appears in Broadcom loops.

  • Glassdoor (2025-12)— Reported in Broadcom SWE onsite reports as a binary-tree traversal problem in infrastructure software rounds.
  • Blind (2025-09)— Broadcom threads cite LCA as a medium problem that tests recursive tree thinking beyond simple traversals.

Problem

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes p and q. The LCA is defined 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). All node values are unique and both p and q will exist in the tree.

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: 3 is the lowest ancestor of both 5 and 1.

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 4 — and itself — so 5 is the LCA.

Approaches

1. Recursive post-order DFS

Recurse left and right. If the current node is p or q, return it. If both left and right return non-null, the current node is the LCA. Otherwise propagate the non-null side.

Time
O(n)
Space
O(h) call stack where h is tree height
function lowestCommonAncestor(root, p, q) {
  if (root === null) return null;
  if (root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left !== null && right !== null) return root; // split — root is LCA
  return left !== null ? left : right; // propagate found node upward
}

Tradeoff: O(n) time — visits every node once. O(h) stack space — O(log n) for balanced, O(n) for a degenerate tree. Elegant and the canonical answer for general binary trees.

2. Iterative with parent pointers

BFS or DFS to build a parent-pointer map for every node. Collect all ancestors of p in a Set. Walk q's ancestors until finding one in p's ancestor set — that's the LCA.

Time
O(n)
Space
O(n)
function lowestCommonAncestor(root, p, q) {
  const parent = new Map([[root, null]]);
  const stack = [root];
  // Build parent pointers until both p and q are found
  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); }
  }
  // Collect ancestors of p
  const ancestors = new Set();
  let curr = p;
  while (curr !== null) { ancestors.add(curr); curr = parent.get(curr); }
  // Walk q's ancestors until hitting p's ancestor
  curr = q;
  while (!ancestors.has(curr)) curr = parent.get(curr);
  return curr;
}

Tradeoff: O(n) time and space. Iterative — avoids recursion stack overflow on deep trees. Broadcom follow-ups sometimes ask for this when the tree is extremely deep.

Broadcom-specific tips

At Broadcom, explain the three cases in the recursive approach before coding: '1. Current node is p or q — return it. 2. p and q split across left and right subtrees — current node is the LCA. 3. Both found on the same side — propagate upward.' Connect to networking: 'This is equivalent to finding the common aggregation switch in a spine-leaf topology for two given hosts — the first node where both paths converge.' Broadcom may also ask the BST variant (LC 235) — note that BST ordering allows a simpler O(h) scan without visiting every node.

Common mistakes

  • Returning before completing the recursive calls — you need both left and right results before deciding.
  • Not handling the case where root equals p or q — a node is an ancestor of itself.
  • Confusing the BST LCA (LC 235) with the general binary tree LCA (LC 236) — the BST version uses value ordering.
  • Assuming p and q are always in different subtrees — they may be on the same path (one is an ancestor of the other).

Follow-up questions

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

  • LCA in a Binary Search Tree (LC 235) — simpler because BST ordering guides the search.
  • LCA with parent pointers given (O(h) two-pointer scan on ancestor lists).
  • LCA queries on a general graph (requires converting to tree with DFS tree + binary lifting).

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 post-order work here?

You need results from both subtrees before making a decision at each node — post-order (process children before parent) provides exactly that information flow.

What if p or q is not in the tree?

The problem guarantees both exist. In a variant where they might not, add a found counter and only return the LCA if both are found.

How does the BST LCA differ?

In a BST, if both p and q values are less than root, go left; if both greater, go right; otherwise root is the LCA. O(h) and requires no post-order — much simpler.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →