Binary Search Tree To Greater Sum Tree - Leetcode Solution

The Binary Search Tree to Greater Sum Tree problem on LeetCode requires us to transform a binary search tree into a greater sum tree. The greater sum tree is a binary tree where the value of a node is the sum of itself and all nodes greater than itself.

To solve the problem, we need to traverse the binary search tree in reverse in-order, which means that we start from the rightmost node and go towards the leftmost node. During the traversal, we maintain the sum of all nodes greater than the current node and update the value of the current node with this sum.

Here's the algorithm for the solution:

1. Initialize a global variable sum to 0.
2. Traverse the binary search tree in reverse in-order.
3. For each node, update its value with sum and then add its value to sum.
4. Return the modified binary search tree.

Here's the Python code that implements the algorithm:

class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        self.sum = 0
        
        def reverse_inorder(node):
            if node:
                reverse_inorder(node.right)
                self.sum += node.val
                node.val = self.sum
                reverse_inorder(node.left)
        
        reverse_inorder(root)
        return root

In the above code, we first initialize the sum variable to 0. Then, we define a helper function reverse_inorder that takes a node as the argument. The function first checks if the node exists and then recursively traverses the right subtree, updates the value of the node with the sum variable, updates the sum variable with the value of the node, and then recursively traverses the left subtree.

Finally, we call the reverse_inorder function with the root of the binary search tree and return the modified tree.

1