Convert Bst To The Greater Sum Tree

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
20 upvotes
Asked in companies
AmazonMathworksCultfit

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5 2 7 1 3 6 8 -1 -1 -1 -1 -1 -1 -1 -1
4 2 5 -1 3 -1 6 -1 -1 -1 -1
Sample Output 1:
21 29 8 31 26 15 0
11 18 6 15 0
Explanation of Sample Input 1:
For the first test case, after converting the given binary tree into the greater sum tree, the level order traversal of the tree will be {21, 29, 8, 31, 26, 15, 0}, where 5 will be replaced by {6+7+8} i.e. 21, 3 will be replaced by {5+6+7+8} i.e. 26, 7 will be replaced by {8} i.e. 8, 1 will be replaced by {2+3+5+6+7+8} i.e. 33, 2 will be replaced by {3+5+6+7+8} i.e. 26, 6 will be replaced by {7+8} i.e. 15 and 8 will be replaced by 0 (because no node has a value greater than 8 in the given tree).

For the second test case, after converting the given binary tree into the greater sum tree, the level order traversal of the tree will be {11, 18, 6, 15, 0}, where, 4 will be replaced by {5+6} i.e. 11, 2 will be replaced by {3+4+5+6} i.e. 18, 5 will be replaced by {6} i.e. 6, 3 will be replaced by {4+5+6} i.e. 15 and 6 will be replaced by 0 (because no node has a value greater than 6 in the given tree).
Sample Input 2:
2
11 2 29 1 7 15 40 -1 -1 -1 -1 -1 -1 35 -1 -1 -1
10 5 15 2 7 12 20 -1 -1 -1 -1 -1 -1 -1 -1
Sample Output 2:
119 137 75 139 130 104 0 40
47 64 20 69 57 35 0
Explanation of Sample Input 2:
For the first test case, after converting the given binary tree into the greater sum tree, the level order traversal of the tree will be {119, 137, 75. 130, 104, 0, 40}.

For the second test case, after converting the given binary tree into the greater sum tree, the level order traversal of the tree will be {47, 64, 20, 69, 57, 35, 0}.
Hint

For replacing the value of a node, find all the nodes which have the value greater than that node.

Approaches (2)
Naive Approach

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

 

  1. 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”. 
     
  2. 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”.

Time Complexity

O(N * N), where ‘N’ is the number of nodes in the given binary search tree.

 

We are going to every node and finding the sum of all nodes which are greater than that node. So, there are ‘N’ nodes, and for each node, we are doing pre-order traversal to get the sum of all the nodes which are greater than that node, which will take O(N) time. Thus, the overall time complexity is O(N * N).

Space Complexity

O(N), where ‘N’ is the number of nodes in the given binary search tree.

 

We are storing the sum of the nodes greater than a node for all the nodes in the tree. This takes a space of O(N). Also, we are using the pre-order traversal algorithm in which the recursive stack will take O(H) space where H is the height of the tree. In the worst case, H will be equal to N, when each node in the tree has only one child. Thus, the recursive stack will take O(N) space and the final space complexity is O(N + N) = O(N).

Code Solution
(100% EXP penalty)
Convert Bst To The Greater Sum Tree
Full screen
Console