# Convert BST to Greater Tree

## Intuition

The sum of all keys greater or equal to a node is the sum of all nodes minues the sum all keys less than the node. So we could use 2 inorder traversal to solve this problem.

In the first traversal, we calculate the sum of all nodes. In the second traversal, we keep the sum of all previous visited nodes, and update it to the total_sum - previous_sum.

## Solution

``````
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
def convertBST(self, root: TreeNode) -> TreeNode:
self.total_sum = 0
self.previous_sum = 0
self._inorder1(root)
self._inorder2(root)
return root

def _inorder1(self, node):
if node is None:
return
self._inorder1(node.left)
self.total_sum += node.val
self._inorder1(node.right)

def _inorder2(self, node):
if node is None:
return
self._inorder2(node.left)
tmp = node.val
node.val = self.total_sum - self.previous_sum
self.previous_sum += tmp
self._inorder2(node.right)

``````