LeetCode 1038 - Binary Search Tree to Greater Sum Tree

The problem gives us the root of a Binary Search Tree, abbreviated as BST, and asks us to transform it into a Greater Sum Tree. In a Binary Search Tree, every node follows an important ordering rule: - All values in the left subtree are smaller than the current node.

leetcodemediumtreedepth-first-searchbinary-search-treebinary-tree

LeetCode Problem 1038

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree

Solution

Problem Understanding

The problem gives us the root of a Binary Search Tree, abbreviated as BST, and asks us to transform it into a Greater Sum Tree.

In a Binary Search Tree, every node follows an important ordering rule:

  • All values in the left subtree are smaller than the current node.
  • All values in the right subtree are larger than the current node.

The transformation rule is:

Replace every node's value with:

current value + sum of all values greater than it in the tree.

This means that after transformation, each node contains the sum of all original node values that are greater than or equal to itself.

For example, suppose a node originally contains value 4, and the values greater than 4 in the BST are 5, 6, 7, and 8.

The updated value becomes:

4 + 5 + 6 + 7 + 8 = 30

The tree structure itself does not change. Only the values stored inside nodes are modified.

The input is the root node of a BST. The output should be the same tree root after all node values have been updated.

The constraints are relatively small:

  • The tree contains between 1 and 100 nodes.
  • Node values are unique.
  • Values range from 0 to 100.

Although the constraints are small enough that even slower approaches could pass, the problem is fundamentally about recognizing the BST property and exploiting it efficiently.

Several edge cases are important:

  • A tree with only one node. The node should remain unchanged because there are no greater values.
  • A completely right-skewed tree, where values are already increasing in a chain.
  • A completely left-skewed tree.
  • The smallest possible value 0.
  • The largest node already having no greater elements.
  • Empty child pointers during traversal.

Because the values are unique and the tree is guaranteed to be a valid BST, we can safely rely on BST ordering during traversal.

Approaches

Brute Force Approach

A straightforward approach is to process every node independently.

For each node:

  1. Traverse the entire tree.
  2. Find all node values greater than the current node's value.
  3. Compute their sum.
  4. Add that sum to the node.

This works because it directly follows the definition of the problem.

However, it is inefficient. If the tree has n nodes, and for every node we traverse all n nodes again, the total complexity becomes O(n²).

Even though the constraints are small enough for this to pass, the approach ignores the special structure of a BST.

Key Insight

The key observation is that an in-order traversal of a BST visits nodes in ascending order:

Left -> Node -> Right

If we reverse the traversal order:

Right -> Node -> Left

then nodes are visited in descending order.

This is extremely useful because when visiting a node in descending order, we have already processed all greater values.

We can maintain a running cumulative sum:

  • Start with 0
  • Visit larger nodes first
  • Add the current node value into the running sum
  • Replace the node value with the running sum

This allows us to transform the tree in a single traversal.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(h) For every node, traverse the entire tree again
Optimal O(n) O(h) Reverse in-order traversal processes nodes once

Here, h represents the height of the tree.

Algorithm Walkthrough

Optimal Reverse In-Order Traversal

  1. Initialize a variable called running_sum to 0.

This variable stores the cumulative total of all previously visited larger node values. 2. Perform a reverse in-order traversal.

Instead of visiting nodes in ascending order, visit them in descending order:

Right -> Node -> Left
  1. Recursively traverse the right subtree first.

The right subtree contains all larger values in a BST. Processing it first ensures that the cumulative sum already includes all greater nodes before updating the current node. 4. Update the current node.

Add the current node's original value to running_sum.

Then overwrite the node's value with the updated cumulative sum. 5. Recursively traverse the left subtree.

The left subtree contains smaller values, so these nodes should include the updated current node value in their future sums. 6. Continue until all nodes have been processed. 7. Return the original root.

The tree has been modified in place.

Why it works

The reverse in-order traversal visits nodes from largest to smallest.

At any moment during traversal, running_sum contains the sum of all previously visited nodes, which are exactly the nodes greater than the current node.

By adding the current node value into running_sum and storing the result back into the node, we correctly compute:

current value + sum of greater values

Because every node is visited exactly once in descending order, the transformation is correct for the entire tree.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

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

        def reverse_inorder(node: Optional[TreeNode]) -> None:
            nonlocal running_sum

            if not node:
                return

            # Visit larger values first
            reverse_inorder(node.right)

            # Update running sum and node value
            running_sum += node.val
            node.val = running_sum

            # Visit smaller values
            reverse_inorder(node.left)

        reverse_inorder(root)
        return root

The implementation follows the reverse in-order traversal strategy directly.

The variable running_sum is declared outside the recursive helper so that every recursive call shares the same cumulative state.

The helper function first processes the right subtree because larger BST values live there.

After all larger values are processed, the current node value is added into running_sum, and the node is updated.

Finally, the traversal moves into the left subtree, where smaller nodes should include the newly updated cumulative sum.

The tree is modified in place, so the original root reference is returned.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func bstToGst(root *TreeNode) *TreeNode {
    runningSum := 0

    var reverseInorder func(node *TreeNode)

    reverseInorder = func(node *TreeNode) {
        if node == nil {
            return
        }

        // Visit larger values first
        reverseInorder(node.Right)

        // Update running sum and node value
        runningSum += node.Val
        node.Val = runningSum

        // Visit smaller values
        reverseInorder(node.Left)
    }

    reverseInorder(root)

    return root
}

