Transform a BST to greater sum tree | GeeksforGeeks

http://www.geeksforgeeks.org/transform-bst-sum-tree/
Given a BST, transform it into greater sum tree where each node contains sum of all nodes greater than that node.
Key Point: Using reverse inorder traversal to get decreasing order. Accumulative Sum.

The idea is to traverse BST in reverse inorder. Reverse inorder traversal of a BST gives us keys in decreasing order. Before visiting a node, we visit all greater nodes of that node. While traversing we keep track of sum of keys which is the sum of all the keys greater than the key of current node.

// Recursive function to transform a BST to sum tree.

// This function traverses the tree in reverse inorder so

// that we have visited all greater key nodes of the currently

// visited node
void transformTreeUtil(struct Node *root, int *sum)

{

   // Base case

   if (root == NULL)  return;

   // Recur for right subtree

   transformTreeUtil(root->right, sum);

   // Update sum

   *sum = *sum + root->data;

   // Store old sum in current node

   root->data = *sum - root->data;

   // Recur for left subtree

   transformTreeUtil(root->left, sum);

}

// A wrapper over transformTreeUtil()

void transformTree(struct Node *root)

{

    int sum = 0; // Initialize sum

    transformTreeUtil(root, &sum);

}

Method 1 (Naive):
This method doesn’t require the tree to be a BST. Following are steps.
1. Traverse node by node(Inorder, preorder, etc.)
2. For each node find all the nodes greater than that of the current node, sum the values. Store all these sums.
3. Replace each node value with their corresponding sum by traversing in the same order as in Step 1.
This takes O(n^2) Time Complexity.
Also check http://www.geeksforgeeks.org/convert-bst-to-a-binary-tree/
Read full article from Transform a BST to greater sum tree | GeeksforGeeks