Difficulty: MediumTrees

Lowest Common Ancestor of a Binary Tree

Problem in Plain English

Return the deepest node that is an ancestor of both given nodes in an arbitrary binary tree. A node counts as its own ancestor, and the result must be the original node object.

Problem Statement

Given the root of a binary tree and two distinct nodes p and q that exist in it, return their lowest common ancestor. The lowest common ancestor is the deepest node whose subtree contains both targets.

A node is a descendant of itself, so the answer may be p or q. This tree has no binary-search ordering: compare node identity, not values or left/right value ranges.

Constraints

2 <= number of nodes <= 10^5
-10^9 <= Node.val <= 10^9; node values are unique.
p != q; both node objects exist in the tree.

Examples

Example 1

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

The targets are in different root subtrees, so neither subtree contains both. Their first shared ancestor is the original root object 3.

Example 2

Input: root = [1,2], p = node 1, q = node 2
Output: node 1

In this minimum-size tree, the root is itself p and also the parent of q. A target may be the answer.

Example 3

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

The path from 4 goes through 2 and then 5. Since 5 counts as its own ancestor, the lowest shared ancestor is 5, not 3.

Intuition

Two nodes share the upper portion of their paths from the root. Walking upward from 5 and 1 in Example 1 reaches 3 first on both paths. Remember each node’s parent, mark the ancestors of p, then climb from q until its path first touches those marks. That first intersection is deeper than every later shared ancestor.

Approaches

Iterative Parent Map

Optimal

Solution Details

Reveal Iterative Parent Map: intuition, complexity, and code

Intuition

Intersect ancestor paths using a parent map. An explicit DFS stack avoids overflow on a chain of 100,000 nodes; this linear-time approach spends linear memory to keep traversal safe in all three languages. A recursive subtree search can use less memory on balanced trees but still needs linear stack depth on a chain.

Step-by-Step Logic

Record root 3 with no parent and push it onto the DFS stack.
Pop 3; record parent(5) = 3 and parent(1) = 3, pushing left then right children. Both targets are now discovered, so stop building the map.
Climb from p = 5, recording the objects 5 and 3 in an identity set.
Start at q = 1. It is not marked, so replace it with parent(1) = 3.
Object 3 is marked. Return that existing node object, whose value is 3.

Why It Works

The tree gives every non-root node exactly one parent, and DFS records that true parent before the child can be used. Discovering a target also records every parent on its route to the root. The ancestor set therefore contains exactly p and the nodes above it. Climbing from q tests its ancestors from deepest to shallowest. The first one in the set is common, and no deeper ancestor of q is common; every common ancestor must lie on q’s parent path. This proves it is the lowest common ancestor, including when a target is the answer.

Dry Run

Iterative Parent Map: variable states at each step
Phase	Current object	State change
Discover	3	parent(3) = null; stack [3]
Expand	3	parent(5) = 3, parent(1) = 3; both targets found
Mark p path	5 then 3	ancestors = {5, 3}
Climb q	1	absent; move to parent 3
Intersect	3	marked; return node 3

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

For n nodes, DFS discovers at most n objects and each upward walk visits at most n ancestors. Identity-map and set operations have expected constant cost. The parent map, DFS stack and ancestor set each occupy O(n) space; the tree is unchanged and no language call stack grows with its height.

Code

Solution.java

1import java.util.*;2
3// TreeNode (val, left, right) is supplied by the judge.4class Solution {5    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {6        Map<TreeNode, TreeNode> parent = new IdentityHashMap<>();7        Deque<TreeNode> stack = new ArrayDeque<>();8        parent.put(root, null);9        stack.push(root);10        while (!parent.containsKey(p) || !parent.containsKey(q)) {11            TreeNode node = stack.pop();12            if (node.left != null) {13                parent.put(node.left, node);14                stack.push(node.left);15            }16            if (node.right != null) {17                parent.put(node.right, node);18                stack.push(node.right);19            }20        }21        Set<TreeNode> ancestors = Collections.newSetFromMap(new IdentityHashMap<>());22        for (TreeNode node = p; node != null; node = parent.get(node)) ancestors.add(node);23        while (!ancestors.contains(q)) q = parent.get(q);24        return q;25    }26}

Hints

Hint 1

Picture the two paths from the root; where do they separate?

Hint 2

A parent map lets you follow either path backward without recursion.

Hint 3

Mark every ancestor of p, including p. The first marked object encountered while climbing from q is the answer.

Edge Cases

One target is the root, or is an ancestor of the other: return that target.
Targets in opposite root subtrees have the root as their LCA.
A 100,000-node chain requires explicit traversal storage rather than recursion.

Common Mistakes and Interview Tips

Applying BST value comparisons to an arbitrary binary tree skips valid subtrees.
Returning a new node with the right value fails the node-identity contract.
Excluding p from its own ancestor set misses an ancestor-target answer.
Stopping when only one target is discovered leaves the other parent path incomplete.

Key Takeaway

A parent map turns a rooted structure into upward paths. Their first intersection from either target gives the deepest shared ancestor without relying on value ordering.