Skip to main content

79. Lowest Common Ancestor of a Binary Tree

mediumAsked at Reddit

Find the lowest common ancestor of two nodes in a binary tree. Reddit uses this canonical LCA problem to test post-order recursion — the same shape they use to find the nearest common parent comment when merging conflicting moderator threads.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit comments-team on-site question.
  • Blind (2025-11)— Reported as a Reddit canonical.

Problem

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. The lowest common ancestor is defined between two nodes p and q 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).

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

Explanation: 5 is itself an ancestor.

Approaches

1. Find paths to both, compare

DFS from root to p, then to q. Compare paths; deepest common node is LCA.

Time
O(n)
Space
O(n)
// Works but multi-pass and O(n) extra for two path arrays.

Tradeoff: Two passes; memory overhead.

2. Post-order recursion (optimal)

Recurse left and right. If both return non-null, current node is LCA. Else return the non-null one.

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: Single-pass, elegant. The key insight: 'if I see both, I'm the LCA'.

Reddit-specific tips

Reddit interviewers grade on the post-order single-pass elegance. Bonus signal: explain the recurrence verbally — 'if my left subtree contains one and right contains the other, I'm the meeting point'.

Common mistakes

  • Returning the first match instead of the meeting point.
  • Forgetting the base case root === p || root === q.
  • Comparing values instead of node references.

Follow-up questions

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

  • LCA in BST (LC 235) — O(h) with property.
  • LCA with parent pointers — two-pointer up.
  • LCA of multiple 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 post-order?

We need information from both subtrees before deciding the current node. Pre-order can't see the right subtree yet.

Does the BST version benefit?

Yes — LCA in BST is O(h) using value comparison: descend left if both p, q < root.val; right if both > root.val; else current is LCA.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →