Convert BST to Greater Tree

Problem

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

Reversed Inorder Traversal solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if (root == null) return root;
        convertBST(root.right);
        root.val += sum;
        sum = root.val;
        convertBST(root.left);
        return root;
    }
}

Tail Recursive solution with not instant vars

public class Solution {
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        helper(root);
        return root;
    }

    private void helper(TreeNode node) {
        if (node == null) return;
        helper(node.right);
        node.val += sum;
        sum = node.val;
        helper(node.left);
    }
}

Analysis

We use reversed inorder traversal in these solutions
Since this is an BST, we know the right is always greater than left and its top
Therefore, we first get to the rightest node in the BST
Then we update the node.val with += sum, and set the sum to node.val
Then we go the left and recursively update the node.val
Notice that, even in the tail-recursive solution, we need to put var sum as global
Otherwise the sum is different in each recursive calls and will get wrong result at the end