Binary Search Tree

Binary Search Tree is a variant of a binary tree. In which a X node has all nodes stored in the left subtree are less than X and all the node stored in the right subtree are greater than or equal to X. Each node follows the same rules with respect to nodes in their left and right subtrees.

In the above BST, the root node is 10, all the left nodes of 10 is less than 10 and all the right nodes of the root node are greater than 10. Similarly, all the child nodes follow the same rules.

Binary Search Tree Example

Suppose, we have the following array -

28, 10, 35, 19, 13, 42

The following example shows the process to create a Binary Search Tree.

The binary search tree is important in data structure because of it's fast operations like insertion, deletion, searching. The time complexity of all these operations take O(log n) time.

Binary Search Tree Operations

The operations perform on BST are -

• Insertion
• Searching
• Deletion

Binary Search Tree Program in C

#include <stdio.h>
#include <stdlib.h>
 
struct bstnode
{
    int value;
    struct bstnode *lnode;
    struct bstnode *rnode;
}*root = NULL, *temp = NULL, *t2, *t1;
 

void insert_element();
void inorder_traversal(struct bstnode *t);
void create_bst();
void search(struct bstnode *t);
void preorder_traversal(struct bstnode *t);
void postorder_traversal(struct bstnode *t);
 
int flag = 1;
 
void main()
{
    int choice;
 
	printf("\nBinary Search Tree Operations"); 
		  printf("\nEnter 1 to insert element in tree "); 
		  printf("\nEnter 2 to preorder traversal "); 
		  printf("\nEnter 3 to postorder traversal "); 
		  printf("\nEnter 4 to inorder traversal "); 
    while(1)
    {
        printf("\nEnter your choice : ");
        scanf("%d", &choice);
        switch (choice)
        {
        case 1:    
            insert_element();
            break;
		case 2:    
            preorder_traversal(root);
            break;
        case 3:    
            postorder_traversal(root);
            break;
        case 4:    
            inorder_traversal(root);
            break;
        
        case 6:    
            exit(0);
        default :     
            printf("Wrong choice, Please enter correct choice  ");
            break;    
        }
    }
}
 
/* To insert a node in the tree */
void insert_element()
{
    create_bst();
    if (root == NULL) 
        root = temp;
    else    
        search(root);    
}
 
/* To create a node */
void create_bst()
{
    int data;
 
    printf("Enter data of node to be inserted : ");
    scanf("%d", &data);
    temp = (struct bstnode *)malloc(1*sizeof(struct bstnode));
    temp->value = data;
    temp->lnode = temp->rnode = NULL;
}
 
/* Function to search the appropriate position to insert the new node */
void search(struct bstnode *t)
{
    if ((temp->value > t->value) && (t->rnode != NULL))      /* value more than root node value insert at right */
        search(t->rnode);
    else if ((temp->value > t->value) && (t->rnode == NULL))
        t->rnode = temp;
    else if ((temp->value < t->value) && (t->lnode != NULL))    /* value less than root node value insert at left */
        search(t->lnode);
    else if ((temp->value < t->value) && (t->lnode == NULL))
        t->lnode = temp;
}
 
/* recursive function to perform inorder traversal of tree */
void inorder_traversal(struct bstnode *t)
{
    if (root == NULL)
    {
        printf("No elements in a tree to display");
        return;
    }
    if (t->lnode != NULL)    
        inorder_traversal(t->lnode);
    printf("%d -> ", t->value);
    if (t->rnode != NULL)    
        inorder_traversal(t->rnode);
}
 

/* To find the preorder traversal */
void preorder_traversal(struct bstnode *t)
{
    if (root == NULL)
    {
        printf("No elements in a tree to display");
        return;
    }
    printf("%d -> ", t->value);
    if (t->lnode != NULL)    
        preorder_traversal(t->lnode);
    if (t->rnode != NULL)    
        preorder_traversal(t->rnode);
}
 
/* To find the postorder traversal */
void postorder_traversal(struct bstnode *t)
{
    if (root == NULL)
    {
        printf("No elements in a tree to display ");
        return;
    }
    if (t->lnode != NULL) 
        postorder_traversal(t->lnode);
    if (t->rnode != NULL) 
        postorder_traversal(t->rnode);
    printf("%d -> ", t->value);
}

Output of the above program

OPERATIONS ---
Binary Search Tree Operations
Enter 1 to insert element in tree 
Enter 2 to preorder traversal 
Enter 3 to postorder traversal 
Enter 4 to inorder traversal 
Enter your choice : 1
Enter data of node to be inserted : 30

Enter your choice : 1
Enter data of node to be inserted : 23

Enter your choice : 1
Enter data of node to be inserted : 56

Enter your choice : 1
Enter data of node to be inserted : 78

Enter your choice : 1
Enter data of node to be inserted : 70

Enter your choice : 2
30 -> 23 -> 56 -> 78 -> 70 -> 
Enter your choice : 3
23 -> 70 -> 78 -> 56 -> 30 -> 
Enter your choice : 4
23 -> 30 -> 56 -> 70 -> 78 -> 
Enter your choice :