Tuesday, September 1, 2015

Add all greater values to every node in a given BST

              50
           /      \
         30        70
        /   \      /  \
     20    40    60   80 

The above tree should be modified to following 

              260
           /      \
         330        150
        /   \       /  \
      350   300    210   80


#include <iostream>
using namespace std;
struct node {
int data;
node *left;
node *right;
};

void addgreater(node *&t,int &sum)
{
if(t==NULL)return ;
if(t)
{
addgreater(t->right,sum);
sum=sum+t->data;
t->data=sum;
addgreater(t->left,sum);
}
}
void create(node *&t,int a)
{
if(t==NULL)
{
t=new node;
t->data=a;
t->left=t->right=NULL;

}
else if(a<t->data)
create(t->left,a);
else
create(t->right,a);

}
void print(node *t)
{
if(t)
{
cout<<t->data<<" ";
print(t->left);
print(t->right);
}
}
int main()
{
int a;
node *t=NULL;

cin>>a;
while(a!=-1){
create(t,a);
cin>>a;
}
print(t);
a=0;
addgreater(t,a);
print(t);

}

No comments:

Post a Comment

Contributors

Translate