Diameter of Binary Tree
Diameter of Binary Tree is a easy trees & bst problem solved with the postorder + multiple return values pattern.
The best approach, optimal (height pass with a running best), runs in O(n) time and O(h) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (heights at every node) up.
Problem
The diameter of a binary tree is the number of edges on the longest path between any two nodes. The path may or may not go through the root.
Given the root of a binary tree, return its diameter.
Examples
Example 1
- Input
root = [7, 3, 9, null, 5, null, null, 4, 8]- Output
4- Why
- The path 4 -> 5 -> 3 -> 7 -> 9 uses 4 edges.
Example 2
- Input
root = [6, 2, null, 1, 4, 0, null, 3]- Output
4- Why
- The longest path 0 -> 1 -> 2 -> 4 -> 3 never touches the root 6.
Example 3
- Input
root = [1]- Output
0- Why
- One node, so no edges.
Constraints
- The tree has
1to10^4nodes. -100 <= Node.val <= 100
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (heights at every node) | O(n²) | O(h) |
| Optimal (height pass with a running best) | O(n) | O(h) |
1Brute force (heights at every node)
O(n²)Each node recomputes heights of its subtrees; on a chain that adds up to n + (n-1) + ... + 1.O(h)Recursion depth is the tree height h.For every node, compute the height of its left and right subtree from scratch; their sum is the longest path that bends at that node. The answer is the maximum over all nodes.
height(null) = 0,height(n) = 1 + max(height(left), height(right)).- At each node, candidate =
height(left) + height(right). - Return the max of the candidate and the answers for both children.
class Solution {
public int diameterOfBinaryTree(TreeNode root) {
if (root == null) return 0;
int through = height(root.left) + height(root.right);
return Math.max(through, Math.max(diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right)));
}
private int height(TreeNode n) {
if (n == null) return 0;
return 1 + Math.max(height(n.left), height(n.right));
}
}class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
through = self.height(root.left) + self.height(root.right)
return max(through, self.diameterOfBinaryTree(root.left), self.diameterOfBinaryTree(root.right))
def height(self, n: Optional[TreeNode]) -> int:
if n is None:
return 0
return 1 + max(self.height(n.left), self.height(n.right))class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
if (root == nullptr) return 0;
int through = height(root->left) + height(root->right);
return max(through, max(diameterOfBinaryTree(root->left), diameterOfBinaryTree(root->right)));
}
private:
int height(TreeNode* n) {
if (n == nullptr) return 0;
return 1 + max(height(n->left), height(n->right));
}
};function diameterOfBinaryTree(root) {
if (root === null) return 0;
const through = height(root.left) + height(root.right);
return Math.max(through, diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right));
}
function height(n) {
if (n === null) return 0;
return 1 + Math.max(height(n.left), height(n.right));
}2Optimal (height pass with a running best)
O(n)Every node is visited once with O(1) work.O(h)Recursion stack as deep as the tree.Compute heights in a single postorder pass. While a node knows both child heights, it also knows the longest path bending at itself, so it updates a running best before returning its own height.
h(null) = 0.l = h(left),r = h(right).best = max(best, l + r).- Return
1 + max(l, r).
class Solution {
private int best;
public int diameterOfBinaryTree(TreeNode root) {
best = 0;
h(root);
return best;
}
private int h(TreeNode n) {
if (n == null) return 0;
int l = h(n.left), r = h(n.right);
best = Math.max(best, l + r);
return 1 + Math.max(l, r);
}
}class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.best = 0
self.h(root)
return self.best
def h(self, n: Optional[TreeNode]) -> int:
if n is None:
return 0
l, r = self.h(n.left), self.h(n.right)
self.best = max(self.best, l + r)
return 1 + max(l, r)class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
best = 0;
h(root);
return best;
}
private:
int best;
int h(TreeNode* n) {
if (n == nullptr) return 0;
int l = h(n->left), r = h(n->right);
best = max(best, l + r);
return 1 + max(l, r);
}
};function diameterOfBinaryTree(root) {
let best = 0;
function h(n) {
if (n === null) return 0;
const l = h(n.left), r = h(n.right);
best = Math.max(best, l + r);
return 1 + Math.max(l, r);
}
h(root);
return best;
}Edge cases to test
- A single node: diameter 0
- The longest path lies entirely inside one subtree and skips the root
- A skewed tree (a chain): diameter is n - 1
Hints
Hint 1
The longest path has a highest node. Through that node, its length is height(left) + height(right), counted in edges.
Hint 2
Computing heights from scratch at every node repeats work. Can one postorder pass return the height and update the best diameter at the same time?
FAQ
What is the best time complexity for Diameter of Binary Tree?
Optimal (height pass with a running best) runs in O(n) time and O(h) extra space. Every node is visited once with O(1) work.
Which pattern does Diameter of Binary Tree use?
It is a trees & bst problem that uses the postorder + multiple return values pattern. Other problems with the same pattern: Balanced Binary Tree, Validate Binary Search Tree, Children Sum in a Binary Tree.
Is there a brute force solution for Diameter of Binary Tree?
Yes. Brute force (heights at every node) takes O(n²) time and O(h) space. For every node, compute the height of its left and right subtree from scratch; their sum is the longest path that bends at that node.
Which edge cases should I test for Diameter of Binary Tree?
A single node: diameter 0; The longest path lies entirely inside one subtree and skips the root; A skewed tree (a chain): diameter is n - 1.