Skip to main content

78. Lowest Common Ancestor of a Binary Tree

mediumAsked at Workday

Find LCA in a general binary tree (no BST property). Workday uses this for org-chart trees that aren't sorted — finding the lowest shared manager between two employees.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2026-Q1)— Workday org-chart team — direct analogy.

Problem

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes 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

Example 2

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

Approaches

1. Build parent pointer map + walk up

BFS/DFS to record parents. Walk p up to root, marking ancestors. Walk q up; first marked is LCA.

Time
O(n)
Space
O(n)
// build parent map, then ancestor traversal

Tradeoff: Works but uses O(n) space.

2. Recursive single-pass

Recurse. Return non-null if p or q found, or LCA. If both children non-null, current is LCA.

Time
O(n)
Space
O(h) recursion)
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: Single DFS pass. The recursion returns 'something found below me' — if both sides find something, the current node is the LCA.

Workday-specific tips

Workday wants the single-pass recursion. The key insight: 'I return non-null if I contain p, q, or their LCA below me'. If BOTH children return non-null, I AM the LCA. Articulate this before coding.

Common mistakes

  • Searching for p and q separately, then walking up — works but two passes.
  • Returning the deeper child instead of the current node when both sides match.
  • Not handling the case where p is an ancestor of q (or vice versa) — the recursion handles this naturally.

Follow-up questions

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

  • LCA of BST (LC 235) — exploit ordering.
  • LCA with parent pointers.
  • LCA of multiple (>2) 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

Why return root === p?

If we find p, we return it — that's a 'token' indicating 'I contain p'. Same for q. The actual LCA detection happens when both subtrees return non-null tokens.

What if p is ancestor of q?

When we hit p, we return p immediately. The other child returns null. We propagate p up — and since the LCA IS p, the answer bubbles correctly.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →