leetExpert
Practice

Lowest Common Ancestor of a Binary Tree

Module 17 · Binary Trees

Problem

Given the root of a binary tree and two nodes p and q known to exist in it, find their lowest common ancestor (LCA) — the deepest node that has both p and q as descendants (a node is allowed to be a descendant of itself). This is a general binary tree — no ordering invariant, unlike a BST. (LeetCode 236.)

Examples

Example 1

Inputroot = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1Output3

Explanation. 5 and 1 sit in different subtrees of 3

Example 2

Inputroot = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4Output5

Explanation. 4 is under 5, so 5 is its own ancestor

text
      3
     / \
    5   1
   / \  / \
  6  2 0   8
    / \
   7   4

Constraints

2 ≤ n ≤ 10⁵ nodes · all values unique · p and q both exist and are distinct

Attempt it first

Without a BST's ordering invariant, you can't decide "go left or go right" the way Module 18's BST version of this problem will. The only information available is structural: does a subtree contain p, does it contain q, or does it contain both? Before opening anything, work out what a recursive function find(node) should return so that a parent, given its two children's return values, can determine whether it is the LCA — and try to state the exact condition precisely.