Maximum Path Sum Between Two Leaves

Given a non-empty binary tree where each node has a non-negative integer value, determine the maximum possible sum of the path between any two leaves of the given tree.

Explanation:

The path includes the leaf nodes, and the maximum path sum may or may not pass through the root of the tree. If there is only one leaf node in the tree, return -1.

Input:

The first line of input contains an integer 'T' representing the number of test cases. Each test case consists of a single line of elements in level order form. The nodes’ values are separated by spaces, and a -1 indicates that the node is null.

Output:

For each test case, output a single integer denoting the maximum path sum between two leaf nodes of the tree.

Example:

Input:

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

Output:

18

Explanation:

            1
          /   \
         2     3
        / \   / \
       4  -1 5   6
        \
         7
The tree has the maximum path sum 18 between leaves 7 and 6.

Constraints:

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 5000
• 0 ≤ data ≤ 100000

Note: 'N' is the number of nodes in the tree. The input ends when all nodes at the last level are null (-1).

Time limit: 1 sec