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.

Description Hints 1 Solution Video 27:38

1038. Binary Search Tree to Greater Sum Tree

Medium88.3% acceptance3 companies

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/

Asked at 3 companies

SAP Amazon

Google

Topics

Hints open one at a time

Hint 1

What traversal method organizes all nodes in sorted order?

27:38

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def bstToGst(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

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

Input

[0,null,1]

Your code is saved on this device.Solution