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

Convert BST to Greater Sum Tree

 

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:

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