Maximum Sum Path in a Binary Tree Problem Statement

You are provided with a binary tree consisting of N nodes where each node has an integer value. The task is to determine the maximum sum achievable by a simple path between any two nodes in the tree, which may include the same node twice.

Description:

A simple path is defined as a path connecting any two nodes in the tree, ensuring no edge is traversed more than once. The sum of a simple path equates to the total of all node values present in that path.

Input:

The first line of input contains an integer 'T' representing the number of test cases. Each test case is given in the form of level-order traversal elements on a single line, where node values are separated by spaces. If a node is null, it's represented by -1.

Output:

Output the maximum sum of a simple path for each test case on a separate line.

Example:

Input:

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

Output:

18

Explanation:

The tree can be visualized with the root node '1'.
- Level 1: root = 1
- Level 2: left child = 2, right child = 3
- Level 3: left of 2 = 4, right of 2 = null (-1); left of 3 = 5, right of 3 = 6
- Level 4: left of 4 = null (-1), right of 4 = 7; other nodes = null (-1)
The input concludes when all nodes on the last level are null (-1).

Constraints:

• 1 <= T <= 100
• 1 <= N <= 3000
• -10^5 <= data <= 10^5 and data != -1

Note:

No need to print anything; your task is to implement the function logic.