Data Structures- Program in C++ to find height,mirror image,leaf nodes of binary search tree

Description:
A binary search tree has following properties :

1. The left subtree of a node contains only nodes with keys less than the node’s key.
2. The right subtree of a node contains only nodes with keys greater than the node’s key.
3. Both the left and right subtrees must also be binary search trees.
4. There must be no duplicate nodes.

Code :

#include<iostream.h>
#include<conio.h>
#include<alloc.h>
#include<stdio.h>
typedef struct node
{
int data;
struct node *left;
struct node *right;
}node;

class bst
{
public:
node *root;
void create();
void insert(node *root,node *New);
void bfs(node *root);
void inorder(node *root);
int count(node *root);
node* mirror(node *temp);
int height(node *temp);
int max(int v1,int v2);
};
void bst::create()
{
int count,i;
node *New;
root=NULL;
cout<<”\n\nEnter the number of nodes: “;
cin>>count;
for(i=0;i<count;i++)
{
New=(node*)malloc(sizeof(node));
New->left=NULL;
New->right=NULL;
cout<<”\nEnter the data: “;
cin>>New->data;
if(root==NULL)
root=New;
else
insert(root,New);
}
}
void bst::insert(node *root,node *New)
{
if(New->data < root->data)
if(root->left==NULL)
root->left=New;
else
insert(root->left,New);
if(New->data > root->data)
if(root->right==NULL)
root->right=New;
else
insert(root->right,New);
}
node* bst::mirror(node *temp)
{
node *temp1;
if(temp==NULL)
return NULL;
else
{
temp1=temp->left;
temp->left=mirror(temp->right);
temp->right=mirror(temp1);
return temp;
}
}
void bst::inorder(node *root)
{
node *temp;
temp=root;
if(temp!=NULL)
{
inorder(temp->left);
cout<<” “<<temp->data;
inorder(temp->right);
}
}
class q
{
node *data[30];
int r,f;
public:
q()
{
r=f=-1;
}
int empty()
{
if(r==-1)
return 1;
return 0;
}
void insert(node *p)
{
if(empty())
r=f=0;
else
r=r+1;
data[r]=p;
}
node *del()
{
node *p=data[f];
if(r==f)
r=f=-1;
else
f=f+1;
return p;
}
};
void bst::bfs(node *root)
{
q q1;
node *temp3;
if(root==NULL)
{
cout<<”\n\nTree is empty.”;
return ;
}
q1.insert(root);
while(!q1.empty())
{
temp3=q1.del();
if(temp3)
{
cout<<” “<<temp3->data;
if(temp3->left)
q1.insert(temp3->left);
if(temp3->right)
q1.insert(temp3->right);
}
else
break;
}
}
int bst::height(node *temp)
{
if(temp==NULL)
return 0;
if(temp->left==NULL && temp->right==NULL)
return 0;
return(max(height(temp->left),height(temp->right))+1);
}
int bst::max(int v1,int v2)
{
if(v1 > v2)
return v1;
else
return v2;
}
int bst::count(node *root)
{
int cnt;
node *temp2;
temp2=root;
if(temp2==NULL)
return 0;
if(temp2->left==NULL && temp2->right==NULL)
return 1;
cnt=count(temp2->left) + count(temp2->right);
return cnt;
}
void main()
{
int ch,cnt,ht;
char ans;
bst a;
clrscr();
cout<<”\n\n\t\t\t\t\t\t\t\t\t\t……OPERATIONS ON BINARY SEARCH TREE……”;
do
{
cout<<”\n\nMENU: “;
cout<<”\n\n1.Create BST\n\n2.Display\n\n3.Counting leaf nodes\n\n4.BFS\n\n5.Mirror\n\n6.Height”;
cout<<”\n\nEnter your choice: “;
cin>>ch;
switch(ch)
{
case 1:
a.create();
break;
case 2:
cout<<”\n\nInorder: “;
a.inorder(a.root);
break;
case 3:
cnt=a.count(a.root);
cout<<”\n\nNumber of leaf nodes: “<< cnt;
break;
case 4:
cout<<”\n\nBFS: “;
a.bfs(a.root);
break;
case 5:
cout<<”\n\nMirror Image: “;
a.mirror(a.root);
a.inorder(a.root);
break;
case 6:
ht=a.height(a.root);
cout<<”\n\nHeight of the tree: “<< ht;
break;
}
cout<<”\n\nDo you want to continue?(y/n): “;
fflush(stdin);
cin>>ans;
}while(ans==’y’ || ans==’Y');
getch(); }