#1038

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Binary Search Tree to Greater Sum Tree

Convert a Binary Search Tree to a Greater Sum Tree by accumulating all larger node values using reverse in-order traversal efficiently.

tree depth first search binary search tree binary tree

Problem Statement

Given a Binary Search Tree (BST), transform it into a Greater Sum Tree where each node's new value is equal to its original value plus the sum of all values in the BST that are greater than it. The BST property ensures in-order traversal yields nodes in ascending order, which is crucial for tracking cumulative sums.

Implement an in-place transformation without changing the BST structure. For example, given root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8], the resulting Greater Sum Tree should be [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]. Constraints include 1 <= nodes <= 100, 0 <= Node.val <= 100, and all node values are unique.

Examples

Example 1

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

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

Example details omitted.

Example 2

Input: root = [0,null,1]

Output: [1,null,1]

Example details omitted.

Constraints

The number of nodes in the tree is in the range [1, 100].
0 <= Node.val <= 100
All the values in the tree are unique.

Solution Approach

Reverse In-Order Traversal with Running Sum

Traverse the BST in reverse in-order (right, root, left) to process nodes from largest to smallest. Maintain a cumulative sum variable that adds the current node's value before updating it. This approach ensures each node receives the sum of all greater values naturally during traversal.

Recursive DFS Implementation

Use a recursive helper function that updates the running sum at each node. The recursion first visits the right subtree, updates the node's value with the cumulative sum, then proceeds to the left subtree. This method leverages the call stack for traversal state without additional data structures.

Iterative DFS Using Stack

An alternative is to use an explicit stack to simulate reverse in-order traversal iteratively. Push nodes while traversing right, pop to update values and cumulative sum, then move to the left child. This avoids recursion depth issues while maintaining the same sum-tracking logic.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) since each node is visited exactly once. Space complexity is O(1) if ignoring recursion stack or O(h) with recursive DFS, where h is the tree height. The in-place update avoids extra arrays for storing node values.

What Interviewers Usually Probe

Expect a clear reverse in-order DFS approach that handles cumulative sums correctly.
Watch for correct in-place updates without changing tree structure.
Demonstrate understanding of BST properties and traversal order impact.

Common Pitfalls or Variants

Common pitfalls

Traversing in standard in-order instead of reverse, which miscalculates cumulative sums.
Resetting the running sum incorrectly between recursive calls or iterations.
Using extra space unnecessarily to store node values instead of updating in-place.

Follow-up variants

Convert a BST to a Lesser Sum Tree by accumulating all smaller node values using in-order traversal.
Handle BSTs with duplicate values where the greater-sum rule includes duplicates differently.
Implement the transformation iteratively using Morris traversal to achieve O(1) extra space.

FAQ

What traversal method should I use for Binary Search Tree to Greater Sum Tree?

Reverse in-order traversal ensures nodes are processed from largest to smallest, enabling correct accumulation of greater values.

Can I modify the BST in place for this problem?

Yes, the transformation is designed to be in-place without altering the tree's structure, just updating node values.

What if the BST has only one node?

A single node remains unchanged in value since there are no greater nodes to add.

Is recursion required to solve this problem?

Recursion is common but an iterative stack-based reverse in-order traversal works equally well.

How does GhostInterview help with this pattern?

It provides targeted guidance on reverse in-order traversal, running sum tracking, and typical pitfalls specific to the Greater Sum Tree pattern.

terminal

Solution

Solution 1: Recursion

Traverse the binary search tree in the order of "right-root-left". Accumulate all the node values encountered into $s$, and assign the accumulated value to the corresponding `node`.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

# 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
class Solution:
    def bstToGst(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(root: Optional[TreeNode]):
            if root is None:
                return
            dfs(root.right)
            nonlocal s
            s += root.val
            root.val = s
            dfs(root.left)

        s = 0
        dfs(root)
        return root

Solution 2: Morris Traversal

Morris traversal does not require a stack, with a time complexity of $O(n)$ and a space complexity of $O(1)$. The core idea is as follows:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

# 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
class Solution:
    def bstToGst(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(root: Optional[TreeNode]):
            if root is None:
                return
            dfs(root.right)
            nonlocal s
            s += root.val
            root.val = s
            dfs(root.left)

        s = 0
        dfs(root)
        return root

Continue Practicing

#938 range sum of bst #897 increasing order search tree #783 minimum distance between bst nodes