Blog

This post focuses on the Binary search tree (BST) and the implementation of a Binary Search Tree program for Insertion, Deletion, and Traversal in C.

What is a Binary Search Tree (BST)?

It is one of the most used data structures where the nodes are placed together in a tree-like structure. Tree-like structure refers to the structure where there is a parent node and each parent is linked with its child nodes. But in BST a parent node cannot have more than two child nodes. The top node being the root node in the structure.

NOTE:
The child nodes on the left of its parent node are equal to its parent node.
The child nodes in the right of its parent node are greater than its parent node.

C Program for Binary Search Tree (BST)

#include < stdio.h > 
#include <malloc.h >

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

void find(int item, struct node **par, struct node **loc)
{
  struct node *ptr, *ptrsave;

  if (root == NULL)
  {
    *loc = NULL;
    *par = NULL;
    return;
  }

  if (item == root->info)
  {
    *loc = root;
    *par = NULL;
    return;
  }

  if (item < root->info)
    ptr = root->lchild;
  else
    ptr = root->rchild;
  ptrsave = root;

  while (ptr != NULL)
  {
    if (item == ptr->info)
    {*loc = ptr;
      *par = ptrsave;
      return;
    }

    ptrsave = ptr;
    if (item < ptr->info)
      ptr = ptr->lchild;
    else
      ptr = ptr->rchild;
  }

  *loc = NULL;
  *par = ptrsave;
}

void insert(int item)
{
  struct node *tmp, *parent, *location;
  find(item, &parent, &location);
  if (location != NULL)
  {
    printf("Item already present");
    return;
  }

  tmp = (struct node *) malloc(sizeof(struct node));
  tmp->info = item;
  tmp->lchild = NULL;
  tmp->rchild = NULL;

  if (parent == NULL)
    root = tmp;
  else
  if (item < parent->info)
    parent->lchild = tmp;
  else
    parent->rchild = tmp;
}

void case_a(struct node *par, struct node *loc)
{
  if (par == NULL)
    root = NULL;
  else
  if (loc == par->lchild)
    par->lchild = NULL;
  else
    par->rchild = NULL;
}

void case_b(struct node *par, struct node *loc)
{
  struct node * child;

  //intializing child
  if (loc->lchild != NULL)
    child = loc->lchild;
  else
    child = loc->rchild;

  if (par == NULL)
    root = child;
  else
  if (loc == par->lchild)
    par->lchild = child;
  else
    par->rchild = child;
}

void case_c(struct node *par, struct node *loc)
{
  struct node *ptr, *ptrsave, *suc, *parsuc;

  ptrsave = loc;
  ptr = loc->rchild;
  while (ptr->lchild != NULL)
  {
    ptrsave = ptr;
    ptr = ptr->lchild;
  }

  suc = ptr;
  parsuc = ptrsave;

  if (suc->lchild == NULL && suc->rchild == NULL)
    case_a(parsuc, suc);
  else
    case_b(parsuc, suc);

  if (par == NULL)
    root = suc;
  else
  if (loc == par->lchild)
    par->lchild = suc;
  else
    par->rchild = suc;

  suc->lchild = loc->lchild;
  suc->rchild = loc->rchild;
}

int del(int item)
{
  struct node *parent, *location;
  if (root == NULL)
  {
    printf("Tree empty");
    return 0;
  }

  find(item, &parent, &location);
  if (location == NULL)
  {
    printf("Item not present in tree");
    return 0;
  }

  if (location->lchild == NULL && location->rchild == NULL)
    case_a(parent, location);
  if (location->lchild != NULL && location->rchild == NULL)
    case_b(parent, location);
  if (location->lchild == NULL && location->rchild != NULL)
    case_b(parent, location);
  if (location->lchild != NULL && location->rchild != NULL)
    case_c(parent, location);
  free(location);
}

int preorder(struct node *ptr)
{
  if (root == NULL)
  {
    printf("Tree is empty");
    return 0;
  }

  if (ptr != NULL)
  {
    printf("%d  ", ptr->info);
    preorder(ptr->lchild);
    preorder(ptr->rchild);
  }
}

void inorder(struct node *ptr)
{
  if (root == NULL)
  {
    printf("Tree is empty");
    return;
  }

  if (ptr != NULL)
  {
    inorder(ptr->lchild);
    printf("%d  ", ptr->info);
    inorder(ptr->rchild);
  }
}

void postorder(struct node *ptr)
{
  if (root == NULL)
  {
    printf("Tree is empty");
    return;
  }

  if (ptr != NULL)
  {
    postorder(ptr->lchild);
    postorder(ptr->rchild);
    printf("%d  ", ptr->info);
  }
}

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

main()
{
  int choice, num;
  root = NULL;
  while (1)
  {
    printf("\n");
    printf("1.Insert\n");
    printf("2.Delete\n");
    printf("3.Inorder Traversal\n");
    printf("4.Preorder Traversal\n");
    printf("5.Postorder Traversal\n");
    printf("6.Display\n");
    printf("7.Quit\n");
    printf("Enter your choice : ");
    scanf("%d", &choice);

    switch (choice)
    {
      case 1:
        printf("Enter the number to be inserted : ");
        scanf("%d", &num);
        insert(num);
        break;
      case 2:
        printf("Enter the number to be deleted : ");
        scanf("%d", &num);
        del(num);
        break;
      case 3:
        inorder(root);
        break;
      case 4:
        preorder(root);
        break;
      case 5:
        postorder(root);
        break;
      case 6:
        display(root, 1);
        break;
      case 7:
        break;
      default:
        printf("Wrong choice\n");
    }
  }
}

Output of Binary Search Tree Program in C: After execution following will be displayed in Screen.

1.Insert
2.Delete
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 250 

1.Insert
2.Delete
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 1
Enter the number to be inserted : 350 

1.Insert
2.Delete
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 4
Enter the number to be inserted : 250 
250  350
1.Insert
2.Delete
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 6
   
        350
   250
1.Insert
2.Delete
3.Inorder Traversal
4.Preorder Traversal
5.Postorder Traversal
6.Display
7.Quit
Enter your choice : 

Binary search in C programming is to find an element’s position in a sorted Array. The following program for binary search finds the location of a searched element from the array.

Binary search is applied to sorted elements. So if the array is not sorted, you must sort it using a sorting technique. You can use any one of the sorting algorithms in c such as merge or bubble sort etc.

The search for the element that is to be searched and if found in an array, it will print its index number that the key is present.

Binary Search Time Complexity:

• Best case:  O(1)
• Average case:  O(log n)
• Worst case:  O(log n)

C Program for Binary Search

Source Code:

#include <stdio.h>

int main()
{
  int arr[100], i, numElemt, first, last, mid, searchElemt;

  printf("How many elements do you want?\n");
  scanf("%d", &numElemt);

  printf("Enter the Elements:\n", numElemt);

 //taking the elements 
  for (i = 0; i < numElemt; i++)
    scanf("%d", &arr[i]);

  printf("Enter the specific elements from the list that needed to be searched:\n");
  scanf("%d", &searchElemt);

  first = 0;
  last = numElemt - 1;
  mid = (first + last) / 2;

  while (first <= last)
  {
    if (arr[mid] < searchElemt)
    {
      first = mid + 1;
    }
    else if (arr[mid] == searchElemt)
    {
      printf("The elements you are searching is found at location: %d.\n", mid + 1);
      break;
    }
    else
    {
      last = mid - 1;
    }

    mid = (first + last) / 2;
  }

//if the searching element is not on the list
  if (first > last)
    printf("The element you are looking for is not present in the list.\n");

  return 0;
}

The output of binary search in c language.