Replace by adding each node with sum of all nodes greater then that node in a given BST

consider the following BST.

           /      \
         30        60
        /   \      /  \
      10    35    50   80 

The above tree should be modified to following 

           /      \
         300        140
        /   \       /  \
      310   270    190   80

This can be done in one traversal.This can be achieved by doing reverse Inorder traversal ,keep track of some of all visited nodes.

struct node
    int data;
    struct node *left, *right;
// A utility function to create a new BST node
struct node *newNode(int item)
    struct node *temp =  (struct node *)malloc(sizeof(struct node));
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
// Recursive function to add all greater values in every node
void modifyBSTUtil(struct node *root, int *sum)
    // Base Case
    if (root == NULL)  return;
    // Recur for right subtree
    modifyBSTUtil(root->right, sum);
    // Now *sum has sum of nodes in right subtree, add
    // root->data to sum and update root->data
    *sum = *sum + root->data;
    root->data = *sum;
    // Recur for left subtree
    modifyBSTUtil(root->left, sum);
// A utility function to do inorder traversal of BST
void inorderTraversal(struct node *root)
    if (root != NULL)
        printf("%d ", root->data);
// Driver Program to test above functions
int main()
    struct node *root = NULL;
 /// add values here
<code class="cpp spaces">    

int sum = 0;
    modifyBSTUtil(root, &amp;sum);
    // print inoder tarversal of the modified BST
    return 0;

Resolving technical problems:

Solve your technical problems instantly

We provide Remote Technical Support from Monday to Sunday, 7:00PM to 1:00 AM

Mail your problem details at along with your mobile numberand we will give you a call for further details. We usually attend your problems within 60 minutes and solve it in maximum 2 days.

Leave a Reply

Your email address will not be published. Required fields are marked *

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