Sunday, October 11, 2015

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

No comments:

Post a Comment

Contributors

Translate