# 538 Convert BST to Greater Tree

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 the 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.

Example 1:

``````            4 (30)
/        \
/          \
1 (36)           6 (21)
/   \             /   \
/     \           /     \
0 (36)  2 (35)   5 (26)  7 (15)
\                \
3 (33)           8 (8)

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
``````

Example 2:

``````Input: root = [0,null,1]
Output: [1,null,1]
``````

Constraints:

• The number of nodes in the tree is in the range `[0, 104]`.
• `-104 <= Node.val <= 104`
• All the values in the tree are unique.
• `root` is guaranteed to be a valid binary search tree.
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 `````` ``````# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def __init__(self): self.total = 0 def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]: def dfs(node): if not node: return dfs(node.right) self.total += node.val node.val = self.total dfs(node.left) dfs(root) return root``````