LeetCode 538 - Convert BST to Greater Tree

LeetCode Problem 538

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

Solution

Problem Understanding

This problem asks us to transform a Binary Search Tree, abbreviated as BST, into a "Greater Tree". In the transformed tree, every node's value should become:

• its original value
• plus the sum of all values greater than it in the original BST

The structure of the tree does not change. Only the node values are updated.

A Binary Search Tree has an important ordering property:

• every value in the left subtree is smaller than the current node
• every value in the right subtree is larger than the current node

This ordering is the key observation that allows an efficient solution.

For example, consider this BST:

        4
      /   \
     1     6

The node 4 should become:

4 + 6 = 10

because 6 is greater than 4.

The node 1 should become:

1 + 4 + 6 = 11

because both 4 and 6 are greater than 1.

The node 6 remains 6 because there are no larger values.

The input is the root of a BST, and the expected output is the same tree after all node values have been updated.

The constraints tell us several important things:

• The tree can contain up to 10^4 nodes.
• Node values may be negative.
• All values are unique.
• The input is guaranteed to be a valid BST.

Because the tree can be fairly large, we should avoid algorithms worse than O(n log n) if possible. Since every node must be visited at least once, an O(n) solution is ideal.

Several edge cases are important:

• An empty tree, root = None
• A tree with only one node
• A completely skewed tree, which behaves like a linked list
• Trees containing negative values
• Trees where all larger values are concentrated on one side

The BST guarantee is especially important because the optimal solution depends entirely on BST ordering properties.

Approaches

Brute Force Approach

A straightforward approach is to process every node independently.

For each node:

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

This works because every node explicitly calculates the exact values greater than itself.

However, the inefficiency is obvious. If the tree contains n nodes:

• we process n nodes
• for each node, we potentially scan all n nodes again

This leads to O(n^2) time complexity.

With up to 10^4 nodes, this can become too slow.

Key Insight for the Optimal Solution

The BST property gives us sorted ordering automatically.

In a normal inorder traversal:

Left -> Node -> Right

BST values are visited in ascending order.

For this problem, we need the sum of all larger values. That means we should process nodes from largest to smallest.

We can achieve this using a reverse inorder traversal:

Right -> Node -> Left

This visits nodes in descending order.

While traversing:

• maintain a running sum of all previously visited nodes
• since traversal is descending, previously visited nodes are all greater
• update the current node using that running sum

This transforms 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 tree again to compute greater sums
Optimal	O(n)	O(h)	Reverse inorder traversal processes nodes in descending order

Here, h represents the height of the tree.

Algorithm Walkthrough

Optimal Algorithm: Reverse Inorder Traversal

1. Initialize a variable called running_sum to 0.

This variable stores the sum of all node values already visited during traversal. Since we traverse from largest to smallest, it always represents the sum of greater values. 2. Start a reverse inorder traversal.

Instead of the usual inorder traversal:

Left -> Node -> Right

we use:

Right -> Node -> Left

This guarantees nodes are visited in descending order. 3. Recursively visit the right subtree first.

The right subtree contains larger values, so those nodes must be processed before the current node. 4. Update the current node.

When visiting a node:

• add its original value to running_sum
• replace the node's value with the updated running_sum

Example:

running_sum = 15
current node = 6

running_sum = 21
node.val = 21

5. Recursively visit the left subtree.

The left subtree contains smaller values, so those nodes should use the updated running sum. 6. Continue until all nodes are processed. 7. Return the root of the modified tree.

Why it works

The correctness depends on reverse inorder traversal visiting BST nodes in descending order.

At any node:

• every previously visited node has a larger value
• running_sum therefore equals the sum of all greater values
• adding the current node's value produces the required Greater Tree value

Because every node is processed exactly once and in the correct order, the transformation is correct.

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 convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        running_sum = 0

        def reverse_inorder(node: Optional[TreeNode]) -> None:
            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

The implementation uses a nested helper function called reverse_inorder.

The variable running_sum is declared outside the helper so it can persist across recursive calls. The nonlocal keyword allows the nested function to modify it.

The traversal begins with the right subtree because larger values must be processed first.

When a node is visited:

running_sum += node.val
node.val = running_sum

This updates the node using the sum of all larger values plus its own original value.

Finally, the traversal proceeds into the left subtree so smaller nodes receive the updated accumulated sum.

