Lowest Common Ancestor of a Binary Tree

Given the root of a binary tree and two node values p and q (both guaranteed to exist, all node values are unique), return the value of their lowest common ancestor (LCA) — the deepest node that has both p and q as descendants (a node is a descendant of itself).

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

Recurse; return a node when it equals p or q.

If both children return a non-null result, the current node is the split point — the LCA.

If only one child returns something, pass that result up.

Common doubts

A node is a descendant of itself, so dfs returns p as soon as it matches, and p is the LCA.

It means one target lies in the left subtree and the other in the right, so the current node is the deepest that has both as descendants.

It records the root-to-target path for each and returns the last node their paths share.

Interview follow-ups

· What an interviewer asks next.

On a BST you can walk down comparing values: go left if both targets are smaller, right if both larger, else you're at the LCA (LeetCode 235).

Preprocess with binary lifting or Euler tour + sparse table for O(log n) or O(1) per query.

Fun facts

The 'return match, split when both sides report' recursion is one of the most elegant tree algorithms.
On a BST the LCA is found without any auxiliary structure, just by comparing values on the way down.

Asked at

AmazonFacebookMicrosoftGoogle

Frequently Sometimes Occasionally

Example 1

Input: root = [3, 5, 1, 6, 2, 0, 8], p = 5, q = 1
Output: 3
5 and 1 sit in different subtrees of 3, which is their lowest common ancestor.

Example 2

Input: root = [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], p = 5, q = 4
Output: 5
4 is a descendant of 5, and a node is a descendant of itself, so the LCA is 5.

Constraints

- The number of nodes is in the range [2, 10^5] - -10^9 <= Node.val <= 10^9 - All Node.val are unique - p != q is not required; both p and q exist in the tree

The lowest common ancestor is the deepest node from which p and q sit in different subtrees (or which is itself one of them). A single postorder recursion finds it: return a node if it is p or q; otherwise, if p and q surface from both children, this node is the LCA; if they surface from only one side, pass that result up.

Prerequisites

Before you start

· Concepts used directly in the solution.

Postorder recursion. Combine child results at the parent.

Descendant relation. A node is a descendant of itself; the LCA may be p or q.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Are values unique?”

Yes — each node has a distinct value, so a value identifies a node.

“Are p and q guaranteed present?”

Yes, both exist in the tree.

The ideal opening — say it like this

I recurse and return a node if it matches p or q; otherwise I combine the results from both children.

If both children report a find, the current node is the split point — the LCA; if only one does, I pass it upward.

Understand the problem

Worked example — tree [3, 5, 1, 6, 2, 0, 8], p = 5, q = 1

         3
        / \
       5   1
      / \ / \
     6  2 0  8
dfs(5) returns 5 (matches p) ; dfs(1) returns 1 (matches q)
at node 3: L=5, R=1 both non-null -> 3 is the LCA
answer: 3

Key observations

1Aha

A match short-circuits

Returning the node as soon as it equals p or q lets an ancestor detect 'this side contains a target'.

2Aha

Both sides non-null ⇒ split point

If both children return something, the targets diverge here, so this node is the LCA.

3Aha

One side non-null ⇒ bubble up

When only one child returns a node, that's either the LCA found deeper or a lone target being carried toward its partner.

Brute force vs optimal

	Root-to-node paths	Single postorder recursion
Idea	Find both paths, take last shared node	Return matches; both sides non-null = LCA
Time	O(n)	O(n)
Space	O(n)	O(height)

Both are O(n); the recursion needs no explicit paths. Full code is in the Approaches selector below.

Summary

Key takeaway

Recurse: return a node if it is p or q; if both children return non-null, this node is the LCA; otherwise bubble up the single non-null result. O(n) time, O(height) space.

dfs(node):
    if node is null or node.val in {p, q}: return node
    L = dfs(left); R = dfs(right)
    if L and R: return node
    return L or R