#136

Lowest Common Ancestor of a Binary Tree

medium

treedepth-first-searchbinary-tree

Given the root of a binary tree and two values p and q present in it, return the value of their lowest common ancestor — the deepest node that has both p and q somewhere in its subtree.

A node is allowed to be a descendant of itself, so if p is an ancestor of q, then p is the answer. All node values are unique.

The tree is given as a level-order array where null marks a missing child. (LeetCode returns the ancestor node; here we return its value, since values are unique.)

Example

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

Output: 3

5 and 1 are in different subtrees of the root, so the root 3 is their LCA.

Constraints

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

Intuition

The lowest common ancestor of p and q is the deepest node having both somewhere in its subtree (a node may be its own ancestor). A direct approach finds the root-to-p path and the root-to-q path as lists, then walks both from the top and returns the last node they share.

function lowestCommonAncestor(root, p, q) {
  // Build the list of values from root down to a target.
  const pathTo = (node, target, trail) => {
    if (!node) return null;
    trail.push(node.val);
    if (node.val === target) return [...trail];
    const found = pathTo(node.left, target, trail) || pathTo(node.right, target, trail);
    trail.pop(); // backtrack before trying the sibling
    return found;
  };
  const pathP = pathTo(root, p, []);
  const pathQ = pathTo(root, q, []);
  // The last position where the two paths agree is the LCA.
  let lca = root.val;
  for (let i = 0; i < Math.min(pathP.length, pathQ.length); i++) {
    if (pathP[i] === pathQ[i]) lca = pathP[i];
    else break;
  }
  return lca;
}

Brute force — find both root-to-node paths, then compare them for the last common node: O(n) time, O(n) space.

That's two full traversals plus two stored paths. Can we do it in one pass with no path lists?

The key observation: a single post-order recursion can report, for each node, whether p or q (or their join point) lies in its subtree. A node is the LCA exactly when one target is found in its left subtree and the other in its right — or when the node itself is a target and the other lies below it. Because the recursion bubbles up the first node that sees both, that node is the lowest such ancestor.

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

Left subtree (rooted at 5): the search finds 5 here → the left call returns non-null (5).
Right subtree (rooted at 1): the search finds 1 here → the right call returns non-null (1).
At the root 3: both children returned non-null → the targets split across the two sides, so 3 is the LCA.

For p = 5, q = 4 instead: 4 lies inside 5's subtree, so the recursion finds 5 first (at the top of that subtree) and never needs to look deeper — 5 is its own answer.

The mechanic is "which side did each target come back on" — a branching decision over subtrees, not a scan, so the trace narrates the bubble-up rather than using a lane.
This reframe returns the LCA node's value (values are unique by constraint); LeetCode returns the node itself, but the recursion is identical.

Optimization

Single post-order recursion

Recurse so each node reports back whether it found p or q (or their LCA) in its subtree. A node is the LCA when its two children's reports are both non-null — meaning one target lies on each side — or when the node itself is one target and the other is found below it.

Because the recursion bubbles up the first node that "sees" both targets, the first such node encountered on the way up is the lowest common ancestor.

O(n) time (one pass), O(h) recursion space.

function lowestCommonAncestor(root, p, q) {
  // Returns the node where p and q's paths join, or whichever target this subtree contains.
  const find = (node) => {
    if (!node) return null;
    if (node.val === p || node.val === q) return node; // found a target here
    const left = find(node.left);
    const right = find(node.right);
    // Targets split across both children: this node is the LCA.
    if (left && right) return node;
    // Otherwise bubble up whichever side found something.
    return left || right;
  };
  return find(root).val;
}

Complexity analysis

Time complexity: O(n). Here's why:

One post-order pass visits each node at most once, doing O(1) work.

So O(n) — a single traversal, versus the brute force's two path-finding passes.

Space complexity: O(h). Here's why:

Only the recursion stack, depth equal to the tree height h.

O(log n) balanced, O(n) worst case. No path lists are stored.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
root = [9,5]59p = 9q = 5	9	The root is an ancestor of its child, so it's the LCA.
root = [10,20,30,40,50,60,70]40205010603070p = 40q = 50	20	40 and 50 are the two children of 20 — their LCA.
root = [10,20,30,40,50,60,70]40205010603070p = 40q = 70	10	Targets in opposite subtrees → the root.
root = [8,null,6,null,4,null,2]8642p = 6q = 2	6	On a right spine, the shallower target 6 is the ancestor of 2.
root = [10,20,30,40,50,60,70]40205010603070p = 60q = 70	30	60 and 70 are 30's two children, so 30 is their LCA.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor