Problem Description

You are given the root of a Binary Search Tree (BST). Your task is to convert it into a Greater Tree where each node's value is replaced by the sum of its original value plus all values in the BST that are greater than it.

In a BST, remember that:

• All nodes in the left subtree have values less than the current node
• All nodes in the right subtree have values greater than the current node
• Both subtrees are also valid BSTs

For example, if you have a BST with values [1, 2, 3, 4, 5], after conversion:

• Node with value 5 becomes 5 (no values greater than it)
• Node with value 4 becomes 4 + 5 = 9
• Node with value 3 becomes 3 + 5 + 4 = 12
• Node with value 2 becomes 2 + 5 + 4 + 3 = 14
• Node with value 1 becomes 1 + 5 + 4 + 3 + 2 = 15

The solution uses a reverse in-order traversal (right → root → left) to visit nodes from largest to smallest value. As we traverse, we maintain a running sum s that accumulates all values seen so far. When we visit each node, we add its current value to the sum, then update the node's value to this new sum. This ensures each node gets the sum of itself and all greater values.

The traversal order is crucial because in a BST, visiting nodes in right-root-left order means we encounter values in descending order, allowing us to accumulate the sum of greater values as we go.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A tree is a special type of graph (specifically, a connected acyclic graph). Binary Search Trees are graph structures with nodes and edges connecting parent nodes to their children.

Is it a tree?

• Yes: The problem explicitly states we're working with a Binary Search Tree (BST), which is a tree data structure where each node has at most two children.

DFS

• We arrive at DFS: Since we're dealing with a tree structure, the flowchart leads us directly to using Depth-First Search (DFS).

Conclusion: The flowchart suggests using a DFS approach for this problem. This makes sense because:

1. We need to traverse all nodes in the tree to calculate the sum of greater values
2. The solution requires visiting nodes in a specific order (reverse in-order: right → root → left) to accumulate values from largest to smallest
3. DFS allows us to recursively traverse the tree structure and maintain the running sum as we backtrack
4. The recursive nature of DFS perfectly matches the recursive structure of the tree, making it ideal for this transformation problem

The DFS pattern is implemented in the solution through the recursive dfs function that traverses right subtree first, processes the current node, then traverses the left subtree, maintaining a running sum throughout the traversal.

Intuition

The key insight comes from understanding what "sum of all keys greater than the original key" means in a BST. In a BST, all values to the right of a node are greater than it, and all values to the left are smaller. So for any node, we need to add all values that appear to its right in an in-order traversal.

Think about an in-order traversal of a BST - it gives us values in ascending order. If we reverse this and do a reverse in-order traversal (right → root → left), we get values in descending order. This is the crucial observation!

As we traverse in descending order, we can maintain a running sum. When we visit each node:

1. We've already visited all nodes with greater values (they came before in our reverse traversal)
2. We can add the current node's value to our running sum
3. We update the node's value to this accumulated sum

For example, if our BST has values [1, 2, 3, 4, 5]:

• We first visit 5 (largest), sum = 0 + 5 = 5, node becomes 5
• Then visit 4, sum = 5 + 4 = 9, node becomes 9
• Then visit 3, sum = 9 + 3 = 12, node becomes 12
• And so on...

This way, each node automatically gets the sum of itself plus all greater values, because we've been accumulating exactly those values as we traverse from largest to smallest. The beauty of this approach is that we only need one pass through the tree with O(1) extra space for the running sum variable s.

Learn more about Tree, Depth-First Search, Binary Search Tree and Binary Tree patterns.

Solution Approach

The solution implements a recursive DFS with reverse in-order traversal (right-root-left). Here's how the implementation works:

Core Algorithm Structure:

1. We define a helper function dfs that recursively traverses the tree
2. We maintain a global variable s to track the running sum of all visited nodes
3. We traverse in the order: right subtree → current node → left subtree

Step-by-step Implementation:

def dfs(root: Optional[TreeNode]):
    if root is None:
        return
    dfs(root.right)    # Visit right subtree first (larger values)
    nonlocal s         # Access the outer scope variable
    s += root.val      # Add current value to running sum
    root.val = s       # Update node with accumulated sum
    dfs(root.left)     # Visit left subtree last (smaller values)

Key Implementation Details:

1. Base Case: When we encounter a None node, we simply return without doing anything

2. Recursive Order: The critical part is visiting root.right before processing the current node. This ensures we process nodes from largest to smallest value

3. Running Sum Update:

   • We use nonlocal s to modify the outer scope's sum variable
   • First add the current node's value to s: s += root.val
   • Then update the node's value to the accumulated sum: root.val = s

4. In-place Modification: The tree is modified in-place - we directly update each node's value rather than creating a new tree

