538. Convert BST to Greater Tree

01/**
02Given 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 sum of all keys greater than the original key in BST.
03
04Example:
05
06Input: The root of a Binary Search Tree like this:
07              5
08            /   \
09           2     13
10
11Output: The root of a Greater Tree like this:
12             18
13            /   \
14          20     13
15**/
16
17//Runtime: 52 ms, faster than 43.25% of C++ online submissions for Convert BST to Greater Tree.
18//Memory Usage: 23.6 MB, less than 100.00% of C++ online submissions for Convert BST to Greater Tree.
19/**
20 * Definition for a binary tree node.
21 * struct TreeNode {
22 *     int val;
23 *     TreeNode *left;
24 *     TreeNode *right;
25 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
26 * };
27 */
28class Solution {
29public:
30    int sum = 0;
31    
32    void inOrder(TreeNode* root){
33        //reversed inorder traversal
34        if(!root) return;
35        if(root->right) inOrder(root->right);
36        int temp = root->val;
37        root->val += sum;
38        sum += temp;
39        if(root->left) inOrder(root->left);
40    }
41    
42    TreeNode* convertBST(TreeNode* root) {
43        inOrder(root);
44        
45        return root;
46    }
47};
48
49/**
50Approach #1 Recursion [Accepted]
51Intuition
52
53One way to perform a reverse in-order traversal is via recursion. By using the call stack to return to previous nodes, we can easily visit the nodes in reverse order.
54
55Algorithm
56
57For the recursive approach, we maintain some minor "global" state so each recursive call can access and modify the current total sum. Essentially, we ensure that the current node exists, recurse on the right subtree, visit the current node by updating its value and the total sum, and finally recurse on the left subtree. If we know that recursing on root.right properly updates the right subtree and that recursing on root.left properly updates the left subtree, then we are guaranteed to update all nodes with larger values before the current node and all nodes with smaller values after.
58**/
59/**
60Complexity Analysis
61
62Time complexity : O(n)O(n)
63
64A binary tree has no cycles by definition, so convertBST gets called on each node no more than once. Other than the recursive calls, convertBST does a constant amount of work, so a linear number of calls to convertBST will run in linear time.
65
66Space complexity : O(n)O(n)
67
68Using the prior assertion that convertBST is called a linear number of times, we can also show that the entire algorithm has linear space complexity. Consider the worst case, a tree with only right (or only left) subtrees. The call stack will grow until the end of the longest path is reached, which in this case includes all nn nodes.
69**/
70/**
71class Solution {
72public:
73    int sum = 0;
74    
75    TreeNode* convertBST(TreeNode* root) {
76        if(!root) return NULL;
77        if(root->right) convertBST(root->right);
78        root->val += sum;
79        sum = root->val;
80        if(root->left) convertBST(root->left);
81        return root;
82    }
83};
84**/
85
86/**
87Approach #2 Iteration with a Stack [Accepted]
88Intuition
89
90If we don't want to use recursion, we can also perform a reverse in-order traversal via iteration and a literal stack to emulate the call stack.
91
92Algorithm
93
94One way to describe the iterative stack method is in terms of the intuitive recursive solution. First, we initialize an empty stack and set the current node to the root. Then, so long as there are unvisited nodes in the stack or node does not point to null, we push all of the nodes along the path to the rightmost leaf onto the stack. This is equivalent to always processing the right subtree first in the recursive solution, and is crucial for the guarantee of visiting nodes in order of decreasing value. Next, we visit the node on the top of our stack, and consider its left subtree. This is just like visiting the current node before recursing on the left subtree in the recursive solution. Eventually, our stack is empty and node points to the left null child of the tree's minimum value node, so the loop terminates.
95**/
96
97/**
98Complexity Analysis
99
100Time complexity : O(n)O(n)
101
102The key observation is that each node is pushed onto the stack exactly once. I will take for granted the assumption that a node will always be pushed at least once, as the alternative would imply that at least one node is disconnected from the root. Notice that nodes are only pushed onto the stack when they are pointed to by node at the beginning of the outer while loop, or when there is a path to them from such a node by using only right pointers. Then notice that at the end of each iteration of the loop, node points to the left child of a node that has been pushed onto (and subsequently popped from) the stack. Therefore, because the outer while loop always begins with node pointing to None, the root (which is not pointed to by any other node), or a left child of a visited node, we cannot revisit nodes.
103
104Space complexity : O(n)O(n)
105
106If we assume that the above logic is sound, the assertion that each node is pushed onto the stack exactly once implies that the stack can contain (at most) nn nodes. All other parts of the algorithm use constant space, so there is overall a linear memory footprint.
107**/
108
109//Runtime: 40 ms, faster than 99.31% of C++ online submissions for Convert BST to Greater Tree.
110//Memory Usage: 23.4 MB, less than 100.00% of C++ online submissions for Convert BST to Greater Tree.
111/**
112class Solution {
113public:
114    int sum = 0;
115    
116    TreeNode* convertBST(TreeNode* root) {
117        int sum = 0;
118        TreeNode* node = root;
119        stack<TreeNode*> stk;
120        
121        while(!stk.empty() || node != NULL){
122            while(node != NULL){
123                stk.push(node);
124                node = node->right;
125            }
126            
127            node = stk.top();
128            stk.pop();
129            sum += node->val;
130            node->val = sum;
131            
132            node = node->left;
133        }
134        
135        return root;
136    }
137};
138**/
139
140/**
141Approach #3 Reverse Morris In-order Traversal [Accepted]
142Intuition
143
144There is a clever way to perform an in-order traversal using only linear time and constant space, first described by J. H. Morris in his 1979 paper "Traversing Binary Trees Simply and Cheaply". In general, the recursive and iterative stack methods sacrifice linear space for the ability to return to a node after visiting its left subtree. The Morris traversal instead exploits the unused null pointer(s) of the tree's leaves to create a temporary link out of the left subtree, allowing the traversal to be performed using only constant additional memory. To apply it to this problem, we can simply swap all "left" and "right" references, which will reverse the traversal.
145
146Algorithm
147
148First, we initialize node, which points to the root. Then, until node points to null (specifically, the left null of the tree's minimum-value node), we repeat the following. First, consider whether the current node has a right subtree. If it does not have a right subtree, then there is no unvisited node with a greater value, so we can visit this node and move into the left subtree. If it does have a right subtree, then there is at least one unvisited node with a greater value, and thus we must visit first go to the right subtree. To do so, we obtain a reference to the in-order successor (the smallest-value node larger than the current) via our helper function getSuccessor. This successor node is the node that must be visited immediately before the current node, so it by definition has a null left pointer (otherwise it would not be the successor). Therefore, when we first find a node's successor, we temporarily link it (via its left pointer) to the node and proceed to the node's right subtree. Then, when we finish visiting the right subtree, the leftmost left pointer in it will be our temporary link that we can use to escape the subtree. After following this link, we have returned to the original node that we previously passed through, but did not visit. This time, when we find that the successor's left pointer loops back to the current node, we know that we have visited the entire right subtree, so we can now erase the temporary link and move into the left subtree.
149
150The figure above shows an example of the modified tree during a reverse Morris traversal. Left pointers are illustrated in blue and right pointers in red. Dashed edges indicate temporary links generated at some point during the algorithm (which will be erased before it terminates). Notice that blue edges can be dashed, as we always exploit the empty left pointer of successor nodes. Additionally, notice that every node with a right subtree has a link from its in-order successor.
151**/
152
153/**
154Complexity Analysis
155
156Time complexity : O(n)O(n)
157
158Although the Morris traversal does slightly more work than the other approaches, it is only by a constant factor. To be specific, if we can show that each edge in the tree is traversed no more than kk times (for some constant kk), then the algorithm is shown to have linear time complexity. First, note that getSuccessor is called at most twice per node. On the first invocation, the temporary link back to the node in question is created, and on the second invocation, the temporary link is erased. Then, the algorithm steps into the left subtree with no way to return to the node. Therefore, each edge can only be traversed 3 times: once when we move the node pointer, and once for each of the two calls to getSuccessor.
159
160Space complexity : O(1)O(1)
161
162Because we only manipulate pointers that already exist, the Morris traversal uses constant space.
163**/
164
165//Runtime: 56 ms, faster than 17.24% of C++ online submissions for Convert BST to Greater Tree.
166//Memory Usage: 23.3 MB, less than 100.00% of C++ online submissions for Convert BST to Greater Tree.
167
168/**
169class Solution {
170public:
171    TreeNode* getSuccessor(TreeNode* node){
172        TreeNode* succ = node->right;
173        while(succ->left && succ->left != node){
174            succ = succ->left;
175        }
176        return succ;
177    }
178    
179    TreeNode* convertBST(TreeNode* root) {
180        int sum = 0;
181        TreeNode* node = root;
182        
183        while(node){
184            if(node->right == NULL){
185                sum += node->val;
186                node->val = sum;
187                node = node->left;
188            }else{
189                TreeNode* succ = getSuccessor(node);
190                if(succ->left == NULL){
191                    succ->left = node;
192                    node = node->right;
193                }else{
194                    succ->left = NULL;
195                    sum += node->val;
196                    node->val = sum;
197                    node = node->left;
198                }
199            }
200        }
201        
202        return root;
203    }
204};
205**/