check if a binary tree is sub tree of other binary tree

#include <iostream>
#include <fstream>

using namespace std;
int sum[100];
struct node
{
int data;
node *left,*right;
};

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

if(t==NULL)
{
t=new node;
t->data=k;
t->left=NULL;
t->right=NULL;
}
cin>>k;
if(k!=-1)
create(t->right,k);
cin>>k;
if(k!=-1)
create(t->left,k);
}
int max(int a ,int b)
{
if(a>b)
return a;
return b;
}
bool identicle(node *t,node *p)
{
if(t==NULL&&p==NULL)
return true;
if(t->data==p->data&&identicle(t->left,p->left)&&identicle(t->right,p->right))
return true;
return false;
}
bool fun(node *t,node *p)
{
if(p==NULL)
return true;
if(t==NULL)
return false;
return(fun(t->left,p)||fun(t->right,p)||identicle(t,p));
return false;
}
int main()
{
int k;
node *t;
t=NULL;
int a,a1;
cin>>a;
create(t,a);
cout<<"enter for 2nd tree\n";
cin>>a;
node *p=NULL;
create(p,a);
cout<<"trees create compeleted\n";
if(fun(t,p))
cout<<"yes";
else
cout<<"no";
return 0;
}

print ancestor of a node in binary tree

#include <iostream>
#include <fstream>

using namespace std;
int sum[100];
struct node
{
int data;
node *left,*right;
};

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 max(int a ,int b)
{
if(a>b)
return a;
return b;
}
bool print(node *t,int k)
{
if(!t)
return false;
if(t->data==k)
return true;
if(print(t->left,k)||(print(t->right,k)))
{
cout<<t->data<<" ";
return true;
}
return false;

}
int main()
{
for(int i=0;i<100;i++)
{
sum[i]=0;
}
ifstream fin;
int k;
fin.open("/home/pawan/Desktop/ds/input.txt");
if(!fin.is_open())

cout<<"file not opened\n";
node *t;
t=NULL;
int a,a1;
cin>>a;

while(a!=-1)
{
create(t,a);
cin>>a;

}
fin.close();
cout<<"enter the key you want to print ancestor ";
int n;
cin>>n;
print(t,n);

return 0;
}

Foldable binary tree

Consider the below trees:
(a) and (b) can be folded.
(c) and (d) cannot be folded.

(a)
       10
     /    \
    7      15
     \    /
      9  11

(b)
        10
       /  \
      7    15
     /      \
    9       11

(c)
        10
       /  \
      7   15
     /    /
    5   11

(d)

         10
       /   \
      7     15
    /  \    /
   9   10  12

#include <iostream>
#include <fstream>

using namespace std;
int sum[100];
struct node
{
int data;
node *left,*right;
};

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);
}
}
bool foldable(node *t1,node *t2)
{
if(t1==NULL&&t2==NULL)
return true;
else if(t1&&t2){
return (foldable(t1->left,t2->right)&&foldable(t1->right,t2->left));
}
return false;
}

int main()
{
for(int i=0;i<100;i++)
{
sum[i]=0;
}
ifstream fin;
int k;
fin.open("/home/pawan/Desktop/ds/input.txt");
if(!fin.is_open())

cout<<"file not opened\n";
node *t;
t=NULL;
int a,a1;
cin>>a;

while(a!=-1)
{
create(t,a);
cin>>a;

}
fin.close();
//cout<<"OLA";
print(t);
if(foldable(t->left,t->right))
cout<<"foldable\n";
else
cout<<"NOT foldable\n";


return 0;
}

Find Itinerary from a given list of tickets

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
using namespace std;
struct hashmap
{
bool visit;
string str[2];
};
int find(hashmap h[],string s,int size)
{
for(int i=0;i<size;i++)
{
if(!(h[i].str[0].compare(s)))
return i;
}
return -1;
}
int main()
{
hashmap tofrom[20], fromto[20];
ifstream fin;
for(int i=0;i<20;i++)
{
fromto[i].visit=false;
}
fin.open("/home/pawan/Desktop/place.txt");
if(!fin.is_open())
cout<<"not opened\n";
int i=0;
while(!fin.eof())
{

string str;
fin>>str;
tofrom[i].str[1]=str;
fromto[i].str[0]=str;
fin>>str;
fromto[i].str[1]=str;
tofrom[i].str[0]=str;
i++;
}
int n=i,index;
for(i=0;i<n;i++)
{
int flag=0;
for(int j=0;j<n;j++)
{
if(!(fromto[i].str[0].compare(tofrom[j].str[0])))
flag=1;
}
if(flag==0)
{
index=i;
break;
}
}
std::vector<string> v;

v.push_back(fromto[index].str[0]);
while(!fromto[index].visit)
{

v.push_back(fromto[index].str[1]);
fromto[index].visit=true;
index=find(fromto,fromto[index].str[1],n);
//cout<<index<<" ";

}
for(i=0;i<v.size();i++)
{
cout<<v[i]<<"->";
}
return 0;
}

Repetition of an element in array within k distance

#include <fstream>
#include <iostream>
using namespace std;

