LeetCode 538: Convert BST to Greater Tree Solution in Python – A Step-by-Step Guide

Imagine you’re strolling through a Binary Search Tree (BST), where numbers are neatly sorted—smaller on the left, larger on the right—and your task is to transform it so each node’s value becomes the sum of itself and all the bigger numbers in the tree, like turning [4, 1, 6, 0, 2, 5, 7, null, null, 3, null, null, 8] into a new tree with sums of greater values. That’s the captivating challenge of LeetCode 538: Convert BST to Greater Tree, a medium-level problem that’s a fantastic way to practice tree traversal in Python. We’ll explore two solutions: the Best Solution, a reverse inorder traversal with running sum that’s efficient and elegant, and an Alternative Solution, an inorder to array and reconstruct approach that’s straightforward but less space-efficient. With detailed examples, clear code, and a friendly tone—especially for the reverse inorder trick—this guide will help you transform that BST, whether you’re new to coding or leveling up. Let’s reshape that tree and start summing!

What Is LeetCode 538: Convert BST to Greater Tree?

In LeetCode 538: Convert BST to Greater Tree, you’re given the root of a Binary Search Tree (BST), and your task is to convert it into a Greater Tree where each node’s value is updated to the sum of its original value and all values greater than it in the BST. A BST ensures that for any node, all left subtree values are less than the node’s value, and all right subtree values are greater, making traversal key. For example, in a BST [4, 1, 6, 0, 2, 5, 7, null, null, 3, null, null, 8], the node with value 4 becomes 30 (sum of 4, 5, 6, 7, 8). This problem builds on LeetCode 94: Binary Tree Inorder Traversal for tree traversal techniques.

Problem Statement

Input: root (TreeNode)—root of a BST.
Output: TreeNode—root of the converted Greater Tree.
Rules: Each node’s new value = original value + sum of all greater values.

Constraints

Number of nodes: 0 to 10⁴.
Node values: -10⁴ to 10⁴.
All values are unique.

Examples

Input: root = [4,1,6,0,2,5,7,null,null,3,null,null,8]

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

Input: root = [0,null,1]

Output: [1,null,1]
0 becomes 1 (0+1), 1 stays 1 (no greater values).

Input: root = [1]

Output: [1]
Single node unchanged.

Understanding the Problem: Converting to Greater Sums

To solve LeetCode 538: Convert BST to Greater Tree in Python, we need to update each node’s value in a BST to include the sum of all greater values. Since BST inorder traversal (left, root, right) gives a sorted ascending order, reverse inorder (right, root, left) gives descending order, allowing us to accumulate sums from largest to smallest. A naive approach might collect all values and recompute sums, but with up to 10⁴ nodes, we can optimize using traversal properties. We’ll explore:

Best Solution (Reverse Inorder Traversal with Running Sum): O(n) time, O(h) space (h = height)—efficient and sleek.
Alternative Solution (Inorder to Array and Reconstruct): O(n) time, O(n) space—simple but uses extra memory.

Let’s dive into the reverse inorder solution with a friendly breakdown!

Best Solution: Reverse Inorder Traversal with Running Sum

Why Reverse Inorder Wins

The reverse inorder traversal with running sum is the best for LeetCode 538 because it processes the BST in descending order (right, root, left), updating each node’s value with a cumulative sum of all greater values in O(n) time and O(h) space (recursion stack). It’s like walking the tree backward, adding up the big numbers as you go!

How It Works

Think of this as a tree-summing hike:

Step 1: Reverse Inorder Traversal:

Visit right subtree, root, left subtree—descending order.

Step 2: Track Running Sum:

Maintain a cumulative sum (self.sum) of visited values.
Add current node’s value to sum after right subtree, then update node.

Step 3: Update Nodes In-Place:

Each node’s new value = original + sum of greater values (tracked by self.sum).

Why It Works:

Reverse inorder ensures larger values are processed first.
Running sum accumulates all greater values naturally.

It’s like a BST greater-sum transformer!

Step-by-Step Example

Example: root = [4, 1, 6, 0, 2, 5, 7, null, null, 3, null, null, 8]

Init: self.sum = 0.
Reverse Inorder:

Right to (6):

Right to (7):

Right to (8): self.sum = 0, update 8 to 8, self.sum = 8.
Visit 7: self.sum = 8, update 7 to 7+8=15, self.sum = 15.

Visit 6: self.sum = 15, update 6 to 6+15=21, self.sum = 21.

Visit 4: self.sum = 21, update 4 to 4+21=25, self.sum = 25.
Left to (1):

Right to (2):

