# Convert BST to Greater Sum Tree

Objective: Given a binary search tree (BST), convert it into greater sum tree.

What is greater sum tree: Greater sum tree is a tree in which every node contains the sum of all the nodes which are greater than the node.  see the example below Approach:

Naive approach will be for every node, traverse the tree and find out all the nodes which are greater and update the node. This approach is fine but only problem with this approach is the Time Complexity will be O(N^2). We can do it in one traversal.

We know that right most node in the binary search tree is the biggest node among all node so we will start from there, (reverse inorder traversal).

1. Since we are visiting the nodes in the decreasing order so all we need to care about maintaining the sum of the nodes visited.
2. Keep a global variable which maintains the sum of the nodes visited till now.
3. Before updating the node value, store it in temp, we need it later
4. Updated the node value as sum ( since each node contains sum of nodes greater than that node which means we need to exclude the node value itself).
5. Update the sum as sum = sum + temp (for the next node in iteration).
6. See the code for better understanding.

Complete Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 public class BSTtoGreaterTree { public static int sum = 0; public void greaterTree(Node root){ if(root!=null){ //visit the right node first greaterTree(root.right); //store the node value in temp int temp = root.data; //update the sum, sum till previous visited node root.data = sum; //update the sum for the next node sum = sum + temp; greaterTree(root.left); }else return; } public void inorder(Node root){ if(root!=null){ inorder(root.left); System.out.print(" " + root.data); inorder(root.right); } } public static void main(String args[]){ Node root = new Node(10); root.left = new Node(5); root.right = new Node(15); root.left.left = new Node(2); root.left.right = new Node(7); root.right.left = new Node(12); root.right.right = new Node(20 ); BSTtoGreaterTree b = new BSTtoGreaterTree(); b.inorder(root); System.out.println(""); b.greaterTree(root); System.out.print("Greater Sum Tree: "); b.inorder(root); } } class Node{ int data; Node left; Node right; public Node (int data){ this.data = data; left = null; right = null; } }

Output:

```2  5  7  10  12  15  20
69  64  57  47  35  20  0
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.