Skip to main content

16. Lowest Common Ancestor of a Binary Tree

mediumAsked at Notion

Find the deepest node that is an ancestor of both p and q — a direct model of Notion's breadcrumb and mention-resolution logic, where the system must locate the nearest shared parent page between two linked blocks.

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

Problem

Given a binary tree and two nodes p and q, find their lowest common ancestor (LCA). The LCA is the deepest node that has both p and q as descendants (a node can be a descendant of itself).

Constraints

  • 2 <= number of nodes <= 10^5
  • All node values are unique
  • p and q are different nodes; both 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: Node 3 is the LCA of nodes 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: Node 5 is an ancestor of node 4, so it is the LCA.

Approaches

1. Brute force — parent map

BFS/DFS to build a parent pointer map; walk ancestors of p into a set, then walk ancestors of q until a match is found.

Time
O(n)
Space
O(n)
function lowestCommonAncestor(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 curr = p;
  while (curr) { ancestors.add(curr); curr = parent.get(curr); }
  curr = q;
  while (!ancestors.has(curr)) curr = parent.get(curr);
  return curr;
}

Tradeoff:

2. Recursive post-order

If a node matches p or q, return it; bubble up the found result — when both subtrees return non-null, the current node is the LCA.

Time
O(n)
Space
O(h) call 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:

Notion-specific tips

Notion evaluates whether you can map an abstract tree algorithm to a concrete product feature — mention that page breadcrumbs and @-mention resolution both reduce to LCA. Interviewers also watch whether you handle the self-ancestor edge case (p is an ancestor of q) without prompting.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →