Binary Tree Diameter

You are given a binary tree represented in level order. Your task is to compute the diameter of the tree. The diameter of a binary tree is defined as the length (in terms of number of nodes) of the longest path between any two nodes in the tree. More formally, if for any node the depth of its left and right subtrees are \(L\) and \(R\), then a candidate for the diameter passing through that node is \(L + R + 1\). Your job is to find the maximum such value.

The binary tree is given as a single line representing its level order traversal. Use the token null to denote missing nodes. For example, the tree shown below matches the input:

1 2 3 4 5 null null

This corresponds to the binary tree:

1
/ \ 2 3
/ \ 4 5

Compute the diameter and output it as an integer.

inputFormat

The input is provided in a single line via standard input which represents the level order traversal of the binary tree. Nodes are separated by spaces and missing nodes are denoted by null. For example:

1 2 3 4 5 null null

outputFormat

Output a single integer via standard output representing the diameter of the tree. The diameter is defined as the maximum sum of the depths of the left and right subtrees plus one.

## sample

1

1