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:
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:
[1, 100].0 <= Node.val <= 100
Note: This question is the same as 538: https://leetcode.com/problems/convert-bst-to-greater-tree/
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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Reverse In-Order Traversal | The time complexity is |
| Iterable Approach Using a Stack | The time complexity is |
Convert BST to Greater Tree - Leetcode 538 - Python • NeetCode • 25,414 views views
Watch 9 more video solutions →Practice Binary Search Tree to Greater Sum Tree with our built-in code editor and test cases.
Practice on FleetCode