# 1038. Binary Search Tree to Greater Sum Tree

Given the root of a binary search tree with distinct values, modify it so that every node has a new value equal to the sum of the values of the original tree that are greater than or equal to node.val.

Example:

Input: [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]

# Solution

Approach 1: inorder traversal from right to left.

# Code (Python)

Approach 1:

class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        if not root:
            return
        node = root
        stack = [node]
        while node.right:
            node = node.right
            stack.append(node)
        
        total = 0
        while stack:
            node = stack.pop()
            total += node.val
            node.val = total
            if node.left:
                current = node.left
                stack.append(current)
                while current.right:
                    current = current.right
                    stack.append(current)
        
        return root

# Code (C++)

Approach 1:

Approach 2: