medium

Lowest Common Ancestor of a Binary Tree

Given the root of a binary tree and two nodes p and q that both exist in it, return their lowest common ancestor: the deepest node that has both p and q as descendants (a node counts as its own descendant).

Constraints

2 ≤ number of nodes ≤ 10^5
All node values unique
p and q exist in the tree

Examples

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

out: 3

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

out: 5

Recognition clues

Answer depends on whether p and q fall in different subtrees
Post-order: each subtree reports "found p or q here"
The first node whose left and right both report a hit is the LCA

Pattern

Tree Traversal

Nearly every tree problem is a traversal with the right information passed down (bounds, depth) or returned up (height, best path through this node). Inorder on a BST yields sorted order, which solves kth-smallest and validation; BFS with a queue yields levels.

Binary Tree Depth-First Search (DFS)Recursion & Backtracking Divide and Conquer

Solution

Recurse: if the current node is null, p or q, return it. Otherwise ask the left and right subtrees. If both return non-null, the targets are split across the subtrees and the current node is the LCA. If only one side returns non-null, propagate that result upward — it is either the LCA already found or the single target seen so far.

time O(n)space O(h)

Alternative approaches

With parent pointers, walk up from p collecting ancestors in a set, then walk up from q. For many queries, binary lifting answers each in O(log n) after O(n log n) preprocessing.

Code it yourself

Solve in

Hints:

Learn Binary Tree ▶ Visualize