Trees crash course ↗ · 174

236. Lowest Common Ancestor of a Binary Tree

With no BST ordering to guide you, find the lowest common ancestor by a single post-order DFS: each call returns p, q, or null upward, and the first node that hears back from both subtrees is the answer.

● MediumTree DFSRecursionTypeScript

PROBLEM What we're solving

Given the root of a binary tree (not a BST) and two distinct nodes p and q, return their lowest common ancestor — the deepest node that has both as descendants (a node is a descendant of itself). For the tree [3,5,1,6,2,0,8,null,null,7,4] with p=5, q=1 the answer is 3; with p=5, q=4 it is 5 (an ancestor of itself, since 4 lives beneath 5).

KEY IDEA Let each subtree report back, then merge

Insight → without ordering you can't pick a direction, so search everywhere — but recursion does the bookkeeping. Define the recursive call to return a node if p or q is found in that subtree (else null). At each node, look at what your left and right calls returned: if both came back non-null, p and q are split across this node, so this node is the LCA. Otherwise bubble up whichever single side was non-null.

RECIPE Base case, recurse, merge

0 · Base case. If the node is null, return null — nothing here.
1 · Hit on p or q. If this node isa target, return it immediately. You don't need to keep searching below it — a node is its own descendant, so it can be the ancestor.
2 · Recurse both sides. Compute left = lca(node.left) and right = lca(node.right). This is the post-order step: you decide after the children answer.
3 · Merge. If left and right are both non-null, the targets straddle this node → return node. Otherwise return the one non-null side (or null if neither found anything).

Classic confusion → returning a target on contact looks like it could miss the case where p is an ancestor of q. It doesn't: when the recursion reaches p, it returns p up without descending, and since q is somewhere beneath it, the higher ancestors only ever see one non-null side — so the answer stays p. This relies on the problem's guarantee that both p and q exist in the tree.

COST Complexity & alternatives

Find both root-to-node paths

O(n) time / O(n) space

Two searches + store both paths, then compare.

Single post-order DFS

O(n) time / O(h) space

One pass; O(h) recursion stack, h = height.

Why O(n) / O(h)

In the worst case you visit every node once, so time is O(n). The only extra memory is the recursion stack, which is as deep as the tree's height h — O(log n) for a balanced tree, O(n) for a degenerate one. You cannot do better than O(n) here because, lacking ordering, any node could be the answer until proven otherwise.

Pattern transfer → in a BST (LC 235) you skip all this: the ordering tells you which way to turn, so you walk down once until p and q split, in O(h) time and O(1)space — no recursion needed. Here, with no order, the "ask both children, then merge" post-order shape is the same backbone used by Diameter of a Binary Tree, Maximum Path Sum, and Balanced Binary Tree: each returns a small summary upward and the parent combines them.

RUN IT Recurse both sides; the node that hears from both is the LCA

tree (level-order)p =q =

step 0 / 7

STARTPost-order DFS for the lowest common ancestor of p=5 and q=1. Each call returns p, q, or null upward; the first node that hears back from both sides is the LCA.

1class TreeNode {
2  val: number;
3  left: TreeNode | null;
4  right: TreeNode | null;
5  constructor(val: number) {
6    this.val = val;
7    this.left = null;
8    this.right = null;
9  }
10}
11 
12function lowestCommonAncestor(
13  root: TreeNode | null,
14  p: TreeNode,
15  q: TreeNode,
16): TreeNode | null {
17  if (root === null) return null;        // fell off the tree
18  if (root === p || root === q) return root; // found p or q -> bubble it up
19▶ 
20▶  const left = lowestCommonAncestor(root.left, p, q);
21  const right = lowestCommonAncestor(root.right, p, q);
22 
23  if (left && right) return root;        // p and q on opposite sides -> LCA
24  return left ?? right;                  // both on one side (or neither)
25}

State

(empty)

call stack

targets p, qcurrent node / bubbled resultfound target / LCAcall stack

slowfast

TYPESCRIPT The solution, annotated

lowestCommonAncestor.ts
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode,
): TreeNode | null {
  if (root === null) return null;            // fell off the tree
  if (root === p || root === q) return root; // found p or q -> bubble it up

  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  if (left && right) return root;            // p and q on opposite sides -> LCA
  return left ?? right;                      // both on one side (or neither)
}

Reading it block by block

Base case. A null node contributes nothing, so return null. This terminates the recursion below the leaves.

Found a target. If root === p || root === q, return root at once. We compare by node identity, not value, and stop descending — a node is its own descendant, so it can still be the LCA if the other target lies beneath it.

Recurse both sides. Ask the left subtree and the right subtree what they found. Because we use the results after both calls return, this is a post-order traversal.

