Lowest Common Ancestor of a Binary Tree

Given a binary tree with unique values and two values p and q that are both in the tree, return the lowest common ancestor (LCA): the deepest node that has both p and q as descendants. A node counts as a descendant of itself.

LeetCode: 236. Lowest Common Ancestor of a Binary Tree

Example

graph TB
    a3["3"] --> a5["5"]
    a3 --> a1["1"]
    a5 --> a6["6"]
    a5 --> a2["2"]
    a1 --> a0["0"]
    a1 --> a8["8"]
    a2 --> a7["7"]
    a2 --> a4["4"]

Text

lca(5, 1) = 3
lca(5, 4) = 5   (5 is an ancestor of 4, and of itself)
lca(6, 4) = 5

This tree is not a BST, so the BST shortcut of comparing values with the node doesn't apply.

Brute force: compare the two root paths

Find the path from the root to p and the path from the root to q. Both start at the root, and they share nodes until they split. The last shared node is the LCA.

Text

path(6) = 3 -> 5 -> 6
path(4) = 3 -> 5 -> 2 -> 4
                ^ last shared node

A tree node is an object with an int val and two reference fields, left and right. A missing child is null, and the empty tree is a null root. OptionalInt is a container that holds either one int or nothing, so a method can report "no answer" without returning null.

Java

import java.util.ArrayList;
import java.util.List;
import java.util.OptionalInt;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static TreeNode node(int val, TreeNode left, TreeNode right) {
        return new TreeNode(val, left, right);
    }

    static TreeNode leaf(int val) {
        return new TreeNode(val, null, null);
    }

    // Adds the values from root to target to path; returns false if target is not found.
    static boolean findPath(TreeNode root, int target, List<Integer> path) {
        if (root == null) return false;
        path.add(root.val);
        if (root.val == target || findPath(root.left, target, path) || findPath(root.right, target, path)) {
            return true;
        }
        path.remove(path.size() - 1);
        return false;
    }

    static OptionalInt lca(TreeNode root, int p, int q) {
        List<Integer> pathP = new ArrayList<>();
        List<Integer> pathQ = new ArrayList<>();
        if (!findPath(root, p, pathP) || !findPath(root, q, pathQ)) {
            return OptionalInt.empty();
        }
        int i = 0;
        while (i < pathP.size() && i < pathQ.size() && pathP.get(i).equals(pathQ.get(i))) {
            i++;
        }
        return OptionalInt.of(pathP.get(i - 1)); // the root is always shared, so i >= 1
    }

    public static void main(String[] args) {
        TreeNode root = node(3, node(5, leaf(6), node(2, leaf(7), leaf(4))), node(1, leaf(0), leaf(8)));
        System.out.println(lca(root, 5, 1) + " " + lca(root, 5, 4) + " " + lca(root, 6, 4));
        System.out.println(lca(root, 5, 99)); // 99 is not in the tree
    }
}

Output

OptionalInt[3] OptionalInt[5] OptionalInt[5]
OptionalInt.empty

The comparison uses equals because List<Integer> holds boxed Integer objects, and == on them compares references.

Time: O(n): at most two traversals. Space: O(h) for the paths and the recursion.

Optimal: one post-order recursion

Search for both values at once. At each node:

If the node is p or q, return it: the LCA is this node or above it.
Otherwise, search both subtrees. If both return something, p and q are on different sides, so this node is the LCA. If only one side returns something, pass it up.

Java

import java.util.OptionalInt;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static TreeNode node(int val, TreeNode left, TreeNode right) {
        return new TreeNode(val, left, right);
    }

    static TreeNode leaf(int val) {
        return new TreeNode(val, null, null);
    }

    static OptionalInt lca(TreeNode root, int p, int q) {
        if (root == null) return OptionalInt.empty();
        if (root.val == p || root.val == q) return OptionalInt.of(root.val);
        OptionalInt left = lca(root.left, p, q);
        OptionalInt right = lca(root.right, p, q);
        if (left.isPresent() && right.isPresent()) return OptionalInt.of(root.val);
        return left.isPresent() ? left : right;
    }

    public static void main(String[] args) {
        TreeNode root = node(3, node(5, leaf(6), node(2, leaf(7), leaf(4))), node(1, leaf(0), leaf(8)));
        System.out.println(lca(root, 5, 1) + " " + lca(root, 5, 4) + " " + lca(root, 6, 4));
        System.out.println(lca(root, 5, 99)); // 99 is not in the tree: the result is wrong
    }
}

Output

OptionalInt[3] OptionalInt[5] OptionalInt[5]
OptionalInt[5]

Time: O(n): one traversal. Space: O(h) for the recursion.

Returning early at p is safe because both values are guaranteed to be in the tree: if q is below p, then p is the answer; if not, the other side of some ancestor will find q.

Edge cases

One value is an ancestor of the other: that value is returned.
A value that is not in the tree: the optimal version returns the other value, which is wrong, as the last line of the example shows. If that can happen, use the path version, which returns an empty result, or count how many of the two values were found during the recursion.
p == q: the node itself.