# 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-&gt;data = item;`
`    ``temp-&gt;left = temp-&gt;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-&gt;right, sum);`
`    ``// Now *sum has sum of nodes in right subtree, add`
`    ``// root-&gt;data to sum and update root-&gt;data`
`    ``*sum = *sum + root-&gt;data;`
`    ``root-&gt;data = *sum;`
`    ``// Recur for left subtree`
`    ``modifyBSTUtil(root-&gt;left, sum);`
`}`
`// A utility function to do inorder traversal of BST`
`void` `inorderTraversal(``struct` `node *root)`
`{`
`    ``if` `(root != NULL)`
`    ``{`
`        inorderTraversal``(root-&gt;left);`
`        ``printf``(``"%d "``, root-&gt;data);`
`        inorderTraversal``(root-&gt;right);`
`    ``}`
`}`
`// Driver Program to test above functions`
`int` `main()`
`{`
`    ``struct` `node *root = NULL;`
`<code class="cpp spaces">    `

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