Find distance between 2 nodes in a Binary tree

The problem, simply

You get a binary tree with all different values, and two values a and b that are both in the tree. Find the distance between them: the number of branches (edges) on the path from one to the other.

The path always goes up from a to some meeting node, then down to b. That meeting node is the lowest node that has both of them below it (or is one of them).

A story to remember it

Picture it

Examples

Way 1: the simple way

Write down the path from the root to a and the path from the root to b. They start the same and then split. The steps after the split are the answer.

1. Find the path from the root to a, as a list of nodes.
2. Find the path from the root to b.
3. Count how many nodes the two lists share at the start, i.
4. The distance is (pathA.size() - i) + (pathB.size() - i).

import java.util.*;

class Solution {
    public int findDist(TreeNode root, int a, int b) {
        List<TreeNode> pa = new ArrayList<>(), pb = new ArrayList<>();
        if (!path(root, a, pa) || !path(root, b, pb)) return -1;   // not found
        int i = 0;
        while (i < pa.size() && i < pb.size() && pa.get(i) == pb.get(i)) i++;
        return (pa.size() - i) + (pb.size() - i);
    }

    // fills 'path' with the nodes from n down to target
    private boolean path(TreeNode n, int target, List<TreeNode> path) {
        if (n == null) return false;
        path.add(n);
        if (n.val == target) return true;
        if (path(n.left, target, path) || path(n.right, target, path)) return true;
        path.remove(path.size() - 1);          // not this way, step back
        return false;
    }
}

How long it takes: two walks of the tree, O(n). Extra room: the two paths and the recursion, O(h).

Way 2: the clever way

Do it in one walk, from the bottom up. Each helper reports to its parent how many steps it is down to a target, or "none".

1. An empty spot reports none.
2. If this node is a target, report 0. If the other target is already below it, the answer is that distance + 1.
3. If both sides report a number, this node is the meeting point. The answer is (left + 1) + (right + 1).
4. If one side reports a number x, report x + 1. Otherwise report none.

class Solution {
    private int dist;

    public int findDist(TreeNode root, int a, int b) {
        if (a == b) return 0;
        dist = -1;
        down(root, a, b);
        return dist;
    }

    // steps from n down to a target below it, or -1 for none
    private int down(TreeNode n, int a, int b) {
        if (n == null || dist != -1) return -1;
        int l = down(n.left, a, b);
        int r = down(n.right, a, b);
        if (n.val == a || n.val == b) {
            int below = Math.max(l, r);              // is the other target under me?
            if (below != -1) dist = below + 1;
            return 0;
        }
        if (l != -1 && r != -1) {                    // the paths meet here
            dist = (l + 1) + (r + 1);
            return -1;
        }
        if (l != -1) return l + 1;
        if (r != -1) return r + 1;
        return -1;
    }
}

How long it takes: each node is visited at most once, O(n). Extra room: the waiting helpers, O(h).

Watch out for

• Comparing paths by value instead of by node. With unique values it works, but comparing the node objects is safer.
• Missing targets. If a or b may not be in the tree, check that both were found before trusting the answer.
• Same node twice. The distance is 0.

What interviewers ask next

• With a known lowest common ancestor L: distance = depth(a) + depth(b) - 2 * depth(L). Find L with the classic recursive LCA, then two depth searches.
• Many questions on the same tree? Precompute depths and use binary lifting, so each question costs O(log n) after O(n log n) setup.
• All nodes at distance k from a node? Mark each node's parent, then search outward from the node like a graph (LeetCode 863).
• In a binary search tree? The meeting point is the first node whose value lies between a and b, found by walking down from the root.

Remember this

Grown-up words: the shared relative is the lowest common ancestor (LCA), the steps are edges, the reports from the bottom are post order recursion, and -1 is the "none" sentinel.