Find LCA in a Binary tree

The problem, simply

You get a binary tree and two nodes in it, p and q. Find their lowest common ancestor: the deepest node that has both p and q somewhere below it (or is one of them).

A node counts as its own ancestor. So if p sits somewhere under q, the answer is q itself.

A story to remember it

Picture it

Examples

Way 1: the simple way

Write down the full way from the root to p, and the full way from the root to q. Walk both lists from the start together. The last spot where they are still the same is the answer.

1. Find the root to p path (go down, and back out of dead ends).
2. Find the root to q path.
3. Compare from the front. The last equal node is the lowest common ancestor.

import java.util.*;

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> toP = new ArrayList<>();
        List<TreeNode> toQ = new ArrayList<>();
        if (!findPath(root, p, toP) || !findPath(root, q, toQ)) return null;
        TreeNode answer = null;
        for (int i = 0; i < toP.size() && i < toQ.size(); i++) {
            if (toP.get(i) != toQ.get(i)) break;   // the ways split here
            answer = toP.get(i);
        }
        return answer;
    }

    private boolean findPath(TreeNode node, TreeNode target, List<TreeNode> path) {
        if (node == null) return false;
        path.add(node);
        if (node == target) return true;
        if (findPath(node.left, target, path) || findPath(node.right, target, path)) return true;
        path.remove(path.size() - 1);   // dead end, step back
        return false;
    }
}

How long it takes: two walks over the tree and one compare, O(n). Extra room: two paths and the call stack, each at most as long as the tree is tall, O(h). It is correct, but it walks the tree twice and keeps lists.

Way 2: the clever way

One walk, with every node reporting up, like the family reunion.

1. If the node is empty, report nothing.
2. If the node is p or q, report itself. There is no need to look below it: if the other one is below, this node is the answer anyway.
3. Ask the left side and the right side.
4. If both sides report something, p and q split here. Report this node.
5. Otherwise, pass up whatever the one non-empty side reported (or nothing).

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;   // nothing, or found one
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root;            // they split here
        return left != null ? left : right;                        // pass the news up
    }
}

How long it takes: each node is asked at most once, O(n). Extra room: the call stack, O(h).

Watch out for

• Compare nodes, not values, when values can repeat. root == p is safe; root.val == p.val is not.
• Stopping at p is correct only because of the "a node is its own ancestor" rule. Do not "fix" it by looking deeper.
• For a stick shaped tree with many nodes, recursion can overflow. Fill a child to parent map with a queue first, then use the parent pointer idea below. That has no deep recursion.

What interviewers ask next

• It is a binary search tree. Then you do not need to search both sides: if both values are smaller than the node go left, if both are bigger go right, otherwise this node is the answer. O(h) time, O(1) room.
• Nodes have parent pointers. Walk up from p and store its ancestors in a set, then walk up from q until you hit one. Or use the two pointer trick from "intersection of two linked lists".
• Many queries on the same tree. Preprocess with binary lifting (each node stores its 1st, 2nd, 4th, 8th ancestor) or an Euler tour with a range minimum table, then answer each query in O(log n) or O(1).
• Distance between two nodes: depth(p) + depth(q) - 2 * depth(lca).

Remember this

Grown-up words: the closest shared grandparent is the lowest common ancestor (LCA), reporting up after asking both children is a postorder depth first search, the waiting family members are the call stack, and jumping 1, 2, 4, 8 steps up at once is binary lifting.