Sponsored
Sponsored
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.
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.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def __init__(self):
9 self.sum = 0
10
11 def bstToGst(self, root: TreeNode) -> TreeNode:
12 if root is not None:
13 self.bstToGst(root.right)
14 self.sum += root.val
15 root.val = self.sum
16 self.bstToGst(root.left)
17 return rootThis Python solution uses a class variable to store the cumulative sum during the reverse in-order traversal. The solution reflects a direct transformation of the BST to a Greater Sum Tree.
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.
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.
This Java solution provides a non-recursive way to handle the BST using a Stack, simulating reverse in-order traversal. Each node's value is computed iteratively based on aggregate sums.