Merge the answers. If left and right are both non-null, the two targets are on opposite sides of this node, so this node is the LCA — return it. Otherwise exactly one side (or neither) found a target, so bubble that side up with left ?? right.

Complexity → O(n) time — every node is visited at most once. O(h) space for the recursion stack, where h is the tree height: O(log n) for a balanced tree, O(n) for a degenerate one.

INTERVIEWFollow-ups they'll ask

"What if it were a BST?" Use LC 235: the ordering lets you walk down once toward both values until they split, in O(h) time and O(1) space — no recursion.
"What if p or q might not be in the tree?"The bubble-up shortcut can return a target that's present even if the other is absent. Track found-counts (or do a full post-order without the early return) and verify both were seen before trusting the result.
"Nodes have parent pointers?" Walk both nodes up to equal depth, then advance together until they meet — O(h) time, O(1) space, no full traversal.
"Many repeated queries on the same tree?" Preprocess with binary lifting or Euler tour + sparse table / RMQ for O(log n) (or O(1)) per query after O(n log n) setup.
"Why compare by identity, not value?" The signature gives you the actual TreeNode objects; comparing references avoids ambiguity if values were ever duplicated.

OPTIMAL Tree DFS

lowestCommonAncestor.ts
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode,
): TreeNode | null {
  if (root === null) return null;            // fell off the tree
  if (root === p || root === q) return root; // found p or q -> bubble it up

  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  if (left && right) return root;            // p and q on opposite sides -> LCA
  return left ?? right;                      // both on one side (or neither)
}

Complexity → O(n) time — every node is visited at most once. O(h) space for the recursion stack, where h is the tree height: O(log n) for a balanced tree, O(n) for a degenerate one.

ALT 1 Find both root-to-node paths, then compare

O(n) time · O(n) space

Record the full path from the root to p and to q, then walk both lists together and return the last node they share — conceptually simple, but it stores two paths and may traverse twice.

approach-2.ts
function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode,
): TreeNode | null {
  function findPath(target: TreeNode): TreeNode[] | null {
    const path: TreeNode[] = [];
    function dfs(node: TreeNode | null): boolean {
      if (!node) return false;
      path.push(node);
      if (node === target) return true;
      if (dfs(node.left) || dfs(node.right)) return true;
      path.pop();
      return false;
    }
    return dfs(root) ? path : null;
  }

  const pathP = findPath(p);
  const pathQ = findPath(q);
  if (!pathP || !pathQ) return null;

  let lca: TreeNode | null = null;
  for (let i = 0; i < pathP.length && i < pathQ.length; i++) {
    if (pathP[i] === pathQ[i]) lca = pathP[i];
    else break;
  }
  return lca;
}

Note → Same asymptotic time, but it materialises two paths (O(n) extra space) and can scan the tree twice. The one-pass post-order solution decides on the way back up with only O(h) stack space.

MNEMONIC The one-liner

"Hit p or q? return it. Both sides come back non-null? you are the LCA. Otherwise bubble up the one side."

TRIGGERS When you see _ → reach for _

LCA in a plain binary tree (no BST order)	post-order DFS, return p/q/null
node is p or q	return it immediately (a node is its own descendant)
left and right both non-null	this node is the LCA
only one side non-null	bubble that side up (left ?? right)

SKELETON The reusable shape

skeleton.ts
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;   // split -> LCA
  return left ?? right;             // bubble up the one side
}

FLASHCARDS Tap to flip

What does each recursive call return?

The node p or q if found in that subtree, the LCA if both were found below, otherwise null.

tap to flip

1 / 6

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

Which traversal order does the standard LC 236 solution use?

QUESTION 02

A node returns itself as the LCA exactly when:

QUESTION 03

Optimal time complexity?

QUESTION 04

Extra space used by the recursive solution?

QUESTION 05

For [3,5,1,6,2,0,8,null,null,7,4] with p=5, q=1, the LCA is:

QUESTION 06

For the same tree with p=5, q=4, the LCA is:

QUESTION 07

Why does returning a target on contact still work when p is an ancestor of q?

QUESTION 08

#236 · Lowest Common Ancestor of a Binary TreeFind the deepest node that has both p and q as descendants with a single post-order recursion: a node whose left and right subtrees each return a target is the LCA; otherwise bubble up whichever side found one. No BST property needed.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Let each subtree report back, then merge

RECIPE Base case, recurse, merge

COST Complexity & alternatives

Why O(n) / O(h)

RUN IT Recurse both sides; the node that hears from both is the LCA

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Tree DFS

ALT 1 Find both root-to-node paths, then compare

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _