Binary Search Tree

Insert(n) //creates BST and inserts node n
1.	[initialize pointer] *t := root;
2.	Check  if (root==NULL) then:
a.	Allocate memory for root node.
b.	Set root->data := n and root->r:=root->l:=NULL;
3.	Else 
a.	Repeat  steps b, c, and d while(t)
b.	If (n<t->data) then:
i.	If(t->l!=NULL) then : Set t := t->l;
ii.	Else create new node and Set t := t->l and break;
c.	Else if (n>t->data) then :
i.	If(t->r!=NULL) then : Set t := t->r;
ii.	Else create new node and Set t := t->r and break;
d.	Else print “NO DUPLICATES ALLOWED”;
e.	[end of while]
f.	Set t->data := n and t->r := t->l := NULL.
4.	Return

Inorder(t)//finds inorder traversal of BST pointed by pointer variable t.
1.	If(t) then:
a.	Call Inorder(t->l);
b.	Print t->data;
c.	Call Inorder(t->r);
2.	Exit

Preorder(t)//finds preorder traversal of BST pointed by pointer variable t.
1.	If(t) then:
a.	Print t->data;
b.	Call  Preorder(t->l);
c.	Call  Preorder(t->r);
2.	Exit

Postorder(t)//finds Postorder traversal of BST pointed by pointer variable t.
1.	If(t) then:
a.	Call Postorder(t->l);
b.	Call Postorder(t->r);
c.	Print t->data;
2.	Exit

Max(t)//Finds the maximum element in a tree.
1.	[initialize max] max:= 0;
2.	Repeat while(t)
a.	Set  max = t->data;
b.	If(max < t->data)
i.	Set max = t->data
c.	Set t=t->r;
3.	Return max
4.	[End]

Min(t)//Finds the minimum element in a tree.
1.	[initialize min] min= 0;
2.	Repeat while(t)
a.	Set  min = t->data;
b.	If(min >  t->data)
i.	Set min = t->data
c.	Set t=t->l;
3.	Return min.
4.	[End]

Height(t)//Finds height of the tree
1.	Initialize x = y = 0;
2.	If (t ) then:
a.	If (t->l) then :    
           Set   x = 1 + Height(t->l).
b.	If(t->r) then : 
               Set   y = 1 + Height(t->r). 
3.	If(x>y) then :  return x.
4.	Else return y.
5.	[end]

//WAP to implement Binary Search Tree operations (insert,delete,search,size,height)

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

void insert(int);
void showBST();
int search(int);
void delete(int);
void size();


struct node
{
int data;
struct node *left;
struct node *right;
struct node *parent;
};
typedef struct node Node;
Node *root=NULL,*prev,*ptr,*par=NULL;
int count=0,side;


int main()
{
int ch,item,h;
while(1)
{
ch=list();
	if(ch==1)
	{
		printf("Enter data to insert ");
		scanf("%d",&item);
		insert(item);
	}
	else if(ch==2)
	{
		printf("Enter data to delete ");
		scanf("%d",&item);
		delete(item);
	}
	else if(ch==3)
	{
		printf("Enter data to Search ");
		scanf("%d",&item);
		search(item);
	}
	else if(ch==4)
	{
		size();
	}
	else if(ch==5)
	{
		h = height(root);
		printf("Height of BST is %d",h); 
	}
	else if(ch==6)
		showBST(root);
	else
		exit(0);
	getch();
}
}

int height(Node *curNode)
{ 
	int curHeight = 0; 
	int curMax = 0; 
	return height1(curNode, curHeight, curMax);

} 

int height1(Node *curNode, int curHeight, int curMax)
{ 
	if(curNode != NULL)
	{ 
	if(curHeight > curMax) 
	{ 
		curMax = curHeight; 
	}  
	if(curNode->left != NULL) 
	{ 
		curMax = height1(curNode->left, curHeight + 1, curMax);
	}  
	if(curNode->right != NULL) 
	{ 
		curMax = height1(curNode->right, curHeight + 1, curMax);
	} 
	} 
return curMax; 
} 


int list()
{
	int ch;
	printf("\nChoose your option\n");
	printf("1. Insert in BST\n");
	printf("2. Delete in BST\n");
	printf("3. Search in BST\n");
	printf("4. Size of BST\n");
	printf("5. Height of BST\n");
	printf("6. Show BST content\n");
	printf("7. Exit\n");
	printf("Enter Choice ");
	scanf("%d",&ch);
return ch;
}

void insert(int item)
{
	Node *n;
	n=(Node *)malloc(sizeof(Node));
	n->data=item;
	n->left=NULL;
	n->right=NULL;
	n->parent=NULL;
	count=count+1;
	if(root==NULL)
		root=n;
	else
	{
		ptr=root;
		while(ptr!=NULL)
		{
			prev=ptr;
			if(item>ptr->data)
			{
			ptr=ptr->right;
			side=1;
			}
			else
			{
			ptr=ptr->left;
			side=0;
			}
		}
		if(side==1)
		{
			prev->right=n;
			n->parent=prev;
		}
		else
		{
			prev->left=n;
			n->parent=prev;
		}
	}
	printf("Insert Successfully!!");
}

int search(int item)
{
	ptr=root;
	if(ptr==NULL)
		printf("BST is empty so no match Found!!");
	else
	{
		while(ptr!=NULL)
		{
		if(ptr->data==item)
		{
			printf("Data is present\n");
			return ptr->data;
		}
		else if(item>ptr->data)
		{
			par=ptr;
			ptr=ptr->right;
		}
		else
		{
			par=ptr;
			ptr=ptr->left;
		}
		}
		printf("Data is not present in BST");
	}
}



void showBST(Node *ptr)
{
	if(ptr!=NULL)
	{
		showBST(ptr->left);
		printf("%d ",ptr->data);
		showBST(ptr->right);
	}
}

void delete(int item)
{
int k=search(item);
	if(k!=item)
		printf(" so delete unsuccessful!!!");
	else
	{
	Node *ptr1,*ptr2;
	count=count-1;
	if(ptr->left==NULL||ptr->right==NULL)
	{
		ptr1=ptr;
	}
	else
	{
		Node *y;
		if(ptr->right!=NULL)
		{
			y=ptr->right;
			while(y->left!=NULL)
			{
			y=y->left;
			}
			ptr1=y;
		}
		else
		{
		y=ptr->parent;
		while(y!=NULL&&ptr==y->right)
		{
		ptr=y;
		y=y->parent;
		}
		ptr1=y;
		}
	}
	if(ptr1->left!=NULL)
		ptr2=ptr1->left;
	else
		ptr2=ptr1->right;
	if(ptr2!=NULL)
		ptr2->parent=ptr1->parent;
	if(ptr1->parent==NULL)
		root=ptr2;
	else if(ptr1==ptr1->parent->left)
		ptr1->parent->left=ptr2;
	else
		ptr1->parent->right=ptr2;
	if(ptr1!=ptr)
		ptr->data=ptr1->data;
	printf("Delete successfull ");
	showBST(root);
	}
}

void size()
{
	printf("Total no. of nodes are : %d",count);
}