Longest Univalue Path in a Binary Tree

Given a binary tree, find the length of the longest path where every node in the path has the same value. The path can be any sequence of connected nodes in the tree and may or may not pass through the root. The length of the path is defined as the number of edges between the nodes.

The tree is provided in a level-order format. Use the string null to represent a missing node. For example, the tree below:

    5
   / \
  4   5
 / \   \
1   1   5

is given as: 5 4 5 1 1 null 5.

A useful hint: you can solve the problem by employing a depth-first search (DFS) while calculating, for each node, the longest path on the left and right that continues with the same value. Then, update the overall answer accordingly.

The relation used in DFS can be written in LaTeX as: [ leftPath = \begin{cases} dfs(node.left) + 1, & \text{if } node.left \neq null \text{ and } node.left.val = node.val \ 0, & \text{otherwise} \end{cases} ]

and similarly for the right path. The result for each node is the sum of both paths, i.e., (leftPath + rightPath), and the answer is the maximum such sum over all nodes.

inputFormat

The input begins with an integer (T) ((1 \le T \le 100)) on the first line, representing the number of test cases. Following this, each test case is given on a separate line. Each test case consists of the level-order traversal of a binary tree with nodes separated by spaces. Use the string null to indicate a missing node. For example:

5 4 5 1 1 null 5

outputFormat

For each test case, print a single integer on a new line that represents the length (i.e., number of edges) of the longest univalue path in the given binary tree.## sample

1
5 4 5 1 1 null 5

2