Convert Bst To The Greater Sum Tree
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

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 :

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

Question

Convert Bst To The Greater Sum Tree

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

Accepted Answer

The task is to convert a Binary Search Tree into a Greater Sum Tree.

Traverse the BST in reverse inorder (right, root, left) to visit nodes in descending order.
Keep track of the sum of all greater nodes encountered so far.
Update the value of each node by adding the sum of greater nodes and update the sum.
Continue this process until all nodes have been visited.
Return the modified BST.

Accepted Answer

public class Solution {
static int sum=0;
public static void replaceWithLargerNodesSum(BinaryTreeNode root) {

if(root==null){
return;
}
replaceWithLargerNodesSum(root.right);
sum+=root.data;
root.data=sum;
replaceWithLargerNodesSum(root.left);

}
}

Accepted Answer

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

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

Space Complexity: O(n)Explanation:

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).

Time Complexity: O(n^2)Explanation:

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).

Accepted Answer

Using In-Order Traversal

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.

Space Complexity: O(n)Explanation:

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

We are using in-order traversal to visit ‘N’ nodes recursively, in which the recursive stack will take O(H) space where H is the height of the tree. In the worst case, H will equal to N, when each node in the tree has only one child. Thus, the space complexity is O(N).

Time Complexity: O(n)Explanation:

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

We are visiting every node exactly once using the reverse in-order traversal of the tree. So, the final time complexity will be O(N).

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:

Top Deloitte Java Developer interview questions & answers

Popular interview questions of Java Developer

Top HR questions asked in Deloitte Java Developer