int hash(int h[],int a)
{

if(h[a])
return 1;
h[a]++;
return 0;
}
int main()
{
int a[]={2,1,2,4,3,2,1};
int n=sizeof(a)/sizeof(a[0]);
cout<<" Enter the distance\n";
int m;
cin>>m;
int h[n];

for (int i = 0; i < n; i++)
h[i]=0;

for (int i = 0; i < n; i++)
{
if(i>m)
h[a[i-m-1]]=0;//delete outside k diste=ance
if(hash(h,a[i])){
cout<<a[i]<<" ";
cout<<"Duplicate\n";
return 0;
}
}
cout<<"No Duplicate";
return 0;
}

detect cycle in graph

#include <iostream>
#include <vector>
#include<fstream>
#include <list>
using namespace std;
int arrr[20],counter=0;
bool DFS(int s,vector < vector < int > > v,bool c[200],bool rec[100])
{
if(!c[s])
{
std::vector<int > ::iterator it;
rec[s]=true;
c[s]=true;
for(it=v[s].begin();it!=v[s].end();++it)
{
if(!c[*it]&&DFS(*it,v,c,rec))
return true;
else if(rec[*it])
return true;
}

}
rec[s]=false;
return false;
}
int main()
{
vector < vector <  int >  > v;
bool c[200],rec[100];
for (int i = 0; i < 200; i++)
{
c[i]=false;
rec[i]=false;
}
ifstream fin;
fin.open("/home/pawan/Desktop/input1.txt");
if(!fin.is_open())
{
cout<<" file not open";
return 0;
}

int n;
fin>>n;
v.resize(n);
int i,j,w;

while(!fin.eof())
{
fin>>i>>j>>w;
v[i].push_back(j);
}
for (i = 0; i < v.size(); i++)
{
std::vector<int >::iterator it;
cout<<i<<"-> ";
for(it=v[i].begin();it<v[i].end();it++)
cout<<*it<<" ";
cout<<endl;
}
bool result= DFS(1,v,c,rec);
if(result)
cout<<"cycle exist";
else
cout<<"cycle free";
return 0;

}

depth first search in graph

#include <iostream>
#include <vector>
#include <fstream>
#include <list>
using namespace std;
int arrr[20],counter=0;
void DFS(int s,vector < vector < int > > v,bool c[200])
{

std::vector<int > ::iterator it;
cout<<s<<"->";
c[s]=true;
for(it=v[s].begin();it!=v[s].end();++it)
{
if(!c[*it])
{
c[*it]=true;

DFS(*it,v,c);
}
}

}
int main()
{
vector < vector <  int >  > v;
bool c[200];
for (int i = 0; i < 200; i++)
{
c[i]=false;

}
ifstream fin;
fin.open("/home/pawan/Desktop/input1.txt");
if(!fin.is_open())
{
cout<<" file not open";
return 0;
}

int n;
fin>>n;
v.resize(n);
int i,j,w;

while(!fin.eof())
{
fin>>i>>j>>w;
v[i].push_back(j);
v[j].push_back(i);
n--;
}
for (i = 0; i < v.size(); i++)
{
std::vector<int >::iterator it;
cout<<i<<"-> ";
for(it=v[i].begin();it<v[i].end();it++)
cout<<*it<<" ";
cout<<endl;
}
DFS(1,v,c);

}





input1.txt

15 0 2 6 1 2 5 2 3 1 1 4 6 2 7 7 4 7 4 3 6 8 4 5 12 5 8 4 8 7 2 8 11 7 11 6 4 5 9 11 9 10 8 10 11 2

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;
}
}

BREADTH FIRST SEARCH USING adjacency LIST in GRAPH

#include <iostream>
#include <vector>
#include <fstream>
#include <list>
using namespace std;
int arrr[20],counter=0;
void BFS(int s,vector < vector < int > > v,bool c[200])
{
std::vector<int> queue;
queue.push_back(s);
list <int > queue1;
queue1.push_back(s);
c[s]=true;int i=0;

// std::vector<int > :: iterator s1;
s1=queue.begin();
int n=5;
while(!queue1.empty())
{
s=queue1.front();
queue1.pop_front();
n--;
//s=*s1;
cout<<s<<" -> ";
std::vector<int>::iterator it;
for(it=v[s].begin();it!=v[s].end();++it)
{

if(!c[*it])
{
//cout<<"'"<<*it<<"'";
//arrr[counter++]=*it;
queue1.push_back(*it);
c[*it]=true;
}

}
// cout<<"EK BAAR KHATAM"<<n;
// ++s1;
}
return;

}
int main()
{
vector < vector <  int >  > v;
bool c[200];
for (int i = 0; i < 200; i++)
{
c[i]=false;

}
ifstream fin;
fin.open("/home/pawan/Desktop/input1.txt");
if(!fin.is_open())
{
cout<<" file not open";
return 0;
}

int n;
fin>>n;
v.resize(n);
int i,j,w;

while(!fin.eof())
{
fin>>i>>j>>w;
v[i].push_back(j);
v[j].push_back(i);
n--;
}
for (i = 0; i < v.size(); i++)
{
std::vector<int >::iterator it;
cout<<i<<"-> ";
for(it=v[i].begin();it<v[i].end();it++)
cout<<*it<<" ";
cout<<endl;
}
BFS(1,v,c);
for(int i=0;i<counter;i++)
{
// cout<<arrr[i]<<" ";
}
}

input1.txt

15 0 2 6 1 2 5 2 3 1 1 4 6 2 7 7 4 7 4 3 6 8 4 5 12 5 8 4 8 7 2 8 11 7 11 6 4 5 9 11 9 10 8 10 11 2