LeetCode 1038: Binary Search Tree to Greater Sum Tree

Problem Restatement

We are given the root of a Binary Search Tree (BST).

We need to convert it into a Greater Sum Tree (GST) where every node’s value is replaced by the sum of all values greater than or equal to that node’s original value in the tree.

The official constraints state that the number of nodes is in [1, 100] and 0 <= Node.val <= 100.

Input and Output

Function shape:

def bstToGst(root: Optional[TreeNode]) -> Optional[TreeNode]:
    ...

Examples

Example 1:

root = [4, 1, 6, 0, 2, 5, 7, None, None, None, 3, None, None, None, 8]

After transformation, node 4 becomes 4 + 5 + 6 + 7 + 8 = 30.

Answer: each node is updated with cumulative sum from right to left in inorder.

Key Insight

In a BST, inorder traversal visits nodes in ascending order.

Reverse inorder (right → node → left) visits nodes in descending order.

We maintain a running sum. For each node in reverse inorder:

1. Add the node’s value to the running sum.
2. Replace the node’s value with the running sum.

This gives each node the sum of all values ≥ its original value.

Correctness

When visiting node in reverse inorder, all nodes visited so far have values ≥ node.val (since we go right-first). The running sum therefore equals the sum of all values ≥ node.val, which is exactly the new value.

Edge Cases

• A missing child should not contribute a fake value to min/max or path computations.
• Leaf nodes often define the base case; verify the behavior on a single-node tree.
• When passing state down the tree, update it before visiting children that depend on the current node.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

class Solution:
    def bstToGst(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        self.acc = 0

        def reverse_inorder(node):
            if node is None:
                return
            reverse_inorder(node.right)
            self.acc += node.val
            node.val = self.acc
            reverse_inorder(node.left)

        reverse_inorder(root)
        return root

Testing

def inorder_vals(root):
    if not root:
        return []
    return inorder_vals(root.left) + [root.val] + inorder_vals(root.right)

def run_tests():
    s = Solution()
    root = TreeNode(4,
        TreeNode(1, TreeNode(0), TreeNode(2, None, TreeNode(3))),
        TreeNode(6, TreeNode(5), TreeNode(7, None, TreeNode(8)))
    )
    s.bstToGst(root)
    vals = inorder_vals(root)
    assert vals == [36, 36, 35, 33, 30, 21, 15, 8]

    print("all tests passed")

run_tests()