Implementation of Binary Search Tree in C

- October 01, 2017

Binary Search Tree

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties −

The left sub-tree of a node has a key less than or equal to its parent node's key.
The right sub-tree of a node has a key greater than to its parent node's key.

Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-tree.

BST is a collection of nodes arranged in a way where they maintain BST properties. Each node has a key and an associated value. While searching, the desired key is compared to the keys in BST and if found, the associated value is retrieved.

Following is a pictorial representation of BST −

Basic Operations:

Following are the basic operations of a tree −

Search − Searches an element in a tree.
Insert − Inserts an element in a tree.
Pre-order Traversal − Traverses a tree in a pre-order manner.
In-order Traversal − Traverses a tree in an in-order manner.
Post-order Traversal − Traverses a tree in a post-order manner.

Let us check out the code :)



#include <stdio.h> 
#include <conio.h>
#include
typedef struct tnode
{
 int data;
 struct tnode *right, *left;
} TNODE;

TNODE *create(TNODE *, int);
void inorder(TNODE *);
void preorder(TNODE *);
void postorder(TNODE *);

void main()
{
 TNODE *root = NULL; /* Main Program */
 int opn, elem, n, i;
 clrscr();
 while(1)
 {
  printf("  ### Binary Search Tree Operations ###");
  printf("\n Press 1-Creation of BST");
  printf("\n       2-Traverse in Inorder");
  printf("\n       3-Traverse in Preorder");
  printf("\n       4-Traverse in Postorder");
  printf("\n       5-Exit\n");
  printf("\n       Your option ? ");
  scanf("%d", &opn);
  switch(opn)
  {
   case 1:
    root = NULL;
    printf("\nBST for How Many Nodes ?");
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
    {
     printf("Read the Data for Node %d ?", i);
     scanf("%d", &elem);
     root = create(root, elem);
    }
    printf("\nBST with %d nodes is ready to Use!!\n", n);
    break;
   case 2:
    printf("\n BST Traversal in INORDER \n");
    inorder(root);
    break;
   case 3:
    printf("\n BST Traversal in PREORDER \n");
    preorder(root);
    break;
   case 4:
    printf("\n BST Traversal in POSTORDER \n");
    postorder(root);
    break;
   case 5:
    exit(0);
   default:
    printf("\n\nInvalid Option !!! Try Again !! \n\n");
    break;
  }
  getch();

 }
}

TNODE *create(TNODE *root, int elem)
{
 if (root == NULL)
 {
  root = (TNODE *) malloc(sizeof(TNODE));
  root->left = root->right = NULL;
  root->data = elem;
  return root;
 }
 else
 {
  if (elem < root->data)
  {
   root->left = create(root->left, elem);
  }
  else if (elem > root->data)
  {
   root->right = create(root->right, elem);
  }
  else
  {
   printf(" Duplicate Element !! Not Allowed !!!");
  }
  return (root);
 }
}

void inorder(TNODE *root)
{
 if (root != NULL)
 {
  inorder(root->left);
  printf(" %d ", root->data);
  inorder(root->right);
 }
}

void preorder(TNODE *root)
{
 if (root != NULL)
 {
  printf(" %d ", root->data);
  preorder(root->left);
  preorder(root->right);
 }
}

void postorder(TNODE *root)
{
 if (root != NULL)
 {
  postorder(root->left);
  postorder(root->right);
  printf(" %d ", root->data);
 }
}