Width of Binary Tree

#include <iostream>
#include <fstream>
using namespace std;
int sum[100];
struct node
{
int data;
node *left,*right;
};

void print(node *t)
{

if(t!=NULL)
{
print(t->left);
print(t->right);
cout<<t->data<<" ";
}

}

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;
}
int height(node *t)
{
if(t==NULL)return 0;
else
return 1+max(height(t->left),height(t->right));
}
int width(node *t,int l)
{
if(t==NULL)
return 0;
if(l==1)return 1;
if(l>1)
{
return width(t->left,l-1)+width(t->right,l-1);
}
return 0;
}
int treewidth(node *t)
{
int h=height(t);
int maxwidth=0;
for(int i=1;i<=h;i++)
{
int w=width(t,i);
if(w>maxwidth)
maxwidth=w;
}
return maxwidth;
}
int main()
{

int k=0;
node *t;
t=NULL;
int a[]={10,6,4,7,14,12,16,-1};
int i=0;
while(a[i]!=-1)
{
create(t,a[i]);
i++;
}
print(t);
cout<<endl;
cout<<treewidth(t);
return 0;
}

Diameter of a Binary tree

#include <iostream>
using namespace std;
struct node
{
int data;
node * left;
node *right;
};
int height(node *t);
int max(int a ,int b)
{
if(a>b)
return a;
else return b;
}
int diameter(node *t)
{
if(t==NULL)return 0;
int ld=diameter(t->left);
int rd=diameter(t->right);
int lh=height(t->left);
int rh=height(t->right);
return max((lh+rh+1),max(lh,rh));
}
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->left,a);
}
else {
create(t->right,a);
}


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

}

int height(node *t)
{
if(t==NULL)
return 0;
return 1+max(height(t->left),height(t->right));
}

int main()
{int k;
node *t;
t=NULL;
int a[]={10,6,4,7,14,12,16,-1};
int i=0;
while(a[i]!=-1)
{
create(t,a[i]);
i++;
}
print(t);
cout<<diameter(t);
return 0;
}

Find Kth smallest element in Binary search tree

/*
TXT file
20 8 22 4 12 10 14 -1
input.txt
*/


#include <iostream>
#include <fstream>
using namespace std;
struct node
{
int data;//,height;
node * left;
node *right;
};
void print(node *t)
{
if(t!=NULL)
{
print(t->left);
print(t->right);
cout<<t->data<<" ";
}

}

int height(node *t)
{
if(t==NULL)
return -1;
else{
if(t->left==NULL&&t->right==NULL)
return 0;
else
{
int a=height(t->left);
int b=height(t->right);
if(a>b)
return a+1;
else
return b+1;
}
}
}
int max(int a ,int b)
{
if(a>b)
return a;
else return b;
}

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->left,a);
}
else {
create(t->right,a);
}
}
void K_small(node *t,int a,int &c)
{
if(t==NULL||c>=a)
return;
K_small(t->left,a,c);
c++;
if(a==c){

cout<<t->data<<" is kth K_small element\n";
return ;
}
K_small(t->right,a,c);
}

int main()
{
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;
fin>>a;
while(a!=-1)
{
create(t,a);
fin>>a;
}

fin.close();
print(t);
cout<<endl;
int c=0;
K_small(t,3,c);
return 0;
}

Find Minimum Height in binary tree

#include <iostream>
#include <fstream>
using namespace std;
struct node
{
int data;//,height;
node * left;
node *right;
};
void print(node *t)
{
if(t!=NULL)
{
print(t->left);
print(t->right);
cout<<t->data<<" ";
}

}

int height(node *t)
{
if(t==NULL)
return -1;
else{
if(t->left==NULL&&t->right==NULL)
return 0;
else
{
int a=height(t->left);
int b=height(t->right);
if(a>b)
return a+1;
else
return b+1;
}
}
}
int max(int a ,int b)
{
if(a>b)
return a;
else return b;
}

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->left,a);
}
else {
create(t->right,a);
}
}
int min_h(node *t)
{
static int h=height(t);
if(t==NULL)
return 0;
if(t->left==NULL&&t->right==NULL)
return 0;
if(t->left==NULL)
return 1+min_h(t->right);
else if(t->right==NULL)
return 1+min_h(t->left);
int a=min_h(t->left);
int b=min_h(t->right);
if(a>b)
return b+1;
else
return a+1;

}
int main()
{
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;
fin>>a;
while(a!=-1)
{
create(t,a);
fin>>a;
}

fin.close();
print(t);
int min=min_h(t);
cout<<"minimun height :";
cout<<min;
return 0;
}