Convert Bst To Greater Tree - Leetcode Solution

Problem Statement: Given the root of 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 the sum of all keys greater than the original key in BST.

Example 1: Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

Example 2: Input: root = [0,null,1] Output: [1,null,1]

Example 3: Input: root = [1,0,2] Output: [3,3,2]

Approach: In a BST, the larger elements are always present in the right subtree of a node and smaller elements are present in the left subtree of a node. We can do an inorder traversal of an BST to get the nodes in an ascending order. We can modify the inorder traversal to traverse the nodes in descending order and keep a track of the sum of nodes visited till now.

We can start by traversing the right subtree first, which will give us the nodes in descending order. We can then update the node value with the sum of all the visited nodes and keep a track of the sum. After traversing the right subtree, we can traverse the left subtree and follow the same approach.

Algorithm:

1. Create a function greaterSumTree(node, sum) which will take a node and a sum as input and returns the sum after updating the node's value.
2. If the node is null, return the sum.
3. Traverse the right subtree recursively by calling greaterSumTree(node.right, sum).
4. Update the node's value by adding the sum to the node's value and update the sum with the new value.
5. Traverse the left subtree recursively by calling greaterSumTree(node.left, sum).
6. Return the updated sum.

Code:

class Solution { public: TreeNode* convertBST(TreeNode* root) { greaterSumTree(root, 0); return root; }

int greaterSumTree(TreeNode* node, int sum) {
    if(!node)
        return sum;
    
    sum = greaterSumTree(node->right, sum);
    
    node->val += sum;
    sum = node->val;
    
    sum = greaterSumTree(node->left, sum);
    
    return sum;
}

};

Complexity Analysis: Time Complexity: O(n), We are traversing all the nodes of BST in the worst case. Space Complexity: O(h), We are using an implicit stack for recursion where h is the height of the BST. The worst case space complexity will be O(n) for a skewed tree.

1