Binary Tree Diameter — Problem Statement & Solution Guide
Problem Description
Binary Tree Diameter
Given a binary tree in which every node holds a distinct integer, determine the diameter of the tree. The diameter is defined as the number of edges on the longest simple path that connects any two leaf nodes of the tree. If the tree contains only a single node, its diameter is defined as 0.
The tree is supplied as a level‑order array where a null entry indicates the absence of a child at that position. Your algorithm must run in O(N) time where N is the number of nodes and use O(H) auxiliary space, where H is the height of the tree (recursion stack). Return the diameter as an integer.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Binary Tree Diameter"
WHY DOES IT MATTER?
This bottom‑up height‑and‑diameter pattern reduces the problem from quadratic to linear time, which is critical for large data sets and real‑time systems. It also demonstrates mastery of recursion and tree DP, a common interview theme.
OPTIMIZATION CHALLENGE
The insight that the diameter either passes through a node or lies entirely in a subtree allows us to compute both values in a single pass, avoiding repeated traversals of the same subtrees.
REAL-WORLD CONNECTION
Consider a network of routers where each link has a latency. Finding the longest minimal‑latency path between any two endpoints is analogous to computing a tree diameter, and the same post‑order aggregation can be used to optimize routing tables.
When implementing, use a helper that returns a pair (height, diameter) to keep the code clean and avoid global variables. Also, remember that height of an empty subtree is -1 so that a leaf node has height 0.
COMPLEXITY AT A GLANCE
O(n)O(h)Core Theory — Why This Approach?
The diameter of a binary tree is the longest path between any two nodes, measured in edges. A naive approach would enumerate all pairs of nodes, compute the path length between them, and keep the maximum. This requires O(n^2) time and is infeasible for large trees because the number of node pairs grows quadratically.
The optimal solution uses a single post‑order traversal that computes two values for each node: the height of its subtree and the best diameter found so far. For a node, the longest path that passes through it is the sum of the heights of its left and right subtrees (plus one for the edges to the node). By propagating the maximum of this value up the recursion, we obtain the global diameter in O(n) time. This bottom‑up strategy eliminates redundant work and guarantees linear complexity.
The key insight is that the diameter either passes through a node (connecting a leaf in its left subtree to a leaf in its right subtree) or lies entirely within one of its subtrees. By computing the height and diameter simultaneously for each subtree, we can decide locally which option yields the larger diameter, ensuring that the final answer is correct without revisiting any node more than once.
Interview Questions on This Problem
Q1What is the time complexity of computing the diameter of a binary tree using a single DFS traversal, and why is it optimal?
The time complexity is O(n), where n is the number of nodes. It is optimal because each node is visited once, and the algorithm performs a constant amount of work per node, matching the lower bound for traversing all nodes.
Q2How would you modify the diameter algorithm to handle a weighted binary tree where edges have lengths?
Replace the height calculation with the maximum weighted distance to a leaf. For each node, compute the two largest weighted depths from its children, sum them to get the candidate diameter through that node, and propagate the maximum weighted depth upward. The overall complexity remains O(n).
Q3During an interview, a candidate returns a diameter of 0 for a tree with two nodes. What mistake might they have made?
They likely counted nodes instead of edges or failed to add 1 when combining child heights. The diameter should be the number of edges, so for two connected nodes it is 1.
Examples
Input
[1,2,3,null,4,5,null,null,null,6]
Output
5
Explanation: The tree structure is: 1 / \ 2 3 \ / 4 5 / 6 The leaf nodes are 6, 5, and any missing children are ignored. The longest path connects leaf 6 to leaf 5 and traverses the edges 6‑4, 4‑2, 2‑1, 1‑3, 3‑5, totaling 5 edges. Hence the diameter is 5.
Input
[42]
Output
0
Explanation: The tree consists of a single node, which is also a leaf. No path exists between two distinct leaves, so the diameter is defined as 0.
Input
[10,20,30,40,50,60,70]
Output
4
Explanation: The tree structure is: 10 / \ 20 30 / \ / \ 40 50 60 70 All four bottom nodes are leaves. The longest leaf‑to‑leaf path is between 40 and 70: 40‑20, 20‑10, 10‑30, 30‑70, which uses 4 edges. Therefore the diameter equals 4.
Constraints
- 1 <= number of nodes <= 10^5
- All node values are distinct 32‑bit signed integers
- The input array represents a valid binary tree in level order; null denotes a missing child
- The algorithm must run in O(N) time and O(H) auxiliary space
Optimal Approach & Strategy
Perform a single post‑order DFS that returns both the height of a subtree and the best diameter found so far. Combine child heights to update the diameter, yielding O(n) time and O(h) space.
Brute Force Approach
Enumerate all pairs of nodes, compute the path length between each pair, and keep the maximum. This requires O(n^2) time and is impractical for large trees.
Verified Code Solutions
function diameterOfBinaryTree(root) {
if (!root) return 0;
let leftHeight = getHeight(root.left);
let rightHeight = getHeight(root.right);
let leftDiameter = diameterOfBinaryTree(root.left);
let rightDiameter = diameterOfBinaryTree(root.right);
return Math.max(leftHeight + rightHeight + 1, Math.max(leftDiameter, rightDiameter));
}
function getHeight(root) {
if (!root) return 0;
return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
if (!root) return 0;
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
int leftDiameter = diameterOfBinaryTree(root->left);
int rightDiameter = diameterOfBinaryTree(root->right);
return max(leftHeight + rightHeight + 1, max(leftDiameter, rightDiameter));
}
int getHeight(TreeNode* root) {
if (!root) return 0;
return 1 + max(getHeight(root->left), getHeight(root->right));
}class Solution {
public int diameterOfBinaryTree(TreeNode root) {
if (root == null) return 0;
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
int leftDiameter = diameterOfBinaryTree(root.left);
int rightDiameter = diameterOfBinaryTree(root.right);
return Math.max(leftHeight + rightHeight + 1, Math.max(leftDiameter, rightDiameter));
}
public int getHeight(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}def diameterOfBinaryTree(self, root):
if not root: return 0
left_height = self.getHeight(root.left)
right_height = self.getHeight(root.right)
left_diameter = self.diameterOfBinaryTree(root.left)
right_diameter = self.diameterOfBinaryTree(root.right)
return max(left_height + right_height + 1, max(left_diameter, right_diameter))
def getHeight(self, root):
if not root: return 0
return 1 + max(self.getHeight(root.left), self.getHeight(root.right))function diameterOfBinaryTree(root) {
if (!root) return 0;
let leftHeight = getHeight(root.left);
let rightHeight = getHeight(root.right);
let leftDiameter = diameterOfBinaryTree(root.left);
let rightDiameter = diameterOfBinaryTree(root.right);
return Math.max(leftHeight + rightHeight + 1, Math.max(leftDiameter, rightDiameter));
}
function getHeight(root) {
if (!root) return 0;
return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.