Diameter of Binary Tree
Measure the longest path, counted in edges, between any two nodes of a binary tree. The path does not have to pass through the root.
Examples
Path is [4,2,1,3] or [5,2,1,3], length 3 (3 edges).
Problem Understanding
The diameter of a tree is the number of edges on the longest path between any two nodes.
Crucially, the path does NOT need to pass through the root. It could be entirely contained within the left or right subtree.
Algorithm Strategy
We use Post-Order DFS.
At any node, the longest path that bends at that node has left + right edges, where left and right are the heights of its two subtrees. The longest path overall can bend at any node, not only the root.
So:
- Return Value: the height of the subtree,
max(left, right) + 1— a parent can extend only one side. - Side Effect:
best = max(best, left + right).
Interactive Visualization
Heights appear under nodes as they return. The longest path found so far is drawn in green, and it moves only when some node’s left + right beats it — often at a node that is not the root.
Dry Run: [1,2,3,4,5]
| Node | Left H | Right H | Path Through Me (L+R) | Max Diameter | Return H |
|---|---|---|---|---|---|
| 4 | 0 | 0 | 0 | 0 | 1 |
| 5 | 0 | 0 | 0 | 0 | 1 |
| 2 | 1 (from 4) | 1 (from 5) | 1+1=2 | 2 | 2 |
| 3 | 0 | 0 | 0 | 2 | 1 |
| 1 | 2 (from 2) | 1 (from 3) | 2+1=3 | 3 | 3 |
Edge Cases & Common Mistakes
- Width in Edges vs Nodes: The diameter is usually defined as the number of edges. If asked for nodes, it's
edges + 1. - Diameter not through Root: The longest path might just exist in the left subtree. We must track
maxDiameterglobally (or pass it up). - Single Node: Diameter is 0 edges (1 node).
- Height vs Diameter: The function returns
Height(depth) but updatesDiameteras a side effect. Don't confuse the two.
Solution
Height calculation with Diameter update.
Diameter of Binary Tree Code
1var diameterOfBinaryTree = function(root) {2 let best = 0;34 function height(node) {5 if (!node) return 0;6 const left = height(node.left);7 const right = height(node.right);8 best = Math.max(best, left + right);9 return Math.max(left, right) + 1;10 }1112 height(root);13 return best;14};