Search for a command to run...
What it teaches: Return height to the parent; record left + right as the best path through each node.
Practise it on judges as “Diameter of Binary Tree”.
Return the length (in edges) of the longest path between any two nodes. The path may not pass through the root.
Example 1
Input: root = [1, 2, 3, 4, 5] Output: 3
The path 4 → 2 → 1 → 3 (or 5 → 2 → 1 → 3).
Constraints
Pattern clues in the wording
These clues point to Tree DFS: Recurse into the left and right children and combine what they return (height, sums, paths).
Stuck? Take one hint at a time
class Solution {
public int diameterOfBinaryTree(TreeNode root) {
return 0;
}
}Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.
Test cases
| # | Input | Expected |
|---|---|---|
| 1 | root = [1,2,3,4,5] | 3 |
| 2 | root = [1,2] | 1 |
+ 1 hidden test the code runner will check
From slow to fast
height(n) returns 1 + max(l, r) and updates best = max(best, l + r).
class Solution {
private int best = 0;
public int diameterOfBinaryTree(TreeNode root) {
height(root);
return best;
}
private int height(TreeNode n) {
if (n == null) return 0;
int l = height(n.left), r = height(n.right);
best = Math.max(best, l + r);
return 1 + Math.max(l, r);
}
}Verdict: One post-order pass.
Before you submit
Test these inputs
Mistakes people make
Interview
How would you return the path itself?