#include<stdio.h>
#include<stdlib.h>
#define size 30
typedef struct tree
{
int info;
struct tree* left;
struct tree* right;
}node;
node* create (node*);
void insert (node*, node*);
node* search (node*, int);
node* del (node*, int);
node* display(node*);
int height (node*);
int diffheights ();
node* create (node* root)
{
int no,ele,i=0;
node* n=NULL;
node *key;
printf("\nNumber of entries:\t");
scanf("%d", &no);
while (i<no)
{
printf("\n----------------------------------INSERT------------------------------------");
printf("\nEnter data:\t");
scanf("%d", &ele);
if (ele> 0)
{
key= search(root, ele);
if (key==NULL)
{
n=(node*)malloc(sizeof(node));
n->info = ele;
n->left=NULL;
n->right=NULL;
if(root==NULL)
{
printf("\nIt's the first element of the tree.");
root=n;
}
else
{
insert(n, root);
}
i++;
}
else
printf("The node data: %d already exists in the tree.",ele);
}
else printf("\nOnly Positive integers are allowed");
}
return root;
}
void insert (node* nw, node* root)
{
node *p;
node *q;
p=root; q=root;
while(q!=NULL)
{
p=q;
if(nw->info>q->info)
q=q->right;
else
q=q->left;
}
if (p->info > nw->info)
{
p->left = nw;
}
else
{
p->right = nw;
}
}
node* search(node* root, int ele)
{
node *q;
q=root;
while((q!=NULL)&&(q->info!=ele))
{
if(q->info>ele)
q=q->left;
else
q=q->right;
}
return q;
}
node* del(node* root, int ele)
{
node* p , *q;
p=root;
while((p!=NULL)&&(p->info!=ele))
{
q=p;
if(p->info > ele)
p = p->left;
else
p=p->right;
}
if((p->right==NULL)&&(p->left==NULL))
{
if (q->info>ele)
q->left=NULL;
else
q->right=NULL;
}
if((p->left==NULL)&&(p->right!=NULL))
{
if (q->info>ele)
q->left=p->right;
else
q->right=p->right;
}
if((p->right==NULL)&&(p->left!=NULL))
{
if (q->info>ele)
q->left=p->left;
else
q->right=p->left;
}
if((p->left!=NULL)&&(p->right!=NULL))
{
node *s, *r = p->left;
while(r->right!=NULL)
{
s=r;
r=r->right;
}
p->info = r->info;
s->right = r-> left;
}
return root;
}
node* display (node* q)
{
if(q!=NULL)
{
q->left=display(q->left);
printf(" | %d | ", q->info);
q->right=display(q->right);
}
return q;
}
int height (node* p)
{
if(p==NULL)
return 0;
else
{
int leftheight = height(p->left);
int rightheight = height(p->right);
if(leftheight>rightheight)
{
return leftheight+1;
}
else
{
return rightheight+1;
}
}
}
int diffheights (node* p)
{
int diff;
int leftheight = height(p->left);
int rightheight = height(p->right);
if(leftheight>rightheight)
{
diff = (-1)*(leftheight-rightheight);
}
else
{
diff = (rightheight-leftheight);
}
return diff;
}
void main()
{
node *root=NULL, *q;
int choice, ele, h, dif;
while(1)
{
printf("\n\n\n1. Create\n2. Search\n3. Delete a node.\n4. Display (Inorder)\n5. Is it a Complete Binary Tree?\n6. Height\n7. Difference b/w left and right heights.\n8. Exit program.\n\nEnter your choice:\t");
scanf("%d", &choice);
switch(choice)
{
case 1: root=create(root); printf("\n\nCREATED"); break;
case 2: printf("Enter value to be searched:\t"); scanf("%d", &ele); q= search(root, ele);
if(q==NULL)
{
printf("\n%d doesn't exist in the tree.", ele);
}
else
{
printf("\n%d found",q->info);
} break;
case 3: printf("Enter value to be deleted:\t");
scanf("%d", &ele);
if(search(root, ele)==NULL)
printf("\nERROR: The value doesnot exist");
else
root = del(root, ele); printf("\nDeleted !"); break;
case 4: display (root); break;
case 5: if(root==NULL)
printf ("\nThe tree is Empty");
else
{
if(diffheights(root))
printf("\n Nope !");
else printf("\n Yes, it is.");
}
break;
case 6: h = height(root); printf("\nHeight = %d\n", h); break;
case 7: dif = diffheights(root);
if(dif==0)
printf("\nIt's a complete binary tree, difference is zero!");
if (dif<0)
printf("Height of Left subtree is greater than Right subtree by %d", (-1)*(dif));
if(dif>0)
printf("Height of Right subtree is greater than Left subtree by %d", dif);
break;
case 8: if(root==NULL)
printf("\nExiting with empty tree\n\n");
else
{
root->right=NULL; root->left=NULL;
free(root);
printf("\nTree Cleared !\n\n");
} exit(0);
default: printf("\n\nHey!! Choose an option from the choices mentioned!!\n And stop testing my program!!");
}
}
}