410/670

410. Diameter of Binary Tree

Easy

You receive the root of a binary tree, where each node is a TreeNode with fields val, left, and right. The diameter of the tree is the number of edges on the longest path between any two nodes — and that path is not required to pass through the root.

Return the diameter as a single integer. An empty tree and a one-node tree both have diameter 0.

The diameter is the longest node-to-node pathExample 1: the path 4 → 2 → 1 → 3 (gold) has 3 edges — the longest in the tree. The path bends at node 1: one chain drops left, one drops right.

Example 1:

Input: root = [1, 2, 3, 4, 5]

Output: 3

Explanation: The longest path runs 4 → 2 → 1 → 3 (or 5 → 2 → 1 → 3): three edges.

Example 2:

Input: root = [1, 2]

Output: 1

Explanation: The only pair of nodes is 1 and 2, joined by a single edge.

Constraints:

0 ≤ number of nodes ≤ 10⁴
-100 ≤ Node.val ≤ 100

Hints:

Any path in a tree has a highest node — its 'bend'. Seen from that node, the path is a chain descending into the left subtree plus a chain descending into the right subtree.

So for each node, the longest path bending there has length height(left subtree) + height(right subtree), counting edges. The answer is the max of that over all nodes.

You don't need a second traversal to get heights: one post-order DFS can return each subtree's height AND update a running best on the way up.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

Input: root = [1, 2, 3, 4, 5]

Expected output: 3