https://online.codingblocks.com/player/7408/content/7929/5372
Given a binary search tree, replace each nodes’ data with the sum of all nodes’ which are greater or equal than it. Include the current node’s data also.
i am taking the sum of all the nodes and than subtracting,it gives wrong answer(but by taking sum as 0 and adding the nodes give the right ans)??
#include
#include
using namespace std;
class node{
public:
int data;
node * left;
node * right;
node(int d){
data=d;
left=right=NULL;
}
};
node * insert(int a[],int s,int e){
if(s>e)
return NULL;
int mi=(s+e)/2;
node* root=new node(a[mi]);
root->left=insert(a,s,mi-1);
root->right=insert(a,mi+1,e);
return root;
}
void print(node *root){
if(root==NULL)
return;
cout<data<<" ";
print(root->left);
print(root->right);
}
void replacesum(node *root, int sum[1]) {
if(root == NULL)
return;
replacesum(root->left, sum);
root->data = sum[0];
sum[0]=sum[0]-root->data;
replacesum(root->right, sum);
}
int main()
{
int n;
cin>>n;
int a[n];
int k=0;
node * root=NULL;
for(int i=0;i<n;i++)
{
int z;
cin>>z;
k=k+z;
a[i]=z;
}
root=insert(a,0,n-1);
//print(root);
int sum[1];
sum[0]=k;
replacesum(root,sum);
print(root);
return 0;
}