Replace with Sum of greater nodes

#1

brute force approach is go to every node and and find sum of all greater nodes and I want to implement this brute force approach, i don’t know how to implement
please provide code for reference

#2

You can maintain a variable called as sum, initialised to 0… and then call the function which replace the nodes as :

void modifysum(node *root,int *sum)
{
if(root==NULL)
{
return;
}
modifysum(root->right,sum);
*sum=*sum+root->data;
root->data=*sum;
modifysum(root->left,sum);
}
void BSTsum(node *root)
{
int sum=0;
modifysum(root,&sum);
}

#3

I think this approach will take O(n) time, as it is reverse inorder
I want worst approach’s code which takes O(n^2) time

#4

This is simple dfs code with a small concept of cumulative sum. Please give it a look.

vector<int>v;
    void dfs(TreeNode* root)
    {
        if(root==NULL)return ;
        v.push_back(root->val);
        dfs(root->right);
        dfs(root->left);
    }
    void dfs1(TreeNode* root,map<int,int>& mp)
    {
        if(root==NULL)return;
        root->val=mp[root->val];
        dfs1(root->right,mp);
        dfs1(root->left,mp);
    }
    TreeNode* bstToGst(TreeNode* root) {
        dfs(root);
        sort(v.begin(),v.end());
        vector<int>temp=v;
        map<int,int>mp;
        for(int i=v.size()-2;i>=0;i--)
        {
            v[i]+=v[i+1];
        }
        
        for(int i=0;i<v.size();i++)
        {
            mp[temp[i]]=v[i];
        }
        dfs1(root,mp);
        return root;
    }