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

Analysis:
Reverse traversal from right to root to left.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12

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