Diameter of a Binary Tree

The diameter is the number of edges on the longest path between any two nodes of the tree. The path does not have to pass through the root.

The tests write a tree as a level-order list (row by row, left to right) with None for a missing child: [3, 9, 20, None, None, 15, 7] is a root 3 with children 9 and 20, where 20 has children 15 and 7.

For [1, 2, 3, 4, 5] the answer is 3 (the path 4 -> 2 -> 1 -> 3).

Examples

Example 1

Input:

diameter(root)  # root = [1, 2, 3, 4, 5]

Output:

3

Example 2

Input:

diameter(root)  # root = [1, 2]

Output:

1

Constraints

• 0 <= number of nodes <= 100000
• The tree is not deeper than 800 levels.