Thursday, July 23, 2015

Find sum of nodes vertically for a given binary tree

for example we are given a binary  tree like this

                                                                        7
                                                                 /              \
                                                             3                    5
                                                           /     \                /
                                                         1         2          4

 sum for 1st band is 1.
sum for 2nd band is 3
sum for 3rd band is (7+2+4)=13.
sum for 4th band is 5
.
here is the trick -

1.if we go left of any node we decrement band by 1 of current node.
2. if we to right child increment band by 1 of current node.


#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
struct node{
int data;
node *left,*right;
};
std::vector<std::vector<int> > v;
struct que{
node *arr[100];
int top;
int rear;
int capacity;
int size;
};


void hashing(int a,int ver)
{
int index=ver%100;
v[index].push_back(a);
}
void printvert(node *temp,int ver)
{

hashing (temp->data,ver);
if(temp->left!=NULL)
printvert(temp->left,ver-1);
if(temp->right!=NULL)
printvert(temp->right,ver+1);


}

void create(node *&t,int a)
{

if(t==NULL)
{
t=new node;
t->data=a;
t->left=NULL;
t->right=NULL;
}
else if(a>t->data)
{
create(t->right,a);
}
else
{
create(t->left,a);
}
}
int main()
{
ifstream fin;
int k;
v.resize(100);
fin.open("/home/pawan/Desktop/ds/input.txt");
if(!fin.is_open())

cout<<"file not opened\n";
node *t;
t=NULL;
int a,a1;
fin>>a;
a1=a;
int i=0;
while(a1!=-1)
{
create(t,a1);
fin>>a;
a1=a;
i++;

}
int m=i;
fin.close();
printvert(t,i/2);

cout<<"yaha tak";
for (i = 0; i < m; i++)
{
for(int j=0;j<v[i].size();j++)
{
// if(v[i][j]>0)
cout<<v[i][j]<<" ";
}
cout<<endl;
}
}

No comments:

Post a Comment

Contributors

Translate