New update is available. Click here to update.

Convert Bst To The Greater Sum Tree

PROBLEM STATEMENT

You have been given a Binary Search Tree of integers. You are supposed to convert it to a greater sum tree such that the value of every node in the given BST is replaced with the sum of the values of all the nodes which are greater than the value of the current node in the tree.

A Binary Search Tree is a tree, whose internal nodes each store a value greater than all the values in the node's left subtree and less than those in its right subtree.

Note :

You need to modify the given tree only. You are not allowed to create a new tree.

For example:

For the given binary search tree

Example

11 will be replaced by {15 + 29 + 35 + 40}, i.e. 119.
2 will be replaced by {7 + 11 + 15 + 29 + 35 + 40}, i.e. 137.
29 will be replaced by {35 + 40}, i.e. 75.
1 will be replaced by {2 + 7 + 11 + 15 + 29 + 35 + 40}, i.e. 139.
7 will be replaced by {11 + 15 + 29 + 35 + 40}, i.e. 130.
15 will be replaced by {15 + 29 + 35 + 40}, i.e. 104.
40 will be replaced by 0 {as there is no node with a value greater than 40}.
35 will be replaced by {40}, i.e. 40.

Input Format:

The first line contains an integer 'T', which denotes the number of test cases. Then the test cases follow.

The first line of each test case contains elements in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 on its place.

For example, the input for the tree depicted in the below image would be :

Example

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

Explanation :

Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null(-1).

Note :

The above format was just to provide clarity on how the input is formed for a given tree. 
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

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

Output Format:

For each test case, print a single line that contains the level order traversal of the greater sum tree where all nodes are printed in a single-space separated manner.

The output of each test case will be printed in a separate line.

Note :

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= 'T' <= 100
0 <= 'N' <= 1000
0 <= 'DATA' <= 10 ^ 4 and 'DATA' != -1

Where ‘N’ is the total number of nodes in the binary search tree, and 'DATA' is the value of the binary search tree node.

Time Limit: 1sec

Approach 1

Our very basic intuition is that we are going to traverse the tree node by node through any order traversal (pre-order, in-order, and post-order), and for each node, we will find all the greater nodes, SUM their values and store it. Then, later we replace each node with its corresponding SUM. The steps are as follows

We are going to use a HashMap, in which the key represents the value of a node and the value corresponding to that key represents the SUM of all nodes which are greater than that key. Let’s say our HashMap is “GREATERSUM”.
So we will visit every node in the tree through pre-order traversal and find the SUM of all the values of nodes that are greater than the value of the current node. Also, we store the SUM in the hashmap “GREATERSUM” corresponding to the current value of the node. Let’s say “GETMAXSUM” is the function which is returning the SUM of the values of all the nodes which are greater than the value of the current node.
GETMAXSUM(root , keyValue):
This function takes two parameters one is the root node of the BST and the other is the value as “KEYVALUE” for which this function will return the SUM of all the values of the nodes which are greater than the “KEYVALUE”.
1. Base Case: If the root is NULL, then return 0.
2. If the value at the root node is less than the “KEYVALUE”, then we will go for the right subtree and store it in “RIGHTANS” because all the nodes from the left subtree will be smaller than the “KEYVALUE”.
3. Else, we add the value of the root node to the “SUM” and recur for the left subtree and right subtree and store the answers in the variables “LEFTANS” and “RIGHTANS” respectively.
4. Return the total SUM i.e. (SUM + LEFTANS + RIGHTANS).

3. Now the key of “GREATERSUM” will represent the node’s value of the given BST and the value corresponding to that key will represent the SUM of all nodes which have greater value than the key.

4. Using any one of the traversals, we will replace all the node’s values corresponding to the value in the “GREATERSUM”.

Try Problem

Approach 2

The key idea behind this approach is that we are going to use reverse in-order traversal using recursion. Reverse inorder traversal of the given binary search tree will give us the value of the nodes in descending order. Thus, before visiting a node, we would have visited all the nodes which are greater than that node in the tree’s reverse in-order traversal. So while traversing, we will keep track of the sum of values of the nodes which we have visited so far, i.e. the sum of the values of all the nodes which are greater than the value of the current node in a variable, let’s say “SUM”.

The steps are as follows :

If the root is NULL, then return.
Recursive call on the right subtree.
Store the value of the root node as “ROOTVAL”.
Set the value of the current node as “SUM”.
Add “ROOTVAL” to the “SUM”.
Recursive call on the left subtree.

Try Problem

Convert Bst To The Greater Sum Tree

PROBLEM STATEMENT

You have been given a Binary Search Tree of integers. You are supposed to convert it to a greater sum tree such that the value of every node in the given BST is replaced with the sum of the values of all the nodes which are greater than the value of the current node in the tree.

A Binary Search Tree is a tree, whose internal nodes each store a value greater than all the values in the node's left subtree and less than those in its right subtree.

Note :

For example:

Input Format:

Explanation :

Note :

Output Format:

Note :

Constraints:

Approach 1

Approach 2

Interested in Coding Ninjas Flagship Courses?