Problem Description

You are given the root of a Binary Search Tree (BST). Your task is to transform it into a "Greater Tree" where each node's value is updated to be the sum of its original value plus all values in the tree 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 [4, 1, 6, 0, 2, 5, 7, 3, 8], each node should be updated as follows:

• Node with value 8 becomes 8 (no values greater than it)
• Node with value 7 becomes 7 + 8 = 15
• Node with value 6 becomes 6 + 7 + 8 = 21
• Node with value 5 becomes 5 + 6 + 7 + 8 = 26
• And so on...

The solution uses a reverse in-order traversal (right → root → left) to visit nodes in descending order. By maintaining a running sum s of all visited nodes, we can efficiently update each node's value to include the sum of all greater values. The traversal order ensures we always process larger values before smaller ones, allowing us to accumulate the sum as we go.

The key insight is that in a BST, a reverse in-order traversal visits nodes from largest to smallest, making it perfect for accumulating the sum of all greater values encountered so far.

Flowchart Walkthrough

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

Is it a graph?

• Yes: While this is specifically a tree problem, a tree is a special type of graph (connected acyclic graph). The problem involves nodes with connections (parent-child relationships).

Is it a tree?

• Yes: The problem explicitly states we're working with a Binary Search Tree (BST), which is a specialized tree structure where nodes follow a specific ordering property.

DFS

• Yes: Since we're dealing with a tree problem, the flowchart directs us to use Depth-First Search (DFS).

Conclusion: The flowchart suggests using DFS for this tree traversal problem.

This aligns perfectly with our solution approach. The problem requires us to visit every node and update its value based on all nodes with greater values. DFS allows us to traverse the tree systematically. Specifically, we use a modified in-order traversal (right → root → left) to visit nodes in descending order of their values, which is ideal for accumulating the sum of greater values as we traverse.

The DFS approach is optimal here because:

1. We need to visit every node exactly once
2. The tree structure naturally lends itself to recursive traversal
3. By choosing the right traversal order (reverse in-order), we can solve the problem in a single pass

Intuition

The key insight comes from understanding what "greater values" means in a BST. In a BST, all values to the right of a node are greater than that node. If we could somehow visit all the greater values first and keep track of their sum, we could update each node as we encounter it.

Think about the in-order traversal of a BST - it visits nodes in ascending order (left → root → right). What if we reversed this? A reverse in-order traversal (right → root → left) would visit nodes in descending order - from largest to smallest. This is exactly what we need!

By traversing the tree in descending order, we can maintain a running sum of all values we've seen so far. When we reach any node, our running sum already contains all values greater than the current node. We just need to:

1. Add the current node's value to our running sum
2. Update the current node's value to this new sum
3. Continue to smaller values

For example, consider a simple BST: [4, 2, 6, 1, 3, 5, 7]. A reverse in-order traversal visits in order: 7 → 6 → 5 → 4 → 3 → 2 → 1.

• When we visit 7, sum = 0, update node to 0 + 7 = 7
• When we visit 6, sum = 7, update node to 7 + 6 = 13
• When we visit 5, sum = 13, update node to 13 + 5 = 18
• And so on...

Each node gets updated with the sum of itself plus all previously visited (greater) values. The beauty of this approach is its simplicity - we solve the problem in a single traversal with just one variable to track the running sum.

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

Solution Approach

The implementation uses a recursive DFS with a reverse in-order traversal pattern. Here's how the solution works:

Data Structure and Variables:

• We maintain a single variable s as our running sum, initialized to 0
• The variable is declared as nonlocal inside the nested function to allow modification across recursive calls

Algorithm Steps:

1. Define the DFS function: Create a recursive helper function dfs(root) that will traverse the tree.

2. Base Case: If the current node is None, simply return. This handles leaf nodes' children and empty trees.

3. Reverse In-order Traversal:

   • First, recursively traverse the right subtree: dfs(root.right)
   • Then, process the current node:
     • Add the current node's value to the running sum: s += root.val
     • Update the node's value to the new sum: root.val = s
   • Finally, recursively traverse the left subtree: dfs(root.left)

4. Start the traversal: Call dfs(root) to begin the process from the root node.

5. Return the modified tree: Return the root of the transformed tree.

Why this works:

• By visiting the right subtree first, we ensure we process all nodes with greater values before the current node
• The running sum s accumulates all values as we traverse, so when we update a node, s contains the sum of all greater values plus the current value
• The left subtree is visited last because all its values are smaller than the current node

Time Complexity: O(n) where n is the number of nodes, as we visit each node exactly once.

Space Complexity: O(h) where h is the height of the tree, due to the recursive call stack. In the worst case (skewed tree), this could be O(n).

Example Walkthrough

Let's walk through a small BST example to see how the reverse in-order traversal transforms it into a Greater Tree.

Initial BST:

      4
     / \
    2   5
   /
  1

We'll trace through the algorithm step by step, tracking our running sum s (initially 0).

Step 1: Start at root (4)

• Call dfs(4)
• First, we need to traverse the right subtree before processing node 4

Step 2: Traverse right to node 5

