## Convert BST to Greater Tree Link

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:

Input: The root of a Binary Search Tree like this:

```
5
/ \
2 13
```

Output: The root of a Greater Tree like this:

```
18
/ \
20 13
```

### Solution:

There is a clever way to perform an in-order traversal using only linear time and constant space, first described by J. H. Morris in his 1979 paper “Traversing Binary Trees Simply and Cheaply”.

### Implementation:

### Java:

```
class Solution {
/* Get the node with the smallest value greater than this one. */
private TreeNode getSuccessor(TreeNode node) {
TreeNode succ = node.right;
while (succ.left != null && succ.left != node) {
succ = succ.left;
}
return succ;
}
public TreeNode convertBST(TreeNode root) {
int sum = 0;
TreeNode node = root;
while (node != null) {
/*
* If there is no right subtree, then we can visit this node and
* continue traversing left.
*/
if (node.right == null) {
sum += node.val;
node.val = sum;
node = node.left;
}
/*
* If there is a right subtree, then there is at least one node that
* has a greater value than the current one. therefore, we must
* traverse that subtree first.
*/
else {
TreeNode succ = getSuccessor(node);
/*
* If the left subtree is null, then we have never been here before.
*/
if (succ.left == null) {
succ.left = node;
node = node.right;
}
/*
* If there is a left subtree, it is a link that we created on a
* previous pass, so we should unlink it and visit this node.
*/
else {
succ.left = null;
sum += node.val;
node.val = sum;
node = node.left;
}
}
}
return root;
}
}
```

### Complexity Analysis:

**Time complexity**: O(n).**Space Complexity:**O(1).