Program to implement various operations on a Binary Search Tree

Binary Search Tree:

Program to implement various operations on Binary Search Tree:

/*Binary Search Tree*/

#include <stdio.h>
#include <alloc.h>
#include <conio.h>
#include <stdlib.h>

#define MAX 10

/* -OPERATIONS-
(i) Creation of a Binary Search Tree
(ii) Traversal
a) Preorder – Recursive/Iterative
b) Inorder – Recursive/Iterative
c) Postorder – Recursive/Iterative
d) Level by Level
(iii) Insertion
a) Recursive
b) Iterative
(iv) Deletion
a) Recursive
b) Iterative
(v) Searching
a) Recursive
b) Iterative
(vi) Finding Height
(vii) Finding number of nodes
{internal, external, total}
(viii) Finding number of leaves (external nodes)
(ix) Determining mirror image
(x) Creating clone
(xi) Sorting (Inorder traversal – Recursive)
(xii) Disposing
(xiii) Finding smallest – Recursive/Iterative
(xiv) Finding largest – Recursive/Iterative
*/

typedef struct binarysearchtree
{int info;
struct binarysearchtree *left;
struct binarysearchtree *right;
}BST;

/*Allocates the memory*/
BST *create();
/*Makes a new node*/
BST *makenode(int);
/*Inserts a new node in a BST using recursive definition*/
BST *insert(BST *,BST *);
/*Iteratively inserts a newnode in a BST*/
BST *iterativeinsert(BST *,BST *);
/*Traverses BST in preorder by recursive definition*/
void preorder(BST *);
/*Traverses BST in preorder by iterative definition*/
void iterativepreorder(BST *);
/*Traverses BST in inorder by recursive definition*/
void inorder(BST *);
/*Traverses BST in inorder using iterative definition*/
void iterativeinorder(BST *);
/*Traverses BST in postorder using recursive definition*/
void postorder(BST *);
/*Traverses BST in postorder using iterative definition*/
void iterativepostorder(BST *);
/*Searches a given element in BST recursively*/
void searchTree(BST *,int);
/*Searches a given element in BST iteratively*/
void iterativeSearchTree(BST *,int);
/*Returns largest from BST using recursive definition*/
int largest(BST *);
/*Returns largest value using iterative definition*/
int largestiterative(BST *);
/*Returns smallest value using recursive definition*/
int smallest(BST *);
/*Returns smallest value using iterative definition*/
int smallestiterative(BST *);
/*Generates mirror image of BST*/
void mirror(BST *);
/*Generates a duplicate copy of BST*/
void clone(BST *);
/*Returns total nodes of BST*/
int totalnodes(BST *);
/*Returns external nodes (leaf nodes) of BST*/
int external(BST *);
/*Returns internal nodes (interior nodes) of a BST*/
int internal(BST *);
/*Returns height of a BST*/
int heightTree(BST *);
/*Deletes a node from BST using recursive definition*/
BST *deletenode(BST *,int);
/*Deletes a node from BST using iterative definition*/
BST *deletenodeiterative(BST *,int);
/*Deletes BST completely using recursive definition*/
BST *dispose(BST *);
/*Delete BST completely using iterative definition*/
BST *iterativedispose(BST *);
/*Traverses BST level by level using recursive definition*/
void levelbyleveltraversal(BST *);
/*Traverses BST level by level using iterative definition*/
void iterativeleveltraversal(BST *);

/*Allocates the memory*/
BST *create()
{
BST *temp=(BST *) malloc(sizeof(BST));
if(temp==NULL)
{printf(“Memory Allocation Error.”);
exit(1);
}
return temp;
}

/*Makes a new node*/
BST *makenode(int x)
{BST *temp=create();
temp->info=x;
temp->left=NULL;
temp->right=NULL;
return temp;
}

/*Inserts a new node in a BST using recursive definition*/
BST *insert(BST *root,BST *num)
{if(root==NULL)
{root=num;
return root;
}
if(num->info < root->info)
root->left=insert(root->left,num);
else if(num->info > root->info)
root->right=insert(root->right,num);
else
printf(“\nDuplicate Value…!”);
return root;
}

/*Iteratively inserts a newnode in a BST*/
BST *iterativeinsert(BST *root,BST *newnode)
{BST *p=root;
if(root==NULL)
{root=newnode;
return root;
}
while(p!=NULL)
{
if(newnode->info<p->info)
{if(p->left)
p=p->left;
else
{p->left=newnode;
break;
}
}
else if(newnode->info>p->info)
{if(p->right)
p=p->right;
else
{p->right=newnode;
break;
}
}
else
{printf(“\nDuplicate key found…!”);
break;
}
}
return root;
}

/*Traverses BST in preorder by recursive definition*/
void preorder(BST *root)
{
if(root)
{printf(“%d\t”,root->info);
preorder(root->left);
preorder(root->right);
}
}

/*Creating clone of a given tree*/
BST *newroot=NULL; /*global definition of root of new tree*/
void clone(BST *root)
{
BST *temp;
if(root)
{printf(“\nMaking node %d”,root->info);
temp=makenode(root->info);
newroot=insert(newroot,temp);
clone(root->left);
clone(root->right);
}
}

/*Traverses BST in inorder by recursive definition*/
void inorder(BST *root)
{
if(root)
{inorder(root->left);
printf(“%d\t”,root->info);
inorder(root->right);
}
}

/*Traverses BST in postorder using recursive definition*/
void postorder(BST *root)
{
if(root)
{postorder(root->left);
postorder(root->right);
printf(“%d\t”,root->info);
}
}

/*Queue definition for Breadth first traversal*/

typedef struct queue
{int front,rear;
BST *arr[MAX];
}queue;

void enqueue(queue *q,BST *node)
{if(q->rear==MAX-1)
{printf(“\nQueue Overflow…!”);
return;
}
q->arr[++q->rear]=node;
}

BST *dequeue(queue *q)
{if(q->rear==-1)
{printf(“\nQueue underflow.”);
return NULL;
}
return(q->arr[q->front++]);
}

int empty(queue *q)
{return (q->front>q->rear);
}

void levelbyleveltraversal(BST *root)
{
queue q;
q.front=0;
q.rear=-1;
if(root!=NULL)
{enqueue(&q,root);
while(!empty(&q))
{
root=dequeue(&q);
printf(“%d\t”,root->info);
if(root->left!=NULL)
enqueue(&q,root->left);
if(root->right!=NULL)
enqueue(&q,root->right);
}
}
}
/*Global stack declaration used for iterative traversals*/
typedef struct stack
{int top;
BST *items[MAX];
}stk;

/*Checks whether the stack is empty or not*/
int empty(stk *s)
{return(s->top==-1);
}

/*Push a node of BST into the stack*/
void push(stk *s, BST *t)
{if(s->top==MAX-1)
{printf(“\nStack Overflow…!”);
return;
}
s->items[++(s->top)]=t;
}

/*Pops/returns a node of BST from the top of the stack*/
BST *pop(stk *s)
{if(s->top==-1)
{printf(“\nStack Underflow…!”);
return NULL;
}
return(s->items[(s->top)--]);
}

/*Iterative Preorder Traversal*/
void iterativepreorder(BST *root)
{stk s;
BST *p=root;
s.top=-1;
do
{
while(p!=NULL)
{printf(“%d\t”,p->info);
push(&s,p);
p=p->left;
}
if(!empty(&s))
{p=pop(&s);
p=p->right;
}
}while(!empty(&s) || p!=NULL);
}

/*Iterative Inorder Traversal*/
void iterativeinorder(BST *root)
{stk s;
BST *p=root;
s.top=-1;
do
{while(p!=NULL)
{push(&s,p);
p=p->left;
}
if(!empty(&s))
{p=pop(&s);
printf(“%d\t”,p->info);
p=p->right;
}
}while(!empty(&s) || p!=NULL);
}

/*Global stack declarations used for
postorder iterative traversals*/

struct pstack
{BST *tree;
int visitedleft,visitedright;
}pstk[MAX];

/*Global declaration of top*/
int top=-1;

void ppush(struct pstack pstk[],BST *t,int VL,int VR)
{if(top==MAX-1)
{printf(“\nStack Overflow…!”);
return;
}
top++;
pstk[top].tree = t;
pstk[top].visitedleft=VL;
pstk[top].visitedright=VR;
}

/*Pop the topmost element from the stack*/
struct pstack *ppop(struct pstack *pstk)
{struct pstack *temp;
if(top==-1)
{printf(“\nStack Underflow…!”);
return NULL;
}
temp=&pstk[top];
top–;
return temp;
}

/*Checks & returns the value of top*/
int pempty()
{return(top==-1);
}

/*Iterative Postorder Traversal*/
void iterativepostorder(BST *root)
{
struct pstack *temp;
BST *p=root;
while(1)
{while(p!=NULL)
{ppush(pstk,p,1,0);
p=p->left;
}
if(pempty())
return;
temp=ppop(pstk);
if(temp->visitedleft==1 && temp->visitedright==1)
printf(“%d\t”,temp->tree->info);
else
{ppush(pstk,temp->tree,temp->visitedleft,1);
p=temp->tree->right;
}
}
}

/*Searching a given node in a BST using recursive definition*/
void searchTree(BST *root,int num)
{if(root==NULL)
{printf(“Number not found…!”);
return;
}
if(num<root->info)
searchTree(root->left,num);
else if(num>root->info)
searchTree(root->right,num);
else
{printf(“\nNumber is found…!”);
return;
}
}

/*Searching a given node in a BST using Iterative definition*/
void iterativeSearchTree(BST *root,int num)
{BST *p=root;
if(root==NULL)
{printf(“\nNumber not found…!”);
return;
}
while(p!=NULL)
{if(num<root->info)
{if(root->left)
root=root->left;
else
{printf(“\nNumber not found…!”);
return;
}
}
else if(num>root->info)
{if(root->right)
root=root->right;
else
{printf(“\nNumber not found…!”);
return;
}
}
else
{printf(“\nNumber found…!”);
return;
}
}
return;
}

/*Return largest value from BST.
Iterative Definition*/
int largest(BST *root)
{BST *p=root;
if(root==NULL)
return -1;
while(p->right!=NULL)
p=p->right;
return(p->info);
}

/*Return smallest value from BST.
Iterative Definition*/
int smallest(BST *root)
{BST *p=root;
if(root==NULL)
return -1;
while(p->left!=NULL)
p=p->left;
return(p->info);
}

/*Return largest value from BST using recursive definition*/
int largestiterative(BST *root)
{if(root==NULL)
return -1;
if(root->right==NULL)
return(root->info);
else
return largestiterative(root->right);
}

/*Return smallest value from BST using recursive definition*/
int smallestiterative(BST *root)
{if(root==NULL)
return -1;
if(root->left==NULL)
return(root->info);
else
return smallestiterative(root->left);
}

/*Generating mirror image*/
void mirror(BST *root)
{BST *temp;
if(root)
{mirror(root->left);
mirror(root->right);
temp=root->left;
root->left=root->right;
root->right=temp;
}
}

/*Return total nodes of a BST*/
int totalnodes(BST *root)
{if(root==NULL)
return 0;
else
return(totalnodes(root->left)+totalnodes(root->right)+1);
}

/*Return external/leaf nodes of a BST*/
int external(BST *root)
{if(root==NULL)
return 0;
else if(root->left==NULL && root->right==NULL)
return 1;
else
return(external(root->left)+external(root->right));
}

/*Return internal/interior nodes of a BST*/
int internal(BST *root)
{if((root==NULL) || ((root->left==NULL)&&(root->right==NULL)))
return 0;
else
return(internal(root->left)+internal(root->right)+1);
}

/*Return height of a tree – recursive definition*/
void heightTree(BST *root,int *height)
{int leftsubtree,rightsubtree;
if(root==NULL)
{*height=0;
}
else
{heightTree(root->left,&leftsubtree);
heightTree(root->right,&rightsubtree);
if(leftsubtree>rightsubtree)
*height=leftsubtree + 1;
else
*height=rightsubtree + 1;
}
}

/*Returns degree of a given node*/
int degree(BST *root)
{if(root->left==NULL && root->right==NULL)
return 0;
else if(root->left!=NULL && root->right!=NULL)
return 2;
else
return 1;
}

/*Deletion of a node from BST using recursive definition*/
BST *deletenode(BST *root,int val)
{BST *temp;
if(root==NULL)
return root;
if(val<root->info)
root->left=deletenode(root->left,val);
else if(val>root->info)
root->right=deletenode(root->right,val);
else /*if only one node exists*/
{if(degree(root)==0)
{free(root);
return NULL;
}
/*if node contains one child either left or right*/
if(degree(root)==1)
{
if(root->right)
{temp=root->right;
free(root);
return temp;
}
else
{temp=root->left;
free(root);
return temp;
}
}
/*If node to be deleted contains both
left as well as right child*/
if(degree(root)==2)
{temp=root->right;
while(temp->left!=NULL)
temp=temp->left;
temp->left=root->left;
temp=root->right;
free(root);
return temp;
}
}
return root;
}

/*Deletion of a node from BST using iterative definition*/
BST *deletenodeiterative(BST *root,int val)
{
BST *cur,*prev,*temp;
if(root==NULL)
return root;
cur=root;
prev=NULL;
while(cur!=NULL && cur->info!=val)
{prev=cur;
if(val<cur->info)
cur=cur->left;
else
cur=cur->right;
}
if(cur==NULL)
return root;
if(degree(cur)==0)
{
if(prev) /*not a root node*/
{
if(prev->left==cur)
prev->left=NULL;
else
prev->right=NULL;
free(cur);
}
else
{free(cur);
return NULL;
}
}
else if(degree(cur)==1)
{if(cur->left)
{
if(prev)
{
if(prev->left==cur)
prev->left=cur->left;
else
prev->right=cur->left;
free(cur);
}
else{
prev=cur->left;
free(cur);
return(prev);
}
}
else
{
if(prev)
{
if(prev->left==cur)
prev->left=cur->right;
else
prev->right=cur->right;
free(cur);
}
else
{
prev=cur->right;
free(cur);
return (prev);
}
}
}
else if(degree(cur)==2)
{if(prev->left==cur)/*case I*/
/*then traverse left of right child*/
{temp=cur->right;
while(temp->left!=NULL)
temp=temp->left;
temp->left=cur->left;
prev->left=cur->right;
free(cur);
}
else/*case II*/
/*traverse left of right child*/
{temp=cur->right;
while(temp->left!=NULL)
temp=temp->left;
temp->left=cur->left;
if(prev!=NULL)
prev->right=cur->right;
temp=cur->right;
free(cur);
return temp;
}
}
return root;
}

/*function to dispose the BST*/
BST *dispose(BST *root)
{BST *left,*right;
if(root!=NULL)
{left=root->left;
right=root->right;
free(root);
root=dispose(left);
root=dispose(right);
}
return root;
}

void main()
{
int ch,x,flag=0;
BST *newnode,*root=NULL;
while(1)
{clrscr();flag=0;
printf(“\nMenu-Binary Search Tree Operations”);
printf(“\n\n1. Recursive”);
printf(“\n2. Non-Recursive”);
printf(“\n3. Exit”);
printf(“\n\nEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
do
{
clrscr();
printf(“\n\nRecursive Menu”);
printf(“\n\n1. Insertion”);
printf(“\n2. Inorder traversal”);
printf(“\n3. Preorder traversal”);
printf(“\n4. Postorder traversal”);
printf(“\n5. Deletion”);
printf(“\n6. Search node”);
printf(“\n7. Find height”);
printf(“\n8. Find total nodes”);
printf(“\n9. Find leaf nodes”);
printf(“\n10. Find interior nodes”);
printf(“\n11. Generate mirror image”);
printf(“\n12. Generate clone”);
printf(“\n13. Display sorted order”);
printf(“\n14. Dispose tree”);
printf(“\n15. Find largest node”);
printf(“\n16. Find smallest node”);
printf(“\n17. Return”);

printf(“\nEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1: printf(“\nEnter the number?”);
scanf(“%d”,&x);
newnode=makenode(x);
root=insert(root,newnode);
break;
case 2: inorder(root);
break;
case 3: preorder(root);
break;
case 4: postorder(root);
break;
case 5: printf(“\nEnter the node to delete?”);
scanf(“%d”,&x);
root=deletenode(root,x);
break;
case 6: printf(“\nEnter the number to search?”);
scanf(“%d”,&x);
searchTree(root,x);
break;
case 7: heightTree(root,&x);
printf(“\nHeight = %d”,x);
break;
case 8: x=totalnodes(root);
printf(“\nTotal nodes = %d”,x);
break;
case 9:x=external(root);
printf(“\nLeaf nodes = %d”,x);
break;
case 10:x=internal(root);
printf(“\nInterior Nodes = %d”,x);
break;
case 11:mirror(root);
break;
case 12:clone(root);
printf(“\nDisplaying original BST-inorder”);
inorder(root);
printf(“\nDisplaying its clone-inorder”);
inorder(newroot);
break;
case 13:printf(“\nTree elements in sorted order:”);
inorder(root);
break;
case 14:printf(“\nDisposing the tree…!”);
root=dispose(root);
break;
case 15:x=largest(root);
printf(“\nLargest value = %d”,x);
break;
case 16:x=smallest(root);
printf(“\nSmallest value = %d”,x);
break;
case 17:flag=1;break;
default:printf(“\nInvalid choice…!”);
}
getch();
}while(flag!=1);
break;
case 2:
do
{clrscr();
printf(“\n\nNon-Recursive/Iterative Menu”);
printf(“\n1. Insertion”);
printf(“\n2. Inorder traversal”);
printf(“\n3. Preorder traversal”);
printf(“\n4. Postorder traversal”);
printf(“\n5. Level by level/BFS traversal”);
printf(“\n6. Deletion”);
printf(“\n7. Search node”);
printf(“\n8. Find largest node”);
printf(“\n9. Find smallest node”);
printf(“\n10. Return”);
printf(“\nEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{case 1: printf(“\nEnter the number?”);
scanf(“%d”,&x);
newnode=makenode(x);
root=iterativeinsert(root,newnode);
break;
case 2: iterativeinorder(root);
break;
case 3: iterativepreorder(root);
break;
case 4: iterativepostorder(root);
break;
case 5: levelbyleveltraversal(root);
break;
case 6: printf(“\nEnter the node to delete?”);
scanf(“%d”,&x);
root=deletenodeiterative(root,x);
break;
case 7: printf(“\nEnter the number to search?”);
scanf(“%d”,&x);
iterativeSearchTree(root,x);
break;
case 8:x=largestiterative(root);
printf(“\nLargest value = %d”,x);
break;
case 9:x=smallestiterative(root);
printf(“\nSmallest value = %d”,x);
break;
case 10:flag=1;break;
default:printf(“\nInvalid choice…”);
}
getch();
}while(flag!=1);
break;
case 3:
exit(0);
default:
printf(“\nInvalid choice…!”);
}
}
}