# Convert BST To Greater Tree

Companies:

Given 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.

#### Example:

Input: The root of a Binary Search Tree like this:

``````          5
/   \
2     13
``````

Output: The root of a Greater Tree like this:

``````         18
/   \
20     13
``````

### Solution:

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".

### Java:

``````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;
}
}
``````

### Complexity Analysis:

• Time complexity : O(n).

• Space Complexity: O(1).

Scroll to Top

### Full Stack Integrated Bootcamp Free Trial

• Please enter a number from 7000000000 to 9999999999.