Skip to main content

21. Lowest Common Ancestor of a Binary Tree

mediumAsked at GitLab

Find the deepest node that has both p and q as descendants in a binary tree.

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

Problem

Given the root of a binary tree and two nodes p and q, return their lowest common ancestor. Every node is its own ancestor.

Constraints

  • 2 <= nodes <= 10^5
  • All node values are unique
  • p and q 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

Approaches

1. Parent map + ancestor set

BFS to record each node's parent, walk p's ancestors into a set, then climb from q until a hit.

Time
O(n)
Space
O(n)
/* BFS to build parent map, climb p collecting ancestors, climb q until first match. */

Tradeoff:

2. Single-pass DFS

Recurse left and right; if both sides return non-null, the current node is the LCA; otherwise return the non-null side. One clean walk.

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

GitLab-specific tips

GitLab maps this onto their group-and-subgroup permission model — finding the LCA of two members is exactly how they resolve the inherited role both users actually share.

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

Practice these live with InterviewChamp.AI →