C Program for Recursive operations in Binary Search Tree

By | April 16, 2017

Recursive operations in Binary Search Tree


Write a C Program for Recursive operations in Binary Search Tree. Here’s simple Program for Recursive operations like Search, Insert, Delete, Preorder, postorder, inorder traversal, height, min and max, display in Binary Search Tree in C Programming Language.


What is Tree ?


In linear data structure, data is organized in sequential order and in non-linear data structure, data is organized in random order. Tree is a very popular data structure used in wide range of applications.

A tree data structure can be defined as follows…

  • Tree is a non-linear data structure which organizes data in hierarchical structure and this is a recursive definition.

A tree data structure can also be defined as follows…

  • Tree data structure is a collection of data (Node) which is organized in hierarchical structure and this is a recursive definition.

Every individual element is called as Node. Node in a tree data structure, stores the actual data of that particular element and link to next element in hierarchical structure.


Below is the source code for C Program for Recursive operations in Binary Search Tree which is successfully compiled and run on Windows System to produce desired output as shown below :


SOURCE CODE : :


/*  C Program for Recursive operations in Binary Search Tree  */


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

struct node
{
	struct node *lchild;
	int info;
	struct node *rchild;
};

struct node *search(struct node *ptr, int skey);
struct node *insert(struct node *ptr, int ikey);
struct node *del(struct node *ptr, int dkey);
struct node *Min(struct node *ptr);
struct node *Max(struct node *ptr);
int height(struct node *ptr);
void preorder(struct node *ptr);
void inorder(struct node *ptr);
void postorder(struct node *ptr);
void display(struct node *ptr,int level);

int main( )
{
	struct node *root=NULL,*ptr;
	int choice,k;

	while(1)
	{
		printf("\n");
		printf("1.Search\n");
		printf("2.Insert\n");
		printf("3.Delete\n");
		printf("4.Preorder Traversal\n");
		printf("5.Inorder Traversal\n");
		printf("6.Postorder Traversal\n");
		printf("7.Height of tree\n");
		printf("8.Find minimum and maximum\n");
		printf("9.Display\n");
		printf("10.Quit\n");
		printf("\nEnter your choice : ");
		scanf("%d",&choice);

		switch(choice)
		{

		case 1:
			printf("\nEnter the key to be searched : ");
			scanf("%d",&k);
			ptr = search(root, k);
			if(ptr!=NULL)
				printf("\nKey found\n");
			break;

		case 2:
			printf("\nEnter the key to be inserted : ");
			scanf("%d",&k);
			root = insert(root, k);
			break;

		case 3:
			printf("\nEnter the key to be deleted : ");
			scanf("%d",&k);
			root = del(root,k);
			break;

		 case 4:
			preorder(root);
			break;

		 case 5:
			inorder(root);
			break;

		 case 6:
		     postorder(root);
			 break;
		   printf("\n");
		 case 7:
			 printf("\nHeight of tree is %d\n", height(root));
			 break;

		 case 8:
			ptr = Min(root);
			if(ptr!=NULL)
				printf("\nMinimum key is %d\n", ptr->info );
			ptr = Max(root);
			if(ptr!=NULL)
				printf("\nMaximum key is %d\n", ptr->info );
			break;

         case 9:
            printf("\n");
            display(root,0);
            printf("\n");
            break;

		 case 10:
			exit(1);

		 default:
			printf("\nWrong choice\n");
		}/*End of switch */
	}/*End of while */

	return 0;

}/*End of main( )*/

struct node *search(struct node *ptr, int skey)
{
	if(ptr==NULL)
	{
		printf("key not found\n");
		return NULL;
	}
	else if(skey < ptr->info)/*search in left subtree*/
		return search(ptr->lchild, skey);
	else if(skey > ptr->info)/*search in right subtree*/
		return search(ptr->rchild, skey);
	else /*skey found*/
		return ptr;
}/*End of search()*/

struct node *insert(struct node *ptr, int ikey )
{
	if(ptr==NULL)
	{
		ptr = (struct node *) malloc(sizeof(struct node));
		ptr->info = ikey;
		ptr->lchild = NULL;
		ptr->rchild = NULL;
	}
	else if(ikey < ptr->info)	/*Insertion in left subtree*/
		ptr->lchild = insert(ptr->lchild, ikey);
	else if(ikey > ptr->info)	/*Insertion in right subtree */
		ptr->rchild = insert(ptr->rchild, ikey);
	else
		printf("\nDuplicate key\n");
	return ptr;
}/*End of insert( )*/

struct node *del(struct node *ptr, int dkey)
{
	struct node *tmp, *succ;

	if( ptr == NULL)
	{
		printf("\nDkey not found\n");
		return(ptr);
	}
	if( dkey < ptr->info )/*delete from left subtree*/
		ptr->lchild = del(ptr->lchild, dkey);
	else if( dkey > ptr->info )/*delete from right subtree*/
		ptr->rchild = del(ptr->rchild, dkey);
	else
	{
		/*key to be deleted is found*/
		if( ptr->lchild!=NULL  &&  ptr->rchild!=NULL )  /*2 children*/
		{
			succ=ptr->rchild;
			while(succ->lchild)
				succ=succ->lchild;
			ptr->info=succ->info;
			ptr->rchild = del(ptr->rchild, succ->info);
		}
		else
		{
			tmp = ptr;
			if( ptr->lchild != NULL ) /*only left child*/
				ptr = ptr->lchild;
			else if( ptr->rchild != NULL) /*only right child*/
				ptr = ptr->rchild;
			else	/* no child */
				ptr = NULL;
			free(tmp);
		}
	}
	return ptr;
}/*End of del( )*/

struct node *Min(struct node *ptr)
{
	if(ptr==NULL)
		return NULL;
	else if(ptr->lchild==NULL)
        return ptr;
	else
		return Min(ptr->lchild);
}/*End of min()*/

struct node *Max(struct node *ptr)
{
	if(ptr==NULL)
		return NULL;
	else if(ptr->rchild==NULL)
        return ptr;
	else
		return Max(ptr->rchild);
}/*End of max()*/

void preorder(struct node *ptr)
{
	if(ptr == NULL )	/*Base Case*/
		return;
	printf("%d  ",ptr->info);
	preorder(ptr->lchild);
	preorder(ptr->rchild);
}/*End of preorder( )*/

void inorder(struct node *ptr)
{
	if(ptr == NULL )/*Base Case*/
		return;
	inorder(ptr->lchild);
	printf("%d  ",ptr->info);
	inorder(ptr->rchild);
}/*End of inorder( )*/

void postorder(struct node *ptr)
{
	if(ptr == NULL )/*Base Case*/
		return;
	postorder(ptr->lchild);
	postorder(ptr->rchild);
	printf("%d  ",ptr->info);

}/*End of postorder( )*/

int height(struct node *ptr)
{
	int h_left, h_right;

	if (ptr == NULL) /*Base Case*/
		return 0;

	h_left =  height(ptr->lchild);
	h_right = height(ptr->rchild);

	if (h_left > h_right)
		return 1 + h_left;
	else
		return 1 + h_right;
}/*End of height()*/

void display(struct node *ptr,int level)
{
	int i;
	if(ptr == NULL )/*Base Case*/
		return;
	else
    {
		display(ptr->rchild, level+1);
		printf("\n");
		for (i=0; i<level; i++)
			printf("    ");
		printf("%d", ptr->info);
		display(ptr->lchild, level+1);
	}
}/*End of display()*/


OUTPUT : :


/*  C Program for Recursive operations in Binary Search Tree  */

1.Search
2.Insert
3.Delete
4.Preorder Traversal
5.Inorder Traversal
6.Postorder Traversal
7.Height of tree
8.Find minimum and maximum
9.Display
10.Quit

Enter your choice : 2

Enter the key to be inserted : 6

1.Search
2.Insert
3.Delete
4.Preorder Traversal
5.Inorder Traversal
6.Postorder Traversal
7.Height of tree
8.Find minimum and maximum
9.Display
10.Quit

Enter your choice : 2

Enter the key to be inserted : 8

1.Search
2.Insert
3.Delete
4.Preorder Traversal
5.Inorder Traversal
6.Postorder Traversal
7.Height of tree
8.Find minimum and maximum
9.Display
10.Quit

Enter your choice : 2

Enter the key to be inserted : 7