Right to (3): self.sum = 25, update 3 to 3+25=28, self.sum = 28.
Visit 2: self.sum = 28, update 2 to 2+28=30, self.sum = 30.

Visit 1: self.sum = 30, update 1 to 1+30=31, self.sum = 31.
Left to (0): self.sum = 31, update 0 to 0+31=31, self.sum = 31.

Result: [25, 31, 21, 31, 30, null, 15, null, null, 28, null, null, 8] (adjusted example output).

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

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

class Solution:
    def __init__(self):
        # Step 1: Initialize running sum
        self.sum = 0

    def convertBST(self, root: TreeNode) -> TreeNode:
        # Step 2: Handle empty tree
        if not root:
            return None

        # Step 3: Reverse inorder traversal
        def reverse_inorder(node):
            if not node:
                return

            # Traverse right subtree
            reverse_inorder(node.right)

            # Update current node with running sum
            self.sum += node.val
            node.val = self.sum

            # Traverse left subtree
            reverse_inorder(node.left)

        reverse_inorder(root)
        return root

Line 9: Running sum as instance variable for recursion.
Lines 13-15: Return None for empty tree.
Lines 18-19: Base case for recursion.
Line 22: Recurse right (larger values first).
Lines 25-26: Add node’s value to sum, update node.
Line 29: Recurse left (smaller values).
Line 31: Start traversal.
Time Complexity: O(n)—visit each node once.
Space Complexity: O(h)—recursion stack (h ≤ n).

It’s like a BST sum converter!

Alternative Solution: Inorder to Array and Reconstruct

Why an Alternative Approach?

The inorder to array and reconstruct solution collects all BST values into a sorted array via inorder traversal, computes cumulative sums from the right, and rebuilds the tree, running in O(n) time and O(n) space. It’s straightforward but uses extra memory, making it great for array-based learners!

How It Works

Picture this as a BST array remodel:

Step 1: Inorder traversal to array (ascending order).
Step 2: Compute greater sums from right to left.
Step 3: Reconstruct tree with new values.

It’s like a BST array rebuilder!

Step-by-Step Example

Example: root = [5, 3, 8]

Step 1: Inorder: [3, 5, 8].
Step 2: Greater sums:

8: 8.
5: 5 + 8 = 13.
3: 3 + 13 = 16.
Array: [16, 13, 8].

Step 3: Reconstruct:

Root = 13, left = 16, right = 8.

Result: [13, 16, 8].

Code for Array Approach

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        # Step 1: Inorder traversal to array
        values = []
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            values.append(node.val)
            inorder(node.right)

        inorder(root)

        # Step 2: Compute greater sums
        n = len(values)
        for i in range(n-2, -1, -1):
            values[i] += values[i+1]

        # Step 3: Reconstruct tree
        def build_tree(vals, start, end):
            if start > end:
                return None
            mid = (start + end) // 2
            root = TreeNode(vals[mid])
            root.left = build_tree(vals, start, mid-1)
            root.right = build_tree(vals, mid+1, end)
            return root

        return build_tree(values, 0, n-1) if values else None

Lines 4-11: Inorder builds sorted array.
Lines 14-15: Compute cumulative sums from right.
Lines 18-25: Rebuild BST from array.
Time Complexity: O(n)—traversal and rebuild.
Space Complexity: O(n)—array storage.

It’s an array-based BST transformer!

Comparing the Two Solutions

Reverse Inorder (Best):

Pros: O(n), O(h), space-efficient.
Cons: Recursive state.

Array Reconstruct (Alternative):

Pros: O(n), O(n), clear steps.
Cons: Extra space.

Reverse inorder wins for efficiency!

Additional Examples and Edge Cases

[1]: [1].
[5, 2, 13]: [18, 20, 13].
[]: None.

Reverse inorder handles them all!

Complexity Recap

Reverse Inorder: Time O(n), Space O(h).
Array: Time O(n), Space O(n).

Reverse inorder’s the space champ!

Key Takeaways

Reverse Inorder: Sum as you go—learn at Python Basics!
Array: Clear but costly.
Trees: BSTs are fun.
Python: Recursion or arrays, your pick!

Final Thoughts: Transform That Tree!

LeetCode 538: Convert BST to Greater Tree in Python is a delightful tree challenge. Reverse inorder with running sum is your fast track, while array reconstruction offers a clear alternative. Want more? Try LeetCode 94: Inorder Traversal or LeetCode 1038: BST to Greater Sum Tree. Ready to convert? Head to Solve LeetCode 538 on LeetCode and reshape that BST today!