BST to Greater Tree Problem Statement

Given a binary search tree (BST) with 'N' nodes, the task is to convert it into a Greater Tree.

A Greater Tree is defined such that every node's value in the original BST is replaced by the sum of all values greater than or equal to it in the tree.

A binary search tree (BST) has the following properties:

• The left subtree of a node contains only nodes with values less than the node's value.
• The right subtree of a node contains only nodes with values greater than the node's value.
• Both the left and right subtrees must also be binary search trees.

Example:

Visual Example:

Input:

Example of level order input for a tree: 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output:

Explanation of the transformation: 4 becomes 9, 2 becomes 14, 5 remains 5, 1 becomes 15, 3 becomes 12.

Input:

The first line contains an integer 'T' indicating the number of test cases. For each test case, a line contains the elements of the tree in level order separated by space. Use -1 for null nodes.

Output:

For each test case, output the level order traversal of the Greater Tree with node values separated by spaces. Use -1 for null nodes. Output each test case on a separate line.

Constraints:

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 5000
• 0 ≤ data ≤ 10⁶

Time Limit: 1 sec