Diameter of a Binary Tree

Easy

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}