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.
1#include<iostream>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode* left;
7 TreeNode* right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11class Solution {
12public:
13 void transform(TreeNode* node, int& sum) {
14 if (!node) return;
15 transform(node->right, sum);
16 sum += node->val;
17 node->val = sum;
18 transform(node->left, sum);
19 }
20
21 TreeNode* bstToGst(TreeNode* root) {
22 int sum = 0;
23 transform(root, sum);
24 return root;
25 }
26};This C++ solution implements the same approach of reverse in-order traversal using a member function in a class. The cumulative sum is maintained by reference, updating each node as the traversal progresses.
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.
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public TreeNode BstToGst(TreeNode root) {
var stack = new Stack<TreeNode>();
var node = root;
int sum = 0;
while (stack.Count > 0 || node != null) {
while (node != null) {
stack.Push(node);
node = node.right;
}
node = stack.Pop();
sum += node.val;
node.val = sum;
node = node.left;
}
return root;
}
}This C# iterative solution enables visiting nodes with a Stack, supporting computation of sums and updating values with less reliance on recursive depth of function.