The function modifies the tree in place and returns the original root reference.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func convertBST(root *TreeNode) *TreeNode {
    runningSum := 0

    var reverseInorder func(node *TreeNode)

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

        reverseInorder(node.Right)

        runningSum += node.Val
        node.Val = runningSum

        reverseInorder(node.Left)
    }

    reverseInorder(root)

    return root
}

The Go solution follows the same logic as the Python version.

Instead of using nonlocal, Go closures automatically capture variables from the surrounding scope, so runningSum can be updated directly inside the recursive function.

The base case checks for nil pointers before recursion.

Since Go passes pointers to tree nodes, modifying node.Val updates the original tree directly.

Integer overflow is not a concern because the constraints remain well within Go's standard integer range.

Worked Examples

Example 1

Input:

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

Reverse inorder 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
 \
  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 depends on tree height

The algorithm performs a single traversal of the tree, so time complexity is linear in the number of nodes.

The space complexity comes from recursion depth:

• O(log n) for balanced BSTs
• O(n) for completely skewed trees

No additional data structures proportional to n are used.

Test Cases

# Helper functions for testing

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

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

# Solution implementation

class Solution:
    def convertBST(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

# Test 1: Empty tree
assert Solution().convertBST(None) is None  # handles empty input

# Test 2: Single node
root = TreeNode(5)
Solution().convertBST(root)
assert root.val == 5  # no greater values exist

# Test 3: Example 2
root = TreeNode(0)
root.right = TreeNode(1)

Solution().convertBST(root)

assert root.val == 1  # 0 + 1
assert root.right.val == 1  # unchanged

# Test 4: Small balanced BST
root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)

Solution().convertBST(root)

assert root.val == 5
assert root.left.val == 6
assert root.right.val == 3

# Test 5: Left-skewed tree
root = TreeNode(3)
root.left = TreeNode(2)
root.left.left = TreeNode(1)

Solution().convertBST(root)

assert root.val == 3
assert root.left.val == 5
assert root.left.left.val == 6

# Test 6: Right-skewed tree
root = TreeNode(1)
root.right = TreeNode(2)
root.right.right = TreeNode(3)

Solution().convertBST(root)

assert root.val == 6
assert root.right.val == 5
assert root.right.right.val == 3

# Test 7: Tree with negative values
root = TreeNode(0)
root.left = TreeNode(-1)
root.right = TreeNode(2)

Solution().convertBST(root)

assert root.val == 2
assert root.left.val == 1
assert root.right.val == 2

# Test 8: Larger BST
root = TreeNode(4)
root.left = TreeNode(1)
root.right = TreeNode(6)
root.left.left = TreeNode(0)
root.left.right = TreeNode(2)
root.left.right.right = TreeNode(3)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)
root.right.right.right = TreeNode(8)

Solution().convertBST(root)

assert inorder_values(root) == [36, 36, 35, 33, 30, 26, 21, 15, 8]

Test Summary

Test	Why
Empty tree	Validates handling of None input
Single node	Ensures no unnecessary modification
Example 2	Verifies simple right-child transformation
Small balanced BST	Confirms standard BST behavior
Left-skewed tree	Tests recursion on one-sided trees
Right-skewed tree	Tests descending traversal correctness
Negative values	Ensures sums work with negatives
Larger BST	Validates full example-scale transformation

Edge Cases

Empty Tree

An empty tree is represented by root = None. A naive implementation might attempt recursion or dereference attributes without checking for null references.

The implementation handles this safely because the recursive helper immediately returns when encountering None.

Single Node Tree

A tree containing only one node has no greater values. The correct result is that the node remains unchanged.

The algorithm handles this naturally because the running sum starts at zero, and the node simply becomes:

0 + original_value

which equals its original value.

Completely Skewed Tree

A BST may be entirely left-skewed or right-skewed, effectively behaving like a linked list.

These cases are important because:

• recursion depth becomes O(n)
• traversal order becomes strictly linear

The implementation still works correctly because reverse inorder traversal preserves descending order even in skewed structures.

Trees with Negative Values

Since node values may be negative, implementations that incorrectly assume positive sums can fail.

For example:

    0
   / \
 -1   2

The node -1 should become:

-1 + 0 + 2 = 1

The algorithm handles this correctly because it relies only on BST ordering, not on positivity assumptions.