## Question

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

**Example**

Given a binary search Tree ｀{5,2,3}｀:

```
5
/ \
2 13
```

Return the root of new tree

```
18
/ \
20 13
```

## Thinking

- Each node new value is current value plus sum(other greater node values)
- Right node is visited first
- Current node value equals current node value plus right node value
- Left node value is harder. Left node is not the next node to be added. It may has a lot of right children.
- Make sure curent always get the sum of other greater node values (store the sum in a globe varilabe)

## Solution

#### Java

```
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root the root of binary tree
* @return the new root
*/
public TreeNode convertBST(TreeNode root) {
// Write your code here
if (root == null) {
return null;
}
convertBST(root.right);
sum = root.val + sum;
root.val = sum;
convertBST(root.left);
return root;
}
private int sum = 0;
}
```