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