## Convert BST to Greater Tree

• Time:O(n)
• Space:O(\log n)

## C++

``````class Solution {
public:
TreeNode* convertBST(TreeNode* root) {
int prefix = 0;
reversedInorder(root, prefix);
return root;
}

private:
void reversedInorder(TreeNode* root, int& prefix) {
if (!root)
return;

reversedInorder(root->right, prefix);
prefix += root->val;
root->val = prefix;
reversedInorder(root->left, prefix);
}
};
``````

## JAVA

``````class Solution {
public TreeNode convertBST(TreeNode root) {
reversedInorder(root);
return root;
}

private int prefix = 0;

private void reversedInorder(TreeNode root) {
if (root == null)
return;

reversedInorder(root.right);
prefix += root.val;
root.val = prefix;
reversedInorder(root.left);
}
}
``````

## Python

``````class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
prefix = 0

def reversedInorder(root: Optional[TreeNode]) -> None:
nonlocal prefix
if not root:
return

reversedInorder(root.right)
prefix += root.val
root.val = prefix
reversedInorder(root.left)

reversedInorder(root)
return root
``````