Diameter of a Binary Tree
Problem
Return the diameter of the tree: 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: [1, 2, 3, 4, 5] Output: 3
The path 4 → 2 → 1 → 3 (or 5 → 2 → 1 → 3).
Also asked as: Diameter of a tree
Test cases
Case 1
Input: [1,2,3,4,5] Expected: 3
Case 2
Input: [1,2] Expected: 1
Case 3
Input: [1] Expected: 0
View solutionHide solution1 approach
1. DFS returning height, update diameter as a side effect
Time O(n)Space O(h)
At each node, the longest path through it is leftHeight + rightHeight; track the max.
function diameterOfBinaryTree(root) { let best = 0; const height = (n) => { if (!n) return 0; const l = height(n.left), r = height(n.right); best = Math.max(best, l + r); return 1 + Math.max(l, r); }; height(root); return best;}