#543
Diameter of Binary Tree
Easy Height with a global best
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the number of edges on the longest path between any two nodes of a binary tree (the path need not pass through the root).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the longest path (in edges) between any two nodes.
Why this works: the longest path through a node = left height + right height. Compute heights once and update a global best.
Example: 1 (2 (4, 5), 3)
at 2: heights 1 + 1 = 2at 1: heights 2 + 1 = 3 → path 4-2-1-3
✦Hints open one at a time
The longest path through a node = height(left) + height(right).
Compute heights bottom-up and update a global maximum along the way.
↗Approach
One postorder pass: height(node) returns 1 + max(child heights) and also updates best with leftHeight + rightHeight.
</>Solution (Java)
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
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); // path bending at n
return 1 + Math.max(l, r);
}
}!Common mistake
Calling a separate height function at every node — O(n²) on a skewed tree.
Complexity
- Time: O(n).
- Space: O(h).
Topic: Binary Trees
🎬 Episodes 53–60: video coming soon