The top solutions are ingenious.

My initial thought was to calculate the sum of the entire BST, then starting from the leftest node, add the sum to every node following an inorder traversal.

Overall running time is 2N ~ O(N) for N nodes

```
public class Solution {
int sum = 0;
public TreeNode convertBST(TreeNode root) {
preorder(root);
inorder(root);
return root;
}
private void preorder(TreeNode root){
if(root == null) return;
sum += root.val;
preorder(root.left);
preorder(root.right);
}
private void inorder(TreeNode root){
if(root == null) return;
inorder(root.left);
sum -= root.val;
root.val += sum;
inorder(root.right);
}
}
```