Diameter of a Binary Tree

You are given a binary tree represented as a comma-separated string in level-order. The string uses the keyword null to denote an absent child. Your task is to compute the diameter of the binary tree. The diameter is defined as the length (i.e., the number of edges) of the longest path between any two nodes in the tree. Note that this path may or may not pass through the root.

For example, consider the tree represented by the string "1,2,3,4,5":

    1
   / \
  2   3
 / \
4   5

The diameter of this tree is 3, corresponding to the path [4,2,1,3] or [5,2,1,3].

Note: If the tree is empty (represented by "null"), then the diameter is 0.

The formula for the diameter at any node is given by: \[ diameter = \max(\text{leftHeight} + \text{rightHeight}, \; \text{leftDiameter}, \; \text{rightDiameter}) \]

inputFormat

The input is a single line containing a comma-separated list of values representing the binary tree in level-order. Each value is either an integer or the literal null (without quotes) for absent nodes.

Examples:

• 1,2,3,4,5
• 1,2,null,3
• null (represents an empty tree)

outputFormat

Output a single integer which is the diameter of the binary tree.

## sample

1,2,3,4,5

3

</p>