Showing posts with label Minimum Height in binary tree. Show all posts
Showing posts with label Minimum Height in binary tree. Show all posts

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

Contributors

Translate