Faangprep Logo
Log inStart free
Browse curriculum

Lowest Common Ancestor of a Binary Tree

Find the deepest node that has both p and q as descendants with one depth-first pass.

MediumSolve on LeetCode

Problem Understanding

Lowest Common Ancestor of a Binary Tree: given the root of a binary tree and two of its nodes p and q, return their lowest common ancestor — the deepest node that has both p and q as descendants. A node counts as a descendant of itself, and both nodes are guaranteed to exist.

Example: in [3, 5, 1, 6, 2, 0, 8, null, null, 7, 4], the LCA of 5 and 1 is 3; the LCA of 5 and 4 is 5.

Attempt 1: Record Both Paths

Find the path from the root to p and the path to q (two depth-first searches), then walk both paths together; the last node they share is the LCA. It is correct and O(n), but it needs two searches and O(h) extra lists. One pass can do it if each subtree simply reports what it found.

The Intuition: Let Each Subtree Report Back

Ask every subtree one question: did you find p or q? Each call returns:

  1. null for an empty subtree.
  2. The node itself if it is p or q — there is no need to search below it.
  3. Otherwise, the answers from both children combined: if both sides found something, p and q are split across this node, so it is the LCA. If only one side found something, pass that up unchanged.

The first node to hear from both sides is the lowest one, because every call below it heard from at most one side.

Interactive Walkthrough

p = 5, q = 1 · → X = WHAT A CALL RETURNED

CALL

Stack depth

1

LCA

—

call stack

lca(3)

 

lca(3)

Next

Search 3's left subtree

Tree

p, q

p and q are labelled in the tree. The calls in progress are outlined from the root down to the running one, and each call's report appears under its node when it returns — so you can watch the answers flow up until one node hears from both sides.

The approach, step by step

  1. Base cases

    Return null for an empty subtree, and return the node itself when it is p or q.

  2. Ask both children

    Recurse into the left and right subtrees.

  3. Combine

    If both children returned a node, return the current node; otherwise return whichever result is not null.

Frequently asked questions

How do you find the lowest common ancestor in a binary tree?

Recurse from the root. A call returns null for an empty subtree and returns the node itself if it is p or q. Otherwise it asks both children: if both return something, this node is the LCA; if only one does, that result is passed up.

Why can the search stop when it reaches p or q?

If the other target is below that node, the node is the answer anyway, since a node counts as its own ancestor. If the other target is elsewhere, a higher node will hear from both sides and return itself instead.

How is this different from the LCA of a binary search tree?

In a BST, values tell you which way to go: walk down from the root until p and q fall on different sides, in O(h) time without exploring both subtrees. A general binary tree has no ordering, so both subtrees must be searched: O(n) time.