Difficulty: Easy Pattern: Trees LeetCode: https://leetcode.com/problems/diameter-of-binary-tree/
The diameter of a binary tree is the length (number of edges) of the longest path between any
two nodes. The path may or may not pass through the root. Given root, return the diameter.
Signature:
int diameterOfBinaryTree(TreeNode root)
Examples:
Input: root = [1,2,3,4,5]
Output: 3
Input: root = [1,2]
Output: 1
Picture the tree as a road map: each line between a parent and child is one road segment. The diameter is the longest single drive between any two houses, counted in road segments – and that drive is a simple path with no backtracking. Any such path has exactly one highest node (its topmost point), where the path stops climbing one branch and starts descending the other. So the strategy is: for every node, look at the arch that passes through it – going down through its deepest left descendant and down through its deepest right descendant – and keep the longest arch seen anywhere in the tree. That longest arch is the diameter.
Trace [1,2,3,4,5]:
1
/ \
2 3
/ \
4 5
The arch through node 1 goes 4 -> 2 -> 1 -> 3 – three edges. The arch through node 2
goes 4 -> 2 -> 5 – two edges. Arches through the leaves 3, 4, 5 are zero edges. The
longest is 3, so the diameter is 3. Note the answer does not have to pass through the
root in general – here it happens to, but in a left-heavy tree the widest arch may sit
entirely inside the left subtree, which is why we check every node, not just the root.
We use recursion with one twist: the helper returns
its height to its parent (so the parent can build its own arch), but it also updates a
shared answer with the best arch it sees. Reason it out explicitly (no leaps of faith):
assume height already returns the correct height of any smaller subtree. At the current
node: get left = height(left child) and right = height(right child); the arch through this
node is left + right, so update the running answer with max(answer, left + right); then
return 1 + max(left, right) as this node’s own height. That assumption is valid because the
same logic applies to each subtree all the way down to an empty subtree – the
base case, which has height 0.
One counting detail: the helper measures height in nodes (a
leaf returns 1, an empty subtree returns 0). A pleasant
consequence is that height(left child) + height(right child) at a node comes out as the
number of edges in the arch through that node – because the node-count of a child subtree
equals the number of edges from the parent down to that subtree’s deepest leaf. So no extra
+1 is needed for the arch, and the answer lands in edges as LeetCode requires. (This
“return height to the parent, track a separate answer on the side” structure is shared with
Balanced Binary Tree; both are single-pass
DFS.)
Pause and answer before expanding. Wrong guesses teach more than fast right ones.
Q1 (recall). The diameter is measured in which unit?
Q2 (comprehend). The helper returns HEIGHT to its parent but also updates a separate best field. Why two different things – why not just return the diameter up the recursion?
best = 0
function diameter(root):
reset best to 0
height(root)
return best
function height(node):
if node is null:
return 0
left = height(node.left)
right = height(node.right)
best = max(best, left + right) # arch through this node
return 1 + max(left, right) # height goes UP to the parent
Resetting best matters if the solver object is reused across calls.
class Solution {
private int best = 0;
public int diameterOfBinaryTree(TreeNode root) {
best = 0;
height(root);
return best;
}
// Returns height (edge count) of subtree; updates the global best diameter seen so far.
private int height(TreeNode node) {
if (node == null) {
return 0;
}
int left = height(node.left);
int right = height(node.right);
best = Math.max(best, left + right);
return 1 + Math.max(left, right);
}
}
The field best is the running answer; it must be reset in the public method because LeetCode
reuses the same Solution instance across test cases. The helper returns edge-count height
(null -> 0, leaf -> 1 + max(0,0) = 1) so left + right is already in edges – no +1 is
needed for the arch, unlike node-count formulations.
Time: O(n) -- every node is visited exactly once
Space: O(h) -- recursion stack depth equals tree height (log n balanced, n skewed)
Tree [1,2,3,4,5]:
1
/ \
2 3
/ \
4 5
| Call | left | right | left+right | best after | return (height) |
|---|---|---|---|---|---|
| height(4) | 0 | 0 | 0 | 0 | 1 |
| height(5) | 0 | 0 | 0 | 0 | 1 |
| height(2) | 1 | 1 | 2 | 2 | 2 |
| height(3) | 0 | 0 | 0 | 2 | 1 |
| height(1) | 2 | 1 | 3 | 3 | 3 |
Longest path: 4 -> 2 -> 1 -> 3 (three edges). Output: 3.
Q1 (apply). Trace this left-leaning chain:
1
/
2
/
3
What diameter does the method return?
123Q2 (analyze). The public method resets best = 0 at the start. Why does this matter specifically on LeetCode?
Solution object across test cases; without reset, the previous answer leaks into the next onebest might start negativeQ3 (transfer). Suppose you must also RETURN one example path that achieves the diameter, not just its length. How would you extend the approach, in words?
left + right + 1 as the diameter – that counts nodes, but LeetCode counts edges.
Keep the height as edge-count and the arch as a bare left + right.best is updated at every node, not just the root.best.