Is Convert BST to Greater Tree easy or hard?

Convert BST to Greater Tree is classified as a Medium problem. The main challenge is recognizing that reverse inorder traversal naturally processes nodes from largest to smallest, which enables maintaining a running sum efficiently.

Convert BST to Greater Tree Python/Java solution

Both Python and Java implementations typically use recursive reverse inorder traversal. A global or class-level running sum variable tracks the accumulated value, and each visited node updates its value with that sum. The algorithm runs in O(n) time and O(h) stack space.

How to solve Convert BST to Greater Tree in O(n)?

Traverse the BST in reverse inorder (right → root → left). Maintain a running variable storing the sum of all previously visited nodes. Update each node by adding this running sum, then update the sum with the node's new value. Since each node is processed once, the total runtime is O(n).

What is the best approach for Convert BST to Greater Tree?

Reverse inorder traversal is the most common solution. By visiting nodes in the order right → root → left, you process values from largest to smallest and maintain a running sum of previously visited nodes. Each node adds this sum to its value, producing the correct greater tree in O(n) time.

Is Convert BST to Greater Tree asked at Google/Amazon/Meta?

BST transformation problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variations of this problem test understanding of BST properties, depth-first traversal, and tree manipulation during recursion.

What data structure is used in Convert BST to Greater Tree?

The primary data structure is a Binary Search Tree. The algorithm relies on the BST ordering property and uses depth-first search traversal, either through recursion, an explicit stack, or Morris traversal for constant extra space.

What is the time complexity of Convert BST to Greater Tree?

The optimal time complexity is O(n) because every node in the tree must be visited exactly once. Space complexity is O(h) with recursive DFS where h is the height of the tree, or O(1) when using Morris traversal.

Description Solution Video 9:33

538. Convert BST to Greater Tree

Medium72.1% acceptance4 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 [0, 10⁴].
-10⁴ <= Node.val <= 10⁴
All the values in the tree are unique.
root is guaranteed to be a valid binary search tree.

Note: This question is the same as 1038: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

Asked at 4 companies

Amazon

Google Microsoft Meta

Topics

9:33

Still stuck?Read 3 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 convertBST(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