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.
Input: root = [1,2,3,4,5]
Output: 3
Explanation: The path is 4 → 2 → 1 → 3, which has 3 edges.
Input: root = [1,2]
Output: 1
Constraints:
- 1 <= Number of nodes <= 104
- -100 <= Node.val <= 100
Contents
- Approach 1 — Brute Force (two DFS calls)
- Approach 2 — Single DFS (Optimal)
- Complexity Analysis
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.
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));
}
This is O(n²) because height() is called for every node.
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.
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.
| Approach | Time | Space |
|---|
| Brute Force | O(n²) | O(h) — call stack |
| Single DFS | O(n) | O(h) — call stack |