C Program to Perform Binary Search Tree Operations

This C program searches an element in a Binary Search Tree.

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 subtree 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. Average search time complexity for BST is O(logn).

Here is the source code of the C program to search for an element in a Binary Search Tree. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<stdio.h>
```
```
#include<stdlib.h>
```
```
struct node
```
```
{
```
```
    int info;
```
```
	struct node*left;
```
```
	struct node*right;
```
```
};
```
```
typedef struct node BST;
```
```
BST *LOC, *PAR;
```
```
void search(BST *root, int item)
```
```
{
```
```
    BST *save,*ptr;
```
```
    if (root == NULL)
```
```
    {
```
```
        LOC = NULL;
```
```
        PAR=NULL;
```
```
    }
```
```
    if (item == root -> info)
```
```
    {
```
```
    LOC = root;
```
```
    PAR = NULL;
```
```
    return;
```
```
    }
```
```
    if (item < root->info)
```
```
    {
```
```
        save = root;
```
```
        ptr = root->left;
```
```
    }
```
```
    else
```
```
    {
```
```
        save = root;
```
```
        ptr = root -> right;
```
```
    }
```
```
    while( ptr != NULL)
```
```
    {
```
```
        if (ptr -> info == item)
```
```
        {
```
```
            LOC = ptr;
```
```
            PAR = save;
```
```
            return;
```
```
        }
```
```
        if(item < ptr->info)
```
```
        {
```
```
            save = ptr;
```
```
            ptr = ptr->left;
```
```
        }
```
```
        else
```
```
        {
```
```
            save = ptr;
```
```
            ptr = ptr->right;
```
```
        }
```
```
    }
```
```
    LOC = NULL;
```
```
    PAR = save;
```
```
    return;
```
```
}
```
```
 
```
```
struct node* findmin(struct node*r)
```
```
{
```
```
	if (r == NULL)
```
```
		return NULL;
```
```
	else if (r->left!=NULL)
```
```
		return findmin(r->left);
```
```
	else if (r->left == NULL)
```
```
		return r;
```
```
}
```

struct node*insert(struct node*r, int x)

```
{
```
```
	if (r == NULL)
```
```
	{
```

            r = (struct node*)malloc(sizeof(struct node));

```
            r->info = x;
```
```
            r->left = r->right = NULL;
```
```
            return r;
```
```
	}
```
```
	else if (x < r->info)
```

            r->left = insert(r->left, x);

```
	else if (x > r->info)
```

            r->right = insert(r->right, x);

```
	return r;
```
```
}
```
```
 
```
```
struct node* del(struct node*r, int x)
```
```
{
```
```
	struct node *t;
```
```
	if(r == NULL)
```
```
		printf("\nElement not found");
```
```
	else if (x < r->info)
```
```
            r->left = del(r->left, x);
```
```
	else if (x > r->info)
```

            r->right = del(r->right, x);

	else if ((r->left != NULL) && (r->right != NULL))

```
	{
```
```
            t = findmin(r->right);
```
```
            r->info = t->info;
```

            r->right = del(r->right, r->info);

```
	}
```
```
	else
```
```
	{
```
```
            t = r;
```
```
            if (r->left == NULL)
```
```
                r = r->right;
```
```
            else if (r->right == NULL)
```
```
                r = r->left;
```
```
            free(t);
```
```
	}
```
```
	return r;
```
```
}
```
```
 
```
```
 
```
```
int main()
```
```
{
```
```
    struct node* root = NULL;
```
```
    int x, c = 1, z;
```
```
    int element;
```
```
    char ch;
```
```
    printf("\nEnter an element: ");
```
```
    scanf("%d", &x);
```
```
    root = insert(root, x);
```

    printf("\nDo you want to enter another element :y or n");

```
    scanf(" %c",&ch);
```
```
    while (ch == 'y')
```
```
    {
```
```
        printf("\nEnter an element:");
```
```
        scanf("%d", &x);
```
```
        root = insert(root,x);
```

        printf("\nPress y or n to insert another element: y or n: ");

```
        scanf(" %c", &ch);
```
```
    }
```
```
    while(1)
```
```
    {
```

        printf("\n1 Insert an element ");

        printf("\n2 Delete an element");

        printf("\n3 Search for an element ");

```
        printf("\n4 Exit ");
```

        printf("\nEnter your choice: ");

```
        scanf("%d", &c);
```
```
        switch(c)
```
```
        {
```
```
            case 1:
```

                printf("\nEnter the item:");

```
                scanf("%d", &z);
```
```
                root = insert(root,z);
```
```
                break;
```
```
            case 2:
```

                printf("\nEnter the info to be deleted:");

```
                scanf("%d", &z);
```
```
                root = del(root, z);
```
```
		break;
```
```
            case 3:
```

                printf("\nEnter element to be searched:  ");

```
                scanf("%d", &element);
```
```
                search(root, element);
```
```
                if(LOC != NULL)
```

                    printf("\n%d Found in Binary Search Tree !!\n",element);

```
                else
```

                    printf("\nIt is not present in Binary Search Tree\n");

```
                break;
```
```
            case 4:
```
```
                printf("\nExiting...");
```
```
		return;
```
```
            default:
```

                printf("Enter a valid choice: ");

```
 
```
```
        }
```
```
    }
```
```
    return 0;
```
```
}
```

$ gcc bst.c -o bst
$ ./bst
 
Enter an element: 32
Do you want to enter another element, y or n: y
Enter an element: 54
Press y or n to insert another element, y or n: y
Enter an element: 65
Press y or n to insert another element, y or n: y
1 Insert an element 
2 Delete an element
3 Search for an element 
4 Exit 
Enter your choice: 3
Enter element to be searched:  32
32 Found in Binary Search Tree !!
 
1 Insert an element 
2 Delete an element
3 Search for an element 
4 Exit 
Enter your choice: 4
Exiting...