Greater Tree

Greater Tree

  September 01, 2018    

---

Problem:

every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Idea is to traverse in Inorder (Right,Root,Left)
Maintain sum of larger number.
Here all the right node will have more value than left and root so add larger sum into left that's why we are going towards rigth first.

int sum=0;
    public TreeNode convertBST(TreeNode root) {
        if(root==null)
            return null;
        root.right=convertBST(root.right);
        sum+=root.val;
        root.val+=sum-root.val;
        root.left=convertBST(root.left);
        return root;
    }