### Description:

Given the root of 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.

As a reminder, a binary search tree is a tree that satisfies these constraints:

The left subtree of a node contains only nodes with keys less than the node's key.

The right subtree of a node contains only nodes with keys greater than the node's key.

Both the left and right subtrees must also be binary search trees.

### Solution:

Time Complexity : O(n)

Space Complexity: O(n)

```
var convertBST = function(root) {
// Keep track of the total during the traversal of the tree
let sum = 0
// Traverse right, middle, left and continually add to the sum
function trans(root) {
if(root === null) return 0;
trans(root.right)
root.val+=sum
sum = root.val
trans(root.left)
}
// Traverse the tree
trans(root)
return root
};
```

## Top comments (0)