Longest Univalue Path in Binary Tree

Given a binary tree, find the length of the longest path in which every node has the same value. The path length is defined as the number of edges between nodes. The path does not necessarily pass through the root.

Let \( P \) be any path where all nodes have the same value. You need to compute the maximum \( |P| \) (i.e. the number of edges). For example, in the tree below:

    5
   / \
  4   5
 / \   \
1   1   5

the longest univalue path has length 2 (from the right child 5 to its right child 5).

Your task is to implement a solution that reads the tree from stdin and outputs the result to stdout.

inputFormat

The input is provided as a single line string representing the binary tree in level order traversal. Each node value is separated by spaces, and the string null is used to denote a missing node.

For example, the tree:

    5
   / \
  4   5
 / \   \
1   1   5

will be given as:

5 4 5 1 1 null 5

outputFormat

Output a single integer representing the length (i.e., the number of edges) of the longest path where each node in the path has the same value.

## sample

5 4 5 1 1 null 5

2