### 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

- If

Latest Source Code:

Github: SumOfAllGreaterValueInBST.java

**Output:**

50 / \ / \ 30 70 / \ / \ 20 40 60 80 After Sum : 260 / \ / \ 330 150 / \ / \ 350 300 210 80