Maximum Sum BST Problem Statement

You are presented with a Binary Tree 'root', which may not necessarily be a Binary Search Tree (BST). Your objective is to identify the maximum sum of node values in any subtree that qualifies as a Binary Search Tree (BST).

Explanation:

A Binary Search Tree is defined as follows:

1) If a left subtree exists for any node, it should comprise only nodes with values less than that node's value.
2) If a right subtree exists for any node, it should comprise only nodes with values greater than that node's value.
3) Both the left and right subtrees must themselves be Binary Search Trees.

Input:

The first line contains a single integer 'T' denoting the number of test cases, followed by each test case.
The first line of each test case contains the tree's elements in a level-order format, separated by spaces. If a node lacks a left or right child, represent it with -1.

Output:

For each test case, return the maximum sum achievable. Output each result on a new line.

Example:

Sample Input:

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

Sample Output:

28
3

Explanation:

For test case 1, the input tree represents an entire BST, and since all nodes have positive values, the whole tree is the subtree with the maximum sum. The sum of all node values is 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.

For test case 2, the subtree containing a single node with a value of 3 is the BST with the maximum sum.

Constraints:

• 1 <= T <= 10
• 1 <= Number of Nodes <= 5 * 10⁴
• 0 <= Node.data <= 10⁵
• Time limit: 1 sec