Problem

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.

Examples

Example 1:

1
2
3
4

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:

1
2
3
4

Input:
root = [0,null,1]
Output:
 [1,null,1]

Solution

Method 1 - Brute Force

Naive approach will be for every node, traverse the tree and find out all the nodes which are greater and update the node. But the time complexity of this approach will be O(n^2).

Method 2 - Recursive Reverse Inorder Traversal

Since this is a BST, the right most node in the BST is the biggest node among all the nodes. So, we can start from right, i.e. we do a reverse inorder traversal to traverse the nodes of the tree in descending order. Since we are visiting the nodes in the decreasing order, all we care about is maintaining the running sum of the nodes visited thus far.

In the process, we keep track of the running sum of all nodes which we have traversed thus far.

Video Explanation

Here is the video explanation:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public class Solution {
	private int sum = 0;
	public TreeNode bstToGst(TreeNode root) {
		if (root == null) {
			return null;
		}
		
		bstToGst(root.right); //visit the right node first

		sum += root.val; //update the sum for the next node
		root.val = sum;
		
		bstToGst(root.left);	
		return root;	
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {

	public TreeNode bstToGst(TreeNode root) {
		reverseInorder(root, new TreeNode(0));
		return root;
	}

	private void reverseInorder(TreeNode root, TreeNode sum) {
		if (root == null) {
			return;
		}

		int right = reverseInorder(root.right, sum);
		sum.val += root.val;
		root.val = sum.val;
		return reverseInorder(root.left, sum);
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {

	public TreeNode bstToGst(TreeNode root) {
		reverseInorder(root, 0);
		return root;
	}

	private int reverseInorder(TreeNode root, int sum) {
		if (root == null) {
			return sum;
		}

		int right = reverseInorder(root.right, sum); // pass in provided sum for accumulation
		root.val = root.val + right;
		return reverseInorder(root.left, root.val); // pass in updated sum
	}
}

Complexity

  • ⏰ Time complexity: O(n), where n is number of nodes in tree.
  • 🧺 Space complexity: O(n) for using recursive stack

Method 4 - Iterative Reverse Inorder Traversal

Initially, use curr to point to the root,

  1. push into Stack the right-most path of current subtree;
  2. pop out a node, update sum and the node value;
  3. point curr to the node’s left child, if any; Repeat the above till the stack is empty and curr has no left child.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public TreeNode bstToGst(TreeNode root) {
        Deque<TreeNode> stk = new ArrayDeque<>();
        TreeNode curr = root;
        int sum = 0;
        while (curr != null || !stk.isEmpty()) {
            while (curr != null) { // save right-most path of the current subtree
                stk.push(curr);
                curr = curr.right;
            }
            curr = stk.pop(); // pop out by reversed in-order.
            sum += curr.val; // update sum.
            curr.val = sum; // update node value.
            curr = curr.left; // move to left branch.
        }    
        return root;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is number of nodes in tree.
  • 🧺 Space complexity: O(n) for using stack