# Add all greater values to every node in a BST

### Add all greater values to every node in a BST

##### Given a Binary Search Tree (BST), modify it so that all greater values in the given BST are added to every node.

Solution :

• Reverse of InOrder traversal with sum
• Second Option
• Traverse tree in InOrder and extract all node data to array in O(n)
• Sum all data of array in reverse order in O(n)
• Again Traverse tree in InOrder and replace node value with array in O(n)
##### Algorithm :
• Take sum class object to hold the sum of nodes (because java doesn’t support call by reference, so we need object)
• Traverse reverse InOrder (means Right – Root – Left)
• If `node is null` then
• `return`
• Recursively call for right child
• Set `sum = sum + node.data`
• Set `node = sum`
• Recursively call for left child

Latest Source Code:
Github: SumOfAllGreaterValueInBST.java

Output:

```   50
/ \
/   \
30   70
/ \ / \
20 40 60 80

After Sum :
260
/ \
/   \
330   150
/ \ / \
350 300 210 80
```
Author: