Convert BST to Greater Tree
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.
1
2
3
4
5
6
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]
Java Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
private int sum = 0;
public TreeNode convertBST(TreeNode root) {
if (root != null) {
convertBST(root.right);
sum += root.val;
root.val = sum;
convertBST(root.left);
}
return root;
}
}
Complexity Analysis
- Time complexity : O(n)O(n)
A 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.
- Space complexity : O(n)O(n)
Using 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.
Approach #2 Iteration with a Stack [Accepted] Intuition
If 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.
Algorithm
One 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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public TreeNode convertBST(TreeNode root) {
int sum = 0;
TreeNode node = root;
Stack<TreeNode> stack = new Stack<TreeNode>();
while (!stack.isEmpty() || node != null) {
/* push all nodes up to (and including) this subtree's maximum on
* the stack. */
while (node != null) {
stack.add(node);
node = node.right;
}
node = stack.pop();
sum += node.val;
node.val = sum;
/* all nodes with values between the current and its parent lie in
* the left subtree. */
node = node.left;
}
return root;
}
}
Approach #3 Reverse Morris In-order Traversal [Accepted] Intuition
There 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.
Algorithm
First, 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.
The 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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
/* Get the node with the smallest value greater than this one. */
private TreeNode getSuccessor(TreeNode node) {
TreeNode succ = node.right;
while (succ.left != null && succ.left != node) {
succ = succ.left;
}
return succ;
}
public TreeNode convertBST(TreeNode root) {
int sum = 0;
TreeNode node = root;
while (node != null) {
/*
* If there is no right subtree, then we can visit this node and
* continue traversing left.
*/
if (node.right == null) {
sum += node.val;
node.val = sum;
node = node.left;
}
/*
* If there is a right subtree, then there is at least one node that
* has a greater value than the current one. therefore, we must
* traverse that subtree first.
*/
else {
TreeNode succ = getSuccessor(node);
/*
* If the left subtree is null, then we have never been here before.
*/
if (succ.left == null) {
succ.left = node;
node = node.right;
}
/*
* If there is a left subtree, it is a link that we created on a
* previous pass, so we should unlink it and visit this node.
*/
else {
succ.left = null;
sum += node.val;
node.val = sum;
node = node.left;
}
}
}
return root;
}
}
