Diameter of a Binary Tree

Given the root of a binary tree, return its diameter: the number of edges on the longest path between any two nodes. The path doesn't have to go through the root.

LeetCode: 543. Diameter of Binary Tree

Example

Text

      1
     / \
    2   3        Output: 3   (4 -> 2 -> 1 -> 3, or 5 -> 2 -> 1 -> 3)
   / \
  4   5

The longest path through a node goes down its left subtree as far as possible and down its right subtree as far as possible: depth(left) + depth(right) edges, where depth counts the nodes on the longest downward path.

Brute force: heights at every node

For every node, compute the depths of both subtrees and take the best sum. Each depth call walks its whole subtree again.

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.

Java

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 int depth(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(depth(root.left), depth(root.right));
    }

    static int diameter(TreeNode root) {
        if (root == null) return 0;
        int throughHere = depth(root.left) + depth(root.right);
        return Math.max(throughHere, Math.max(diameter(root.left), diameter(root.right)));
    }

    public static void main(String[] args) {
        TreeNode root = node(1, node(2, leaf(4), leaf(5)), leaf(3));
        System.out.println(diameter(root) + " " + diameter(node(1, leaf(2), null)));
    }
}

Output

3 1

Time: O(n²) for a skewed tree (O(n log n) for a balanced one). Space: O(h).

Optimal: one post-order pass

Compute the depth bottom-up, as in Find the Height of a Binary Tree, and use the two child depths at each node to update the best diameter on the way. Java passes an int by value, so a method cannot update the caller's int. The code shares the running best through a one-element int[] that every call can modify.

Java

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);
    }

    // Returns the depth of root, and updates best[0] with the longest path through any node below it.
    static int depth(TreeNode root, int[] best) {
        if (root == null) return 0;
        int left = depth(root.left, best);
        int right = depth(root.right, best);
        best[0] = Math.max(best[0], left + right);
        return 1 + Math.max(left, right);
    }

    static int diameter(TreeNode root) {
        int[] best = {0};
        depth(root, best);
        return best[0];
    }

    public static void main(String[] args) {
        TreeNode root = node(1, node(2, leaf(4), leaf(5)), leaf(3));
        System.out.println(diameter(root) + " " + diameter(node(1, leaf(2), null)));

        // The longest path stays inside the left subtree: 8 -> 6 -> 4 -> 2 -> 5 -> 7 -> 9.
        TreeNode deep = node(1,
            node(2, node(4, node(6, leaf(8), null), null), node(5, null, node(7, null, leaf(9)))),
            leaf(3));
        System.out.println(diameter(deep));
    }
}

Output

3 1
6

Time: O(n). Space: O(h).

Edge cases

Empty tree or single node: 0.
Path that avoids the root: found at the node where the path turns, as in the last example.
Counting nodes instead of edges: add 1.