All problems

Diameter of Binary Tree

Easy · tree dfs

You are given the root of a binary tree. Imagine walking from one node to another, only along the links between a parent and a child, and never visiting the same node twice. The length of such a walk is the number of links it uses.

Return the length of the longest walk between any two nodes of the tree. The walk does not have to pass through the root, and it can start and end at any node. A tree with no nodes or with a single node has no links to walk along, so its answer is 0.

Examples

Example 1

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

Output: 3

Walking from 4 up to 2, over to 1 and down to 3 uses 3 links, and so does 5, 2, 1, 3. Nothing is longer.

Example 2

Input: root = [1, 2]

Output: 1

Example 3

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

Output: 4

The longest walk is 5, 3, 2, 4, 6. It never touches the root.

Constraints