Skip to main content

92. Lowest Common Ancestor of a Binary Tree

mediumAsked at Ola

Find the lowest common ancestor of two nodes in a binary tree.

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

Problem

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

Constraints

  • 2 <= number of nodes <= 10^5
  • p and q exist in the tree
  • All Node.val are unique

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 and ancestor walk

BFS to record parents; walk up from p collecting ancestors; walk up from q until reaching one.

Time
O(n)
Space
O(n)
// parent map then set traversal

Tradeoff:

2. DFS upward propagation

Recurse; if node is p or q return it; otherwise propagate non-null results from left and right. Two non-null means current node is LCA.

Time
O(n)
Space
O(h)
function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
  const L = lowestCommonAncestor(root.left, p, q);
  const R = lowestCommonAncestor(root.right, p, q);
  if (L && R) return root;
  return L || R;
}

Tradeoff:

Ola-specific tips

Ola interviewers like the upward-propagation idiom; tie it to finding the smallest shared dispatcher node across two driver tasks.

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

Practice these live with InterviewChamp.AI →