Binary Tree Maximum Path Sum Problem Statement

Determine the maximum path sum for any path in a given binary tree with 'N' nodes.

Note:

• A 'path' is defined as any sequence of adjacent nodes connected by an edge within the binary tree.
• The 'path' does not need to pass through the root of the tree.
• The 'path sum' is summed from the values of nodes along that path.

Input:

The first line contains an integer T which denotes the number of test cases to be processed.
Each test case consists of elements of the binary tree given in level-order form, where node values are separated by a single space, and '-1' signifies a null node.

1 2 3 4 -1 5 6 -1 -1 -1 -1 -1 -1

Output:

For each test case, print a single integer indicating the maximum path sum. Each test case result should be on a new line.

Example:

Input:

1
1 2 3 4 -1 5 6 -1 -1 -1 -1 -1 -1

Output:

16

Explanation:

In the given binary tree, one possible maximum path is from node 4 through node 2, node 1, node 3, to node 5 which gives the maximum sum.

Constraints:

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 2000
• -5000 ≤ data ≤ 5000 (data ≠ -1 as -1 denotes null nodes)
• Where 'N' is the number of nodes, and 'data' is the value of the node.

Time Limit: 1 sec

Implementation Note: You do not need to print anything for the function. The output is managed independently.