Diameter of Binary Tree

Share

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. The length is measured in number of edges.

Example 1
Input: root = [1,2,3,4,5]
Output: 3
Explanation: The path is 4 → 2 → 1 → 3, which has 3 edges.
Example 2
Input: root = [1,2]
Output: 1
Constraints:

Contents

Approach 1: Brute Force O(n²)

For each node, compute the height of its left and right subtrees separately. The diameter through that node is leftHeight + rightHeight. Track the maximum across all nodes.

Java
int maxDiameter = 0;

public int diameterOfBinaryTree(TreeNode root) {
    computeDiameter(root);
    return maxDiameter;
}

private void computeDiameter(TreeNode node) {
    if (node == null) return;
    int leftH  = height(node.left);
    int rightH = height(node.right);
    maxDiameter = Math.max(maxDiameter, leftH + rightH);
    computeDiameter(node.left);
    computeDiameter(node.right);
}

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

Note: This is O(n²) because height() is called for every node.

Approach 2: Single DFS: O(n)

Combine height calculation and diameter tracking in a single DFS. At each node, the recursive call returns the height of the subtree, while we update the global maximum diameter as a side-effect.

Java
int maxDiameter = 0;

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

private int height(TreeNode node) {
    if (node == null) return 0;

    int leftHeight  = height(node.left);
    int rightHeight = height(node.right);

    // Diameter through this node = left height + right height
    maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);

    // Return height of this subtree
    return 1 + Math.max(leftHeight, rightHeight);
}
The diameter at any node = height(left subtree) + height(right subtree). A leaf node has height 0. The diameter does not need to pass through the root of the whole tree.

Complexity Analysis
ApproachTimeSpace
Brute ForceO(n²)O(h): call stack
Single DFSO(n)O(h): call stack