LCA in BT

Hard TUF ID 118 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the root of a binary tree and two nodes p and q that are both in the tree. Return their lowest common ancestor (LCA): the deepest node that has both p and q in its subtree. A node counts as being in its own subtree, so if p is an ancestor of q, the answer is p itself.

Constraints (LeetCode): up to 10^5 nodes, all values distinct, p != q (we also handle p == q), and both nodes exist. This is a plain binary tree, not a binary search tree, so values tell us nothing about where a node is.

Example 1

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

p = 5, q = 1   ->  3

5 is in the left subtree of 3 and 1 in the right one, so the paths split at the root.

Example 2

Same tree, p = 5, q = 4. The answer is 5: it is an ancestor of 4 and an ancestor of itself, and no deeper node contains both.

Approach 1: Brute force, compare the two root paths

Intuition. The ancestors of a node are exactly the nodes on the path from the root to it. So the common ancestors of p and q are the nodes that appear on both root paths. In a tree, two root paths start together, agree for a while, and once they split they never meet again. The common ancestors are therefore a shared prefix, and the lowest one is the last node of that prefix.

Finding a root-to-node path is a DFS that appends each node on the way down, stops as soon as it finds the target, and removes a node again if the target was not below it.

Algorithm.

Find pathP from the root to p and pathQ from the root to q.
Walk both lists from index 0 while the nodes are the same object.
The last equal node is the LCA.

static TreeNode bruteForce(TreeNode root, TreeNode p, TreeNode q) {
    List<TreeNode> pathP = new ArrayList<>(), pathQ = new ArrayList<>();
    if (!pathTo(root, p, pathP) || !pathTo(root, q, pathQ)) return null;
    TreeNode lca = null;
    for (int i = 0; i < pathP.size() && i < pathQ.size() && pathP.get(i) == pathQ.get(i); i++) {
        lca = pathP.get(i);                                   // still on the shared prefix
    }
    return lca;
}

static boolean pathTo(TreeNode node, TreeNode target, List<TreeNode> path) {
    if (node == null) return false;
    path.add(node);
    if (node == target) return true;
    if (pathTo(node.left, target, path) || pathTo(node.right, target, path)) return true;
    path.remove(path.size() - 1);                             // target is not below this node
    return false;
}

Complexity. Time O(n): each path search visits every node at most once, and the comparison is O(h). Space O(h) for each path plus O(h) recursion, which is O(n) for a skewed tree.

It is already linear, but it walks the tree twice and stores two lists. The other approaches trade those costs differently.

Approach 2: Parent pointers and an ancestor set

Intuition. If every node knew its parent, we could walk upward instead of searching downward. Record parents with one BFS. Then climb from p to the root, putting every node (including p) into a set: that set is “all ancestors of p”. Finally climb from q. The first node we meet that is in the set is a common ancestor, and because we climb from the bottom, it is the lowest one.

This is the method of choice when nodes already store parent links, or when many LCA queries are asked on the same tree (the parent map is built once). It is also iterative, so very deep trees cannot overflow the call stack.

Algorithm.

BFS from the root, storing parent[child] = node for every edge.
Add p and all its ancestors to a set.
Starting at q, move to the parent until the current node is in the set; return it.

static TreeNode parentPointers(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return null;
    Map<TreeNode, TreeNode> parent = new HashMap<>();
    parent.put(root, null);
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node.left != null) { parent.put(node.left, node); queue.add(node.left); }
        if (node.right != null) { parent.put(node.right, node); queue.add(node.right); }
    }
    if (!parent.containsKey(p) || !parent.containsKey(q)) return null;
    Set<TreeNode> ancestorsOfP = new HashSet<>();
    for (TreeNode a = p; a != null; a = parent.get(a)) ancestorsOfP.add(a);   // p counts as its own ancestor
    for (TreeNode b = q; b != null; b = parent.get(b)) {
        if (ancestorsOfP.contains(b)) return b;               // first shared ancestor on the way up is the lowest
    }
    return null;
}

Complexity. Time O(n) to build the map, then O(h) for each climb. Space O(n) for the map and the set.

Approach 3: Optimal, one post-order recursion

Intuition. Ask each subtree a single question and let the answers bubble up: “what do you contain?” Define optimal(node) to return:

null if neither p nor q is in this subtree;
p or q if exactly one of them is in it;
the LCA if both are in it.

At a node, ask the left subtree and the right subtree. If both return something, p is on one side and q on the other, so this node is where their paths split: it is the LCA. If only one side returns something, pass that up unchanged; it is either one of the targets or an LCA already found deeper. If the node itself is p or q, return it immediately. That shortcut is correct even when the other target lies below it: in that case this node is the LCA, and no other branch will find anything, so this node’s return value travels all the way to the top.

Algorithm.

If root is null, p, or q, return root.
left = optimal(root.left), right = optimal(root.right).
If left is null, return right. If right is null, return left.
Otherwise return root.

static TreeNode optimal(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = optimal(root.left, p, q);
    TreeNode right = optimal(root.right, p, q);
    if (left == null) return right;
    if (right == null) return left;
    return root;                                              // p and q were found on different sides
}

Dry run with p = 7, q = 4 on the tree above:

node	left result	right result	returns
6	null	null	null
7	(is p)		7
4	(is q)		4
2	7	4	2 (split point)
5	null (from 6)	2	2
0, 8	null	null	null
1	null	null	null
3	2	null	2

The answer is 2.

Complexity. Time O(n): each node is visited at most once. Space O(h) for the recursion stack, and no extra data structures.

Edge cases and pitfalls

One node is the ancestor of the other. p = 5, q = 4 must return 5. Approach 3 handles it with the early return; Approach 1 because 5 is the last shared node; Approach 2 because p itself is in the ancestor set.
p == q. All three return that node.
A target that is not in the tree. Approach 3 assumes both exist. If only p is present it returns p, which looks like a valid answer. Approaches 1 and 2 check presence and return null. If the input does not guarantee presence, verify it first.
Compare nodes, not values. The code uses == on node references. Comparing values breaks as soon as two nodes share a value.
Deep trees. A chain of 10^5 nodes means 10^5 nested calls in Approaches 1 and 3, which can overflow the Java stack. The parent-pointer approach has no recursion.

LCA in BST uses ordering to walk straight down to the split point in O(h).
Print root to leaf path in BT teaches the root-to-node path used in Approach 1.
Print all nodes at a distance of K in BT reuses the parent-pointer idea from Approach 2.
Minimum time taken to burn the BT from a given Node combines parent pointers with a BFS.

LCA in BT

Problem

Approach 1: Brute force, compare the two root paths

Approach 2: Parent pointers and an ancestor set

Approach 3: Optimal, one post-order recursion

Edge cases and pitfalls

Related problems