Diameter of Binary Tree

NeetCode: Diameter of Binary Tree · LeetCode: 543. Diameter of Binary Tree · Difficulty: Easy

The diameter is the number of edges on the longest path between any two nodes. The path may or may not pass through the root.

Example

Text

Input:  [1, 2, 3, 4, 5]    Output: 3    (4 -> 2 -> 1 -> 3)
Input:  [1, null, 2, null, 3]    Output: 2

Trees are given in LeetCode's level-order array form: the first value is the root, and each following pair of values holds the left and right child of the next node that exists, in the order the nodes were placed. null marks a missing child, and a missing node has no children listed. The tree(Integer...) helper in each program builds a TreeNode from such an array. TreeNode has the fields val, left, and right; a missing child is null, so no wrapper type is needed.

Brute force: height of both sides at every node

The longest path that turns at a node goes down its left side and down its right side, so its length is height(left) + height(right). Compute that for every node and keep the maximum. Heights are recomputed from scratch each time. A height here counts nodes, with 0 for a missing node.

Java

import java.util.ArrayDeque;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

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

    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int throughHere = height(root.left) + height(root.right);
        return Math.max(throughHere,
            Math.max(diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right)));
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.diameterOfBinaryTree(tree(1, 2, 3, 4, 5)));
        System.out.println(s.diameterOfBinaryTree(tree(1, null, 2, null, 3)));
    }
}

Output

3
2

Time: O(n²) in the worst case (a chain), since each node triggers a height computation. Space: O(h).

Optimal: one DFS that returns heights and updates the answer

The DFS already computes the height of every subtree. While returning 1 + max(left, right) to the parent, it can also record left + right as a candidate diameter at no extra cost. The best value is kept in a field of Solution and reset at the start of each call.

Java

import java.util.ArrayDeque;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    private int best;

    private int dfs(TreeNode node) { // returns the height of the subtree
        if (node == null) {
            return 0;
        }
        int left = dfs(node.left);
        int right = dfs(node.right);
        best = Math.max(best, left + right);
        return 1 + Math.max(left, right);
    }

    public int diameterOfBinaryTree(TreeNode root) {
        best = 0;
        dfs(root);
        return best;
    }
}

public class Main {
    // Builds a tree from LeetCode's level-order array: null marks a missing child.
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.remove();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.diameterOfBinaryTree(tree(1, 2, 3, 4, 5)));
        System.out.println(s.diameterOfBinaryTree(tree(1, null, 2, null, 3)));
    }
}

Output

3
2

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

Interview points

The longest path through a node has length height(left) + height(right), counted in edges.
The diameter is the maximum of that value over all nodes, so the path need not touch the root.
One DFS returns the height and updates the best value, giving O(n) time.

Summary

Brute force: O(n²) time. Optimal: O(n) time.
Space is O(h) for the recursion.
A single node has diameter 0.