• Call dfs(5)
• Node 5 has no right child, so dfs(None) returns immediately
• Process node 5:
  • s = 0 + 5 = 5
  • Update node 5's value to 5
• Node 5 has no left child, so dfs(None) returns immediately
• Return to node 4

Step 3: Process node 4

• Now we can process node 4:
  • s = 5 + 4 = 9
  • Update node 4's value to 9
• Next, traverse the left subtree

Step 4: Traverse left to node 2

• Call dfs(2)
• Node 2 has no right child, so dfs(None) returns immediately
• Process node 2:
  • s = 9 + 2 = 11
  • Update node 2's value to 11
• Traverse left to node 1

Step 5: Process node 1

• Call dfs(1)
• Node 1 has no right child, so dfs(None) returns immediately
• Process node 1:
  • s = 11 + 1 = 12
  • Update node 1's value to 12
• Node 1 has no left child, so dfs(None) returns immediately
• Return to node 2, then to node 4

Final Greater Tree:

       9
      / \
    11   5
   /
  12

Verification:

• Node 5: Original value 5 + (no greater values) = 5 ✓
• Node 4: Original value 4 + (5) = 9 ✓
• Node 2: Original value 2 + (4 + 5) = 11 ✓
• Node 1: Original value 1 + (2 + 4 + 5) = 12 ✓

The traversal order was: 5 → 4 → 2 → 1 (descending), and each node was updated with the sum of itself plus all previously visited (greater) values.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the binary search tree. The algorithm performs a modified in-order traversal (right-root-left) that visits each node exactly once. Each visit involves a constant amount of work (adding to the sum and updating the node value), so the total time complexity is linear with respect to the number of nodes.

Space Complexity: O(h) where h is the height of the binary search tree. The space complexity comes from the recursive call stack used during the depth-first search traversal. In the worst case (a skewed tree), the height could be O(n), making the space complexity O(n). In the best case (a balanced tree), the height would be O(log n), making the space complexity O(log n). The additional space used for the variable s is O(1) and doesn't affect the overall space complexity.

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

Common Pitfalls

1. Using a Class Variable Instead of Nonlocal

A common mistake is trying to use a class variable to maintain the running sum, which can cause issues with multiple test cases or concurrent calls.

Incorrect approach:

class Solution:
    def __init__(self):
        self.running_sum = 0  # Class variable - persists between calls!
  
    def convertBST(self, root: TreeNode) -> TreeNode:
        def dfs(node):
            if not node:
                return
            dfs(node.right)
            self.running_sum += node.val  # Using class variable
            node.val = self.running_sum
            dfs(node.left)
      
        # Problem: running_sum might not be 0 if method called multiple times
        dfs(root)
        return root

Solution: Always reset the running sum or use a local variable with nonlocal:

def convertBST(self, root: TreeNode) -> TreeNode:
    running_sum = 0  # Local variable
  
    def dfs(node):
        nonlocal running_sum  # Properly access outer scope variable
        if not node:
            return
        dfs(node.right)
        running_sum += node.val
        node.val = running_sum
        dfs(node.left)
  
    dfs(root)
    return root

2. Wrong Traversal Order

Using standard in-order traversal (left → root → right) instead of reverse in-order traversal will produce incorrect results.

Incorrect approach:

def convertBST(self, root: TreeNode) -> TreeNode:
    running_sum = 0
  
    def dfs(node):
        nonlocal running_sum
        if not node:
            return
        dfs(node.left)  # Wrong: visiting smaller values first!
        running_sum += node.val
        node.val = running_sum
        dfs(node.right)  # Larger values visited last
  
    dfs(root)
    return root

This would accumulate smaller values into larger ones, which is the opposite of what we want.

3. Forgetting to Update the Node Value

Sometimes developers correctly maintain the running sum but forget to actually update the node's value.

Incorrect approach:

def dfs(node):
    nonlocal running_sum
    if not node:
        return
    dfs(node.right)
    running_sum += node.val  # Only updating sum
    # Missing: node.val = running_sum
    dfs(node.left)

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

The problem typically expects the original tree to be modified in-place, but some might try to create a new tree structure.

Incorrect (and inefficient) approach:

def convertBST(self, root: TreeNode) -> TreeNode:
    if not root:
        return None
  
    # Creating new nodes instead of modifying existing ones
    new_root = TreeNode()
    # ... complex logic to rebuild tree
    return new_root  # Wrong: should return modified original root

5. Not Handling Edge Cases

Failing to handle edge cases like empty trees or single-node trees.

Better approach with explicit edge case handling:

def convertBST(self, root: TreeNode) -> TreeNode:
    # Explicitly handle empty tree (though the recursive solution handles this naturally)
    if not root:
        return root
  
    running_sum = 0
  
    def dfs(node):
        nonlocal running_sum
        if not node:
            return
        dfs(node.right)
        running_sum += node.val
        node.val = running_sum
        dfs(node.left)
  
    dfs(root)
    return root

Best Practice Solution:

Use a local variable with nonlocal keyword, perform reverse in-order traversal, and modify nodes in-place. This ensures the solution is self-contained, correct, and efficient.