Skip to main content
Talentd

Binary Search Tree to Greater Sum Tree - Solution & Explanation

MediumTreeDepth-First SearchBinary Search TreeBinary Tree28 min readAsked at: Amazon, SAP, Google
Practice this problem

Problem Statement

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

As a reminder, a binary search tree is a tree that satisfies these constraints:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.

 

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 2:

Input: root = [0,null,1]
Output: [1,null,1]

 

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.

 

Note: This question is the same as 538: https://leetcode.com/problems/convert-bst-to-greater-tree/

Approach Overview

Problem Overview: You are given a binary search tree where each node must be updated so its new value equals the original value plus the sum of all keys greater than it. The structure of the tree stays the same; only node values change.

Approach 1: Reverse In-Order Traversal (DFS) (Time: O(n), Space: O(h))

A BST visited in reverse in-order order (right → node → left) processes nodes from largest to smallest. Maintain a running variable sum that stores the cumulative total of nodes already visited. When you reach a node, add its value to sum and update the node with this new total. Because nodes are visited in descending order, sum always represents the sum of all greater values. This approach relies on depth-first search and the ordering property of a BST. The recursion depth equals the tree height h, giving O(h) auxiliary space. For balanced trees this is O(log n), while a skewed tree degrades to O(n).

The key insight is exploiting the BST ordering. Instead of computing greater sums by scanning other nodes, you accumulate them naturally while traversing from the largest value downward. This produces an optimal linear-time solution and minimal extra state.

Approach 2: Iterative Traversal Using a Stack (Time: O(n), Space: O(h))

The same reverse in-order logic can be implemented iteratively with an explicit stack. Start from the root and push nodes while moving right to reach the maximum element. Pop a node, update the running sum, modify the node value, then move to its left subtree. Repeat the process until the stack becomes empty. Each node is pushed and popped once, keeping the time complexity O(n).

This approach avoids recursion and is useful in environments where stack depth is a concern. The stack stores at most the height of the tree, so space complexity remains O(h). The algorithm still leverages the sorted property of a binary tree structured as a BST, ensuring nodes are processed in descending order.

Recommended for interviews: Reverse in-order traversal is the expected solution. It demonstrates understanding of BST ordering and how DFS traversal patterns can transform data efficiently. Mentioning the iterative stack variant shows awareness of recursion limits and gives a practical alternative while keeping the same O(n) performance.

Approach 1: Reverse In-Order Traversal

A reverse in-order traversal (right-root-left) allows us to visit nodes in decreasing order of their values in a BST. By maintaining a cumulative sum during this traversal, we can update each node with the sum of all nodes that have been visited so far, effectively converting it into a Greater Sum Tree.

This C solution uses a helper function to perform reverse in-order traversal on the BST. As it visits each node, it maintains a cumulative sum of values, updating each node with this cumulative sum. This effectively transforms the BST into a Greater Sum Tree.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is O(n) where n is the number of nodes, as each node is visited once. The space complexity is O(h), where h is the height of the tree, representing the stack space used by the recursion.

Try this approach in the editor →

Approach 2: Iterable Approach Using a Stack

We can emulate the recursive reverse in-order traversal with an iterative approach using a stack. By processing the nodes in decreasing order of their values, we maintain a sum of all visited nodes and update each node accordingly.

This C solution uses an explicit stack data structure to simulate the recursive reverse in-order traversal process. The sum is accumulated for nodes observed, and their values are updated iteratively.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is O(n) because each node is visited once in the traversal loop. Space complexity is O(h) for stack use in the case where the tree's height is h.

Try this approach in the editor →

Approach 3: 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.

Time complexity is O(n), and space complexity is O(n), where n is the number of nodes in the binary search tree.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C

Try this approach in the editor →

Approach 4: 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:

Define s as the cumulative sum of the node values in the binary search tree. Traverse the binary tree nodes:

  1. If the right subtree of the current node root is null, add the current node value to s, update the current node value to s, and move the current node to root.left.
  2. If the right subtree of the current node root is not null, find the leftmost node next in the right subtree (i.e., the successor node of root in an in-order traversal):
    • If the left subtree of the successor node next is null, set the left subtree of next to point to the current node root, and move the current node to root.right.
    • If the left subtree of the successor node next is not null, add the current node value to s, update the current node value to s, then set the left subtree of next to null (i.e., remove the link between next and root), and move the current node to root.left.
  3. Repeat the above steps until the binary tree nodes are null, at which point the traversal is complete.
  4. Finally, return the root node of the binary search tree.

Morris reverse in-order traversal follows the same idea as Morris in-order traversal, except that the traversal order changes from "left-root-right" to "right-root-left".

Code

PythonJavaC++GoTypeScriptC

Python

Java

C++

Go

TypeScript

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Reverse In-Order Traversal

The time complexity is O(n) where n is the number of nodes, as each node is visited once. The space complexity is O(h), where h is the height of the tree, representing the stack space used by the recursion.

Iterable Approach Using a Stack

The time complexity is O(n) because each node is visited once in the traversal loop. Space complexity is O(h) for stack use in the case where the tree's height is h.

Recursion—
Morris Traversal—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Reverse In-Order Traversal (DFS)O(n)O(h)Preferred solution for BST problems; simple and optimal when recursion depth is manageable.
Iterative Traversal Using StackO(n)O(h)Useful when avoiding recursion or when stack overflow risk exists for deep trees.

Video Solution

Binary Search Tree to Greater Sum Tree | Brute | Better | Optimal | Leetcode 1038 | codestorywithMIK • codestorywithMIK • 9,928 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Binary Search Tree to Greater Sum Tree easy or hard?
The problem is rated Medium on LeetCode. The implementation is short, but recognizing that reverse in-order traversal processes nodes in descending order is the key insight that makes the solution straightforward.
Binary Search Tree to Greater Sum Tree Python/Java solution
In Python or Java, the typical implementation uses a recursive DFS with a global running sum variable. Traverse right, update the node with the cumulative sum, then traverse left. Both languages achieve O(n) time and O(h) space with this approach.
How to solve Binary Search Tree to Greater Sum Tree in O(n)?
Traverse the BST using reverse in-order traversal (right → node → left). Maintain a global or external variable storing the cumulative sum of previously visited nodes. Update each node by adding the running sum, then update the running sum with the node's new value. Since each node is processed once, the complexity remains O(n).
What is the best approach for Binary Search Tree to Greater Sum Tree?
Reverse in-order traversal is the best approach. Visiting nodes in the order right → node → left processes BST values from largest to smallest, allowing you to maintain a running sum of greater values. Each node is updated once, giving O(n) time and O(h) space where h is the tree height.
Is Binary Search Tree to Greater Sum Tree asked at Google/Amazon/Meta?
BST transformation and traversal problems like this appear frequently in interviews at companies such as Amazon, Google, and Meta. Interviewers often use variations that test understanding of in-order traversal, reverse traversal, and maintaining state during DFS.
What data structure is used in Binary Search Tree to Greater Sum Tree?
The main data structure is a Binary Search Tree. The algorithm also uses recursion or a stack to perform depth-first traversal while maintaining a running sum of previously processed nodes.
What is the time complexity of Binary Search Tree to Greater Sum Tree?
The optimal solution runs in O(n) time because every node in the BST is visited exactly once during traversal. The auxiliary space is O(h), where h is the height of the tree, due to recursion stack or an explicit stack in the iterative version.

Ready to solve this problem?

Practice Binary Search Tree to Greater Sum Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Unique Binary Search Trees II