The main function simply initializes s = 0, calls the DFS helper function with the root, and returns the modified tree. The time complexity is O(n) where n is the number of nodes (we visit each node once), and space complexity is O(h) where h is the height of the tree (for the recursion stack).

Example Walkthrough

Let's walk through a small BST example to illustrate the solution approach:

Initial BST:
      4
     / \
    1   6
   / \ / \
  0  2 5  7
      \    \
       3    8

We'll perform a reverse in-order traversal (right → root → left) with a running sum s = 0.

Traversal Steps:

1. Start at root (4), go right to 6, then right to 7, then right to 8

   • Visit node 8: s = 0 + 8 = 8, update node 8 → 8
   • No more right children, process 7

2. Visit node 7: s = 8 + 7 = 15, update node 7 → 15

   • Go left (none exists), backtrack to 6

3. Visit node 6: s = 15 + 6 = 21, update node 6 → 21

   • Go left to 5

4. Visit node 5: s = 21 + 5 = 26, update node 5 → 26

   • No children, backtrack to 6, then to 4

5. Visit node 4: s = 26 + 4 = 30, update node 4 → 30

   • Go left to 1, then right to 2, then right to 3

6. Visit node 3: s = 30 + 3 = 33, update node 3 → 33

   • No children, backtrack to 2

7. Visit node 2: s = 33 + 2 = 35, update node 2 → 35

   • No left child, backtrack to 1

8. Visit node 1: s = 35 + 1 = 36, update node 1 → 36

   • Go left to 0

9. Visit node 0: s = 36 + 0 = 36, update node 0 → 36

   • No children, traversal complete

Final Greater Tree:

      30
     /  \
    36   21
   / \   / \
  36 35 26  15
      \      \
      33      8

Each node now contains the sum of its original value plus all values greater than it in the original BST. For instance, the original node 4 had values {5, 6, 7, 8} greater than it, so its new value is 4 + 5 + 6 + 7 + 8 = 30.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the number of nodes in the binary search tree. This is because the algorithm performs a depth-first search (DFS) traversal that visits each node exactly once. The DFS function is called once for each node in the tree, and at each node, it performs constant time operations (adding to the sum s and updating the node's value).

The space complexity is O(n), where n is the number of nodes in the binary search tree. This space is used by the recursive call stack during the DFS traversal. In the worst case, when the tree is completely unbalanced (essentially a linked list), the recursion depth can reach n levels deep, requiring O(n) space on the call stack. In the best case of a balanced tree, the space complexity would be O(log n) for the recursion stack, but we consider the worst-case scenario for complexity analysis.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Use nonlocal for the Running Sum

One of the most common mistakes is forgetting to declare nonlocal running_sum inside the nested function. Without this declaration, Python treats running_sum as a local variable when you try to modify it, leading to an UnboundLocalError.

Incorrect Code:

def bstToGst(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    def reverse_inorder_traversal(node):
        if node is None:
            return
        reverse_inorder_traversal(node.right)
        running_sum += node.val  # ERROR: UnboundLocalError
        node.val = running_sum
        reverse_inorder_traversal(node.left)
  
    running_sum = 0
    reverse_inorder_traversal(root)
    return root

Solution: Always include nonlocal running_sum before modifying the variable, or use a mutable container like a list [0] to store the sum:

# Option 1: Using nonlocal
nonlocal running_sum
running_sum += node.val

# Option 2: Using a list to avoid nonlocal
running_sum = [0]  # In main function
running_sum[0] += node.val  # In helper function
node.val = running_sum[0]

2. Incorrect Traversal Order

Another critical mistake is using standard in-order traversal (left → root → right) instead of reverse in-order traversal. This would process nodes from smallest to largest, giving incorrect results.

Incorrect Code:

def reverse_inorder_traversal(node):
    if node is None:
        return
    reverse_inorder_traversal(node.left)  # WRONG: Processing left first
    nonlocal running_sum
    running_sum += node.val
    node.val = running_sum
    reverse_inorder_traversal(node.right)  # WRONG: Processing right last

This would accumulate sums in ascending order, causing each node to contain the sum of all values less than or equal to it, which is the opposite of what we want.

Solution: Always maintain the correct order: right → root → left to ensure you're processing nodes from largest to smallest value.

3. Creating a New Tree Instead of Modifying In-Place

Some implementations might accidentally create new nodes instead of modifying the existing tree, which wastes memory and may not meet the problem requirements.

Incorrect Approach:

def bstToGst(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    def build_greater_tree(node):
        if node is None:
            return None
        new_node = TreeNode()  # Creating new nodes unnecessarily
        new_node.right = build_greater_tree(node.right)
        nonlocal running_sum
        running_sum += node.val
        new_node.val = running_sum
        new_node.left = build_greater_tree(node.left)
        return new_node

Solution: Modify the existing nodes directly by updating node.val rather than creating new TreeNode objects. This is more efficient and typically what the problem expects.