Convert BST to Greater Tree

LeetCode Q 538 - Convert BST to Greater Tree

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: [5, 2, 13] ; Output: [18, 20, 13]

Solution:

Code:

int sum = 0;
public TreeNode convertBST(TreeNode root) {
  if (root == null) return root;
  dfs(root);
  return root;
}

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