Diameter of Binary Tree — Solution in Python, Java & C++
Diameter of Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Diameter of Binary Tree is an easy coding problem on depth-first search and trees, asked in Amazon, Google, Microsoft and Meta interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Google, Microsoft, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return the length of its diameter: the longest path between any two nodes, measured in edges. The path may or may not pass through the root.
Example 1
Input: root = [1,2,3,4,5]
Output: 3
Explanation: The paths 4 → 2 → 1 → 3 and 5 → 2 → 1 → 3 each have three edges.
Example 2
Input: root = [1,2]
Output: 1
Example 3
Input: root = [1,2,null,3,4,5,null,null,6]
Output: 4
Explanation: The longest path, 5 → 3 → 2 → 4 → 6, never reaches the root.
Constraints
The number of nodes in the tree is in the range [1, 10^4]-100 <= Node.val <= 100
Hints for Diameter of Binary Tree
Hint 1
Every path has one highest node; at that node the path goes down into the left subtree, the right subtree, or both.
Hint 2
The longest path whose highest node is
xhasheight(x.left) + height(x.right)edges, with height counted in nodes.Hint 3
Compute heights bottom-up in one walk and update a running maximum of that sum at every node.
How to solve Diameter of Binary Tree
For each node, the longest path that turns at it is the height of its left subtree plus the height of its right subtree. One post-order walk computes every height once and keeps the best such sum.
Approach
- Define
height(null) = 0. - At each node, compute
l = height(left)andr = height(right). - Update
best = max(best, l + r). - Return
1 + max(l, r)as this node's height. - After
height(root), returnbest.
Why it works
Any path has a unique topmost node, and from there it descends at most once into each subtree; the longest such descent into a subtree has exactly that subtree's height in edges, counting the edge from the top node. So the best path topped at x has l + r edges, and taking the maximum over all x covers every path.
Complexity
- Time —
O(n) - Space —
O(h) recursion depth
Pitfalls
- The diameter counts edges, not nodes — a single node has diameter 0.
- Returning only
height(root.left) + height(root.right)misses paths that do not pass through the root (third example). - Computing heights separately at every node is O(n^2) on a chain.
Reference solution
Python
from typing import Optional
def diameterOfBinaryTree(root: Optional[TreeNode]) -> int:
best = 0
def height(node):
nonlocal best
if node is None:
return 0
l = height(node.left)
r = height(node.right)
best = max(best, l + r)
return 1 + max(l, r)
height(root)
return bestJava
public static int diameterOfBinaryTree(TreeNode root) {
int[] best = new int[1];
diameterHeight(root, best);
return best[0];
}
static int diameterHeight(TreeNode node, int[] best) {
if (node == null) return 0;
int l = diameterHeight(node.left, best);
int r = diameterHeight(node.right, best);
best[0] = Math.max(best[0], l + r);
return 1 + Math.max(l, r);
}C++
int diameterHeight(TreeNode* node, int& best) {
if (!node) return 0;
int l = diameterHeight(node->left, best);
int r = diameterHeight(node->right, best);
best = max(best, l + r);
return 1 + max(l, r);
}
int diameterOfBinaryTree(TreeNode* root) {
int best = 0;
diameterHeight(root, best);
return best;
}JavaScript
var diameterOfBinaryTree = function(root) {
var best = { value: 0 };
diameterHeight(root, best);
return best.value;
};
var diameterHeight = function(node, best) {
if (node === null) return 0;
var l = diameterHeight(node.left, best);
var r = diameterHeight(node.right, best);
if (l + r > best.value) best.value = l + r;
return 1 + Math.max(l, r);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals