C Program to Implement Binary Search Tree [BST]

This is the C Program implementation of binary search tree with
->Insertion
->Deletion
->Traversal
->Display
In computer science, a binary search tree (BST), sometimes also called an ordered or sorted binary tree, is a node-based binary tree data structure where each node has a comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node’s left sub-tree and smaller than the keys in all nodes in that node’s right sub-tree. Each node has no more than two child nodes. Each child must either be a leaf node or the root of another binary search tree. The left sub-tree contains only nodes with keys less than the parent node; the right sub-tree contains only nodes with keys greater than the parent node. BSTs are also dynamic data structures, and the size of a BST is only limited by the amount of free memory in the operating system. The main advantage of binary search trees is that it remains ordered, which provides quicker search times than many other data structures. The common properties of binary search trees are as follows:[1]

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree.
Each node can have up to two successor nodes.
There must be no duplicate nodes.
A unique path exists from the root to every other node.
The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient. The other advantages are:

Binary Search Tree is fast in insertion and deletion etc. when balanced.
Very efficient and its code is easier than other data structures.
Stores keys in the nodes in a way that searching, insertion and deletion can be done efficiently.
Implementation is very simple in Binary Search Trees.
Nodes in tree are dynamic in nature.

Binary search trees are a fundamental data structure used to construct more abstract data structures such as sets, multisets, and associative arrays. Some of their disadvantages are as follows:

The shape of the binary search tree totally depends on the order of insertions, and it can be degenerated.
When inserting or searching for an element in binary search tree, the key of each visited node has to be compared with the key of the element to be inserted or found, i.e., it takes a long time to search an element in a binary search tree.
The keys in the binary search tree may be long and the run time may increase.
After a long intermixed sequence of random insertion and deletion, the expected height of the tree approaches square root of the number of keys which grows much faster than log n.

A binary search tree of size 9 and depth 3, with root 8 and leaves 1, 4, 7 and 13

Program:

#include<stdio.h>

typedef struct T
{
int data;
struct t *lchild,*rchild;
}NODE;


NODE *root=NULL,*prev,*temp,*newnode;

int dec,flag=0,depth=0,ai=0,arr[50],que[500],front=-1,rear=-1,jpr=-1;
main()
{
int ch,ele;
printf("Enter the Choicen 1.INSERT n 2.INORDER n 3.PREORDER n 4.POSTORDER n 5.DISPLAY n 6.EXIT n");
scanf("%d",&ch);
while(ch<6)
{
switch(ch)
{
case 1: printf("Enter the Element to be Insertedn"); scanf("%d",&ele); insert(ele); break;
case 2: inorder(root); break;
case 3: preorder(root); break;
case 4: postorder(root); break;
case 5: jp1016(); break;
case 6: break;
}
scanf("%d",&ch);
}
}

insert(int num)
{
temp=root;
newnode=(NODE *)malloc(sizeof(NODE));
newnode->data=num;
newnode->lchild=newnode->rchild=NULL;
depth++;
arr[ai]=num;
ai++;
while(temp!=NULL)
{
if(num<temp->data) {prev=temp;temp=temp->lchild;dec=0;}
else if(num>temp->data){prev=temp;temp=temp->rchild;dec=1;}
else if(num==temp->data){ printf("Element already Exists n"); depth--; ai--; return;  }
}
if(flag==0){root=newnode;flag=1;}
if(dec==0){prev->lchild=newnode;}
else if(dec==1){prev->rchild=newnode;}
}

inorder(NODE *jp)
{
if(jp==NULL) return;
else
{
inorder(jp->lchild);
printf("%dt",jp->data);
inorder(jp->rchild);
}
}

preorder(NODE *jp)
{
if(jp==NULL) return;
else
{
printf("%dt",jp->data);
preorder(jp->lchild);
preorder(jp->rchild);
}
}

postorder(NODE *jp)
{
if(jp==NULL) return;
else
{
inorder(jp->lchild);
inorder(jp->rchild);
printf("%dt",jp->data);
}
}

enqueue(int ele)
{
if(front==-1&&rear==-1)
{
front++;rear++;jpr++;
que[rear]=ele;
return;
}
rear++;
que[rear]=ele;
return;
}

place(NODE *jp,int ele)
{
NODE *a,*b;
while(jp->data!=ele)
{
while(ele<jp->data) jp=jp->lchild;
while(ele>jp->data) jp=jp->rchild;
}
if(jp->data==ele)
{
a=jp->lchild;
b=jp->rchild;
if(a==NULL&&b!=NULL) { enqueue(1016); enqueue(b->data); jpr++; return;}
else if(a!=NULL&&b==NULL){enqueue(a->data); enqueue(1016); jpr++; return;}
else if(a==NULL&&b==NULL) {enqueue(1016); enqueue(1016);jpr++;return; }
else
{
enqueue(a->data);
enqueue(b->data);
jpr++;
return;
}
}
}

heightfinder(NODE *jp,int ele)
{
int h=0;
while(jp->data!=ele)
{
while(ele<jp->data) {jp=jp->lchild; h++;}
while(ele>jp->data) {jp=jp->rchild; h++;}
}
if(jp->data==ele)
{
return h;
}
}

expo(int num)
{
int i,expo=1;
if(num==0) return 1;
else
{
for(i=0;i<num;i++)
expo=expo*2;
return expo;
}
}

jp1016()
{
int i=0,hp=1,hc;
enqueue(root->data);
for(i=0;i<ai;i++)
{
hc=heightfinder(root,arr[i]);
if(hc>hp) hp=hc;
}

for(i=0;i<expo(hp+1)-1;i++)
{
if(que[jpr]==1016) { enqueue(1016); enqueue(1016); jpr++; }
else place(root,que[jpr]);
}
display(hp+1);
}

display(int height)
{
int space=height-1,sp=space,i,n,j,m=0,k;

for(i=0;i<height;i++)
{
n=expo(i);
for(k=0;k<sp;k++)
printf(" ");
sp--;
for(j=0;j<n;j++)
{
if(que[m]!=1016) printf("%d ",que[m]);
else if(que[m]==1016) printf(" ");
m++;
}
printf("n");
}
reset();
}

reset()
{
int i;
front=-1,rear=-1,jpr=-1;
for(i=0;i<500;i++) que[i]=0;
}