Diameter of a tree

The problem, simply

You get a binary tree. A path is a walk along the branches from one node to another, never using a branch twice. Its length is the number of branches (edges) it uses.

The diameter is the length of the longest path in the tree. That path does not have to go through the root.

Some books count nodes instead of edges. Then the answer is one more. Ask which one the interviewer wants. Here we count edges, like LeetCode 543.

A story to remember it

Picture it

Examples

Way 1: the simple way

At every node, measure the height of the left side and of the right side from scratch. Their sum is the longest path bending at that node. Keep the biggest one over all nodes.

1. height(n) is 0 for an empty node, else 1 + max(height(left), height(right)).
2. At each node, the path bending here is height(left) + height(right).
3. The answer is the biggest of that value, the left side's answer and the right side's answer.

class Solution {
    public int diameter(TreeNode root) {
        if (root == null) return 0;
        int here = height(root.left) + height(root.right);   // bends at root
        return Math.max(here, Math.max(diameter(root.left), diameter(root.right)));
    }

    private int height(TreeNode n) {
        if (n == null) return 0;
        return 1 + Math.max(height(n.left), height(n.right));
    }
}

How long it takes: every node measures everything below it again. In a stick shaped tree that is O(n^2). Extra room: the waiting helpers, O(h).

Way 2: the clever way

Measure each height once, from the bottom up, and check the bending path at the same time. The helper returns a height, and it updates a "best so far" on the side.

1. An empty spot returns height 0.
2. Get the left height L and the right height R.
3. The path bending here has L + R edges. If it beats best, save it.
4. Return 1 + max(L, R) to the parent.

class Solution {
    private int best;

    public int diameter(TreeNode root) {
        best = 0;
        height(root);
        return best;
    }

    // returns the height, and checks the path that bends at n
    private int height(TreeNode n) {
        if (n == null) return 0;
        int left = height(n.left);
        int right = height(n.right);
        best = Math.max(best, left + right);   // edges in the path bending here
        return 1 + Math.max(left, right);
    }
}

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

Watch out for

• Edges or nodes. With heights counted in nodes, left + right is the number of edges. If the problem wants nodes, return best + 1.
• Only checking the root. The longest path may bend anywhere.
• Forgetting to reset best between calls when it is a field.

What interviewers ask next

• Return the path itself? Also remember which node gave the best bend, then walk down the taller side twice from it.
• Maximum path sum (values can be negative)? Same shape: return the best downward sum (never below 0), and update the best with node + left + right. That is LeetCode 124.
• Diameter of a general tree or a graph that is a tree? Run a search from any node to find the farthest node a, then search from a. The farthest distance from a is the diameter.
• Longest path where all values are equal? Same idea, but a side counts only when the child has the same value (LeetCode 687).

Remember this

Grown-up words: the rope is a path, its length in branches is the number of edges, the longest one is the diameter, the bend is the path's topmost node, and asking children first is post order traversal.