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

consider the following BST.

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

The above tree should be modified to following 

              235
           /      \
         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)
    {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}
// 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
    inorderTraversal(root);
    return 0;
}

Leave a Reply

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