1.Search
2.Insert
3.Delete
4.Preorder Traversal
5.Inorder Traversal
6.Postorder Traversal
7.Height of tree
8.Find minimum and maximum
9.Display
10.Quit

Enter your choice : 2

Enter the key to be inserted : 9

1.Search
2.Insert
3.Delete
4.Preorder Traversal
5.Inorder Traversal
6.Postorder Traversal
7.Height of tree
8.Find minimum and maximum
9.Display
10.Quit

Enter your choice : 2

Enter the key to be inserted : 3

1.Search
2.Insert
3.Delete
4.Preorder Traversal
5.Inorder Traversal
6.Postorder Traversal
7.Height of tree
8.Find minimum and maximum
9.Display
10.Quit

Enter your choice : 2

Enter the key to be inserted : 4

1.Search
2.Insert
3.Delete
4.Preorder Traversal
5.Inorder Traversal
6.Postorder Traversal
7.Height of tree
8.Find minimum and maximum
9.Display
10.Quit

Enter your choice : 2

Enter the key to be inserted : 2

1.Search
2.Insert
3.Delete
4.Preorder Traversal
5.Inorder Traversal
6.Postorder Traversal
7.Height of tree
8.Find minimum and maximum
9.Display
10.Quit

Enter your choice : 9


        9
    8
        7
6
        4
    3
        2

1.Search
2.Insert
3.Delete
4.Preorder Traversal
5.Inorder Traversal
6.Postorder Traversal
7.Height of tree
8.Find minimum and maximum
9.Display
10.Quit

Enter your choice : 1

Enter the key to be searched : 7

Key found

1.Search
2.Insert
3.Delete
4.Preorder Traversal
5.Inorder Traversal
6.Postorder Traversal
7.Height of tree
8.Find minimum and maximum
9.Display
10.Quit

Enter your choice : 3

Enter the key to be deleted : 2

1.Search
2.Insert
3.Delete
4.Preorder Traversal
5.Inorder Traversal
6.Postorder Traversal
7.Height of tree
8.Find minimum and maximum
9.Display
10.Quit

Enter your choice : 3

Enter the key to be deleted : 4

1.Search
2.Insert
3.Delete
4.Preorder Traversal
5.Inorder Traversal
6.Postorder Traversal
7.Height of tree
8.Find minimum and maximum
9.Display
10.Quit

Enter your choice : 9


        9
    8
        7
6
    3

1.Search
2.Insert
3.Delete
4.Preorder Traversal
5.Inorder Traversal
6.Postorder Traversal
7.Height of tree
8.Find minimum and maximum
9.Display
10.Quit

Enter your choice : 4
6  3  8  7  9
1.Search
2.Insert
3.Delete
4.Preorder Traversal
5.Inorder Traversal
6.Postorder Traversal
7.Height of tree
8.Find minimum and maximum
9.Display
10.Quit

Enter your choice : 5
3  6  7  8  9
1.Search
2.Insert
3.Delete
4.Preorder Traversal
5.Inorder Traversal
6.Postorder Traversal
7.Height of tree
8.Find minimum and maximum
9.Display
10.Quit

Enter your choice : 6
3  7  9  8  6
1.Search
2.Insert
3.Delete
4.Preorder Traversal
5.Inorder Traversal
6.Postorder Traversal
7.Height of tree
8.Find minimum and maximum
9.Display
10.Quit

Enter your choice : 7

Height of tree is 3

1.Search
2.Insert
3.Delete
4.Preorder Traversal
5.Inorder Traversal
6.Postorder Traversal
7.Height of tree
8.Find minimum and maximum
9.Display
10.Quit

Enter your choice : 8

Minimum key is 3

Maximum key is 9

1.Search
2.Insert
3.Delete
4.Preorder Traversal
5.Inorder Traversal
6.Postorder Traversal
7.Height of tree
8.Find minimum and maximum
9.Display
10.Quit

Enter your choice : 9


        9
    8
        7
6
    3

1.Search
2.Insert
3.Delete
4.Preorder Traversal
5.Inorder Traversal
6.Postorder Traversal
7.Height of tree
8.Find minimum and maximum
9.Display
10.Quit

Enter your choice : 10

Process returned 1

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in short interval.


Thanks for reading the post….

Leave a Reply