48. Diameter of Binary Tree
The diameter is the number of edges on the longest path between any two nodes. The path does not have to pass through the root.
Example 1
Input:
root = [1,2,3,4,5]Output:
3Explanation: Path 4 → 2 → 1 → 3 has 3 edges.
Example 2
Input:
root = [1,2,null,3,4,5,null,null,6]Output:
4Hint 1
Every path has a highest node where it “bends”. Its length there is leftHeight + rightHeight.
Approach 1: Height from every node
Compute heights separately for each node.
⏱ Time O(n²)💾 Space O(h)
Approach 2: One DFS ✅
Return height and update the best diameter on the way up.
⏱ Time O(n)💾 Space O(h)
Reference solution for One DFS (time O(n), space O(h)). Each solution passes every test in all four languages.
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
best = 0
def height(node): # number of nodes on the longest downward path
nonlocal best
if not node:
return 0
l, r = height(node.left), height(node.right)
best = max(best, l + r) # longest path that bends at this node
return 1 + max(l, r)
height(root)
return bestclass Solution {
private int best = 0;
public int diameterOfBinaryTree(TreeNode root) {
best = 0;
height(root);
return best;
}
private int height(TreeNode node) {
if (node == null) return 0;
int l = height(node.left), r = height(node.right);
best = Math.max(best, l + r); // path bending at this node
return 1 + Math.max(l, r);
}
}class Solution {
int best = 0;
int height(TreeNode* node) {
if (!node) return 0;
int l = height(node->left), r = height(node->right);
best = max(best, l + r); // path bending at this node
return 1 + max(l, r);
}
public:
int diameterOfBinaryTree(TreeNode* root) {
best = 0;
height(root);
return best;
}
};function diameterOfBinaryTree(root) {
let best = 0;
const height = node => {
if (!node) return 0;
const l = height(node.left), r = height(node.right);
best = Math.max(best, l + r); // path bending at this node
return 1 + Math.max(l, r);
};
height(root);
return best;
}Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.
This problem is explained in the lesson Binary Trees & BSTs.
Run your code to see results here.