48.Diameter of Binary Tree

EasyTrees · 3/15

Problem

Given the root of a binary tree, return the length of its diameter — the longest path between any two nodes in the tree. The path may or may not pass through the root.

The length of a path is measured in edges, not nodes.

Examples

Input:  root = [1,2,3,4,5]
Output: 3
Explanation: The path 4 -> 2 -> 1 -> 3 (or 5 -> 2 -> 1 -> 3) has 3 edges.

Input:  root = [1,2]
Output: 1

Input:  root = [1,2,null,3,4,5,null,null,6]
Output: 4
Explanation: The longest path 5 -> 3 -> 2 -> 4 -> 6 never touches the root.

Constraints

The number of nodes in the tree is in the range [1, 10^4].
-100 <= Node.val <= 100

💡 Key Insight

Every path has a unique highest node where it "bends". The longest path that bends at node has length height(node.left) + height(node.right) (heights counted in nodes, so a null child has height 0). The diameter is the maximum of that sum over all nodes. Instead of recomputing heights for every node (O(n²)), compute height bottom-up once and update a global maximum along the way (O(n)).

Brute Force (Height per Node)

TimeO(n²)SpaceO(h)

Intuition

For every node, compute the heights of its left and right subtrees with a separate helper; their sum is the longest path bending there. Recurse into both children to try every node as the bend point.

Algorithm

If root is null, return 0.
through = height(root.left) + height(root.right).
Return max(through, diameter(root.left), diameter(root.right)).
height(node) = 0 for null, else 1 + max(height(left), height(right)).

Visualization

Tree [1,2,3,4,5]:
        1
       / \
      2   3
     / \
    4   5

node 1: height(2)=2 + height(3)=1 = 3   <- best
node 2: height(4)=1 + height(5)=1 = 2
node 3, 4, 5: 0

Code

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // longest path that bends at root
        int through = height(root.left) + height(root.right);
        int best = Math.max(diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right));
        return Math.max(through, best);
    }

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

Complexity

Time: O(n²) — height is O(size of subtree) and is called for every node; a skewed tree sums to n + (n-1) + ... + 1.
Space: O(h) — recursion depth.

Single-Pass DFSOptimal

TimeO(n)SpaceO(h)

Intuition

The brute force recomputes the same heights over and over. Flip it around: a post-order DFS that returns the height of each subtree already has both child heights in hand when it finishes a node. At that moment, left + right is the longest path bending there, so we update a running diameter and still return 1 + max(left, right) to the parent.

Algorithm

Keep a field diameter = 0.
dfs(node):
- If node is null, return 0.
- left = dfs(node.left), right = dfs(node.right).
- diameter = max(diameter, left + right).
- Return 1 + max(left, right).
Call dfs(root) and return diameter.

Dry Run

flowchart TD
    N1["1<br/>L=2, R=1<br/>diameter = 3<br/>returns 3"] --> N2["2<br/>L=1, R=1<br/>diameter = 2<br/>returns 2"]
    N1 --> N3["3<br/>L=0, R=0<br/>returns 1"]
    N2 --> N4["4<br/>returns 1"]
    N2 --> N5["5<br/>returns 1"]

Post-order visits 4, 5, 2, 3, 1. At node 2 the diameter becomes 2; at node 1 it becomes 2 + 1 = 3.

Code

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int diameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return diameter;
    }

    // returns the height (in nodes) of the subtree rooted at node
    private int height(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = height(node.left);
        int right = height(node.right);
        // longest path bending at this node has left + right edges
        diameter = Math.max(diameter, left + right);
        return 1 + Math.max(left, right);
    }
}

Complexity

Time: O(n) — each node is visited exactly once.
Space: O(h) — recursion depth; O(n) for a skewed tree.

Complexity Comparison

Approach	Time	Space
Brute Force (Height per Node)	O(n²)	O(h)
Single-Pass DFS	O(n)	O(h)

Common Pitfalls

Assuming the diameter passes through the root — the third example's longest path lives entirely in the left subtree.
Mixing up edges and nodes: with heights counted in nodes (null = 0), left + right is already the edge count; adding 1 is wrong.
Returning the diameter from the recursive helper instead of the height — the parent needs the height, and the diameter must be tracked separately.
Declaring diameter as a static field — LeetCode reuses the class across test cases, so a static value leaks between runs.