Question

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.

Difficulty:Easy

Category:Tree

Analyze

Solution

// Runtime: 32ms
class Solution {
 public:
  TreeNode* convertBST(TreeNode* root) {
    int sum = 0;
    dfs(root, sum);
    return root;
  }

 private:
  void dfs(TreeNode* root, int& sum) {
    if (!root) return;
    dfs(root->right, sum);
    sum += root->val;
    root->val = sum;
    dfs(root->left, sum);
  }
};