The Go implementation mirrors the Python solution closely.

Instead of Python's nonlocal, Go closures automatically capture runningSum from the surrounding scope.

Go uses nil checks instead of Python's None.

Because node values are at most 100 and there are at most 100 nodes, integer overflow is not a concern with Go's standard int type.

Worked Examples

Example 1

Input:

[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]

The BST structure is:

        4
      /   \
     1     6
    / \   / \
   0   2 5   7
        \     \
         3     8

Reverse in-order traversal order:

8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0
Current Node Running Sum Before Running Sum After Updated Node Value
8 0 8 8
7 8 15 15
6 15 21 21
5 21 26 26
4 26 30 30
3 30 33 33
2 33 35 35
1 35 36 36
0 36 36 36

Final tree:

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

Output:

[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

Example 2

Input:

[0,null,1]

Tree:

0
 \
  1

Traversal order:

1 -> 0
Current Node Running Sum Before Running Sum After Updated Node Value
1 0 1 1
0 1 1 1

Final tree:

1
 \
  1

Output:

[1,null,1]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every node is visited exactly once
Space O(h) Recursive call stack depth equals tree height

The algorithm performs a single DFS traversal through the tree.

No extra data structures proportional to the number of nodes are used. The only additional memory comes from recursion stack frames.

In the worst case of a completely skewed tree, the height becomes n, leading to O(n) recursion space. In a balanced tree, the height is O(log n).

Test Cases

# Helper utilities for testing

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(values):
    if not values:
        return None

    nodes = [
        TreeNode(v) if v is not None else None
        for v in values
    ]

    kids = deque(nodes[1:])
    root = nodes[0]

    for node in nodes:
        if node:
            if kids:
                node.left = kids.popleft()
            if kids:
                node.right = kids.popleft()

    return root

def tree_to_list(root):
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        node = queue.popleft()

        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)

    while result and result[-1] is None:
        result.pop()

    return result

class Solution:
    def bstToGst(self, root):
        running_sum = 0

        def reverse_inorder(node):
            nonlocal running_sum

            if not node:
                return

            reverse_inorder(node.right)

            running_sum += node.val
            node.val = running_sum

            reverse_inorder(node.left)

        reverse_inorder(root)
        return root

sol = Solution()

# Example 1
root = build_tree([4,1,6,0,2,5,7,None,None,None,3,None,None,None,8])
result = sol.bstToGst(root)
assert tree_to_list(result) == [30,36,21,36,35,26,15,None,None,None,33,None,None,None,8]  # Standard balanced BST

# Example 2
root = build_tree([0,None,1])
result = sol.bstToGst(root)
assert tree_to_list(result) == [1,None,1]  # Small two-node tree

# Single node
root = build_tree([5])
result = sol.bstToGst(root)
assert tree_to_list(result) == [5]  # No greater values exist

# Left-skewed tree
root = build_tree([3,2,None,1])
result = sol.bstToGst(root)
assert tree_to_list(result) == [3,5,None,6]  # Descending structure

# Right-skewed tree
root = build_tree([1,None,2,None,3])
result = sol.bstToGst(root)
assert tree_to_list(result) == [6,None,5,None,3]  # Ascending chain

# Larger balanced BST
root = build_tree([5,3,7,2,4,6,8])
result = sol.bstToGst(root)
assert tree_to_list(result) == [26,33,15,35,30,21,8]  # Fully balanced BST

# Minimum value case
root = build_tree([0])
result = sol.bstToGst(root)
assert tree_to_list(result) == [0]  # Smallest allowed value

Test Summary

Test Why
Balanced BST example Verifies standard transformation behavior
Two-node tree Checks small input handling
Single node Ensures node remains unchanged
Left-skewed tree Tests deep left recursion
Right-skewed tree Tests deep right recursion
Larger balanced BST Verifies cumulative updates across many nodes
Minimum value node Confirms handling of value 0

Edge Cases

Single Node Tree

A tree containing only one node is the smallest valid input.

This case can expose bugs where implementations incorrectly assume that every node has larger or smaller neighbors. The correct behavior is that the node remains unchanged because there are no greater values.

The implementation handles this naturally because the traversal visits the node once, adds its value to running_sum, and stores the same value back.

Completely Right-Skewed Tree

A right-skewed BST behaves similarly to a linked list with increasing values.

This case is important because reverse in-order traversal immediately walks down the deepest path first. Incorrect traversal ordering would produce wrong cumulative sums.

The implementation correctly processes nodes from largest to smallest, ensuring that each node accumulates all greater values before updating.

Completely Left-Skewed Tree

A left-skewed BST contains nodes only on the left side.

This tests whether the algorithm properly handles trees where right subtrees are frequently None.

The recursive helper safely returns when encountering None, so missing children never cause issues.

Largest Value Node

The maximum node in the BST should remain unchanged because there are no greater values.

This is important because some incorrect implementations accidentally double count values or update the maximum node incorrectly.

Since reverse in-order traversal visits the largest node first when running_sum is still 0, the node correctly becomes:

0 + original_value

which leaves it unchanged.