Write A Program To Creating a Binary Search Tree With Explanation

We assume that every node of a binary search tree is capable of holding an integer data item and that the links can be made to point to the root of the left subtree and the right subtree, respectively. Therefore, the structure of the node can be defined using the following declaration:

struct tnode
    {
        int data;
        struct tnode *lchild,*rchild;
    };

    A complete C program to create a binary search tree follows:
#include <stdio.h>
#include <stdlib.h>
struct tnode
{
   int data;
   struct tnode *lchild, *rchild;
};

struct tnode *insert(struct tnode *p,int val)
{
   struct tnode *temp1,*temp2;
   if(p == NULL)
   {
      p = (struct tnode *) malloc(sizeof(struct tnode)); /* insert the new node as root node*/
         if(p == NULL)
           {
      printf("Cannot allocate\n");
      exit(0);
          }
       p->data = val;
       p->lchild=p->rchild=NULL;
   }
  else
  {
   temp1 = p;
   /* traverse the tree to get a pointer to that node whose child will be the newly created node*/
  while(temp1 != NULL)
  {
     temp2 = temp1;
     if( temp1 ->data > val)
          temp1 = temp1->lchild;
     else
          temp1 = temp1->rchild;
  }
  if( temp2->data > val)
  {
  temp2->lchild = (struct tnode*)malloc(sizeof(struct tnode));/*inserts the newly created node as left child*/
          temp2 = temp2->lchild;
          if(temp2 == NULL)
               {
          printf("Cannot allocate\n");
          exit(0);
              }
          temp2->data = val;
          temp2->lchild=temp2->rchild = NULL;
  }
  else
  {
     temp2->rchild = (struct tnode*)malloc(sizeof(struct tnode));/ *inserts the newly created node
   as left child*/
      temp2 = temp2->rchild;
      if(temp2 == NULL)
           {
      printf("Cannot allocate\n");
      exit(0);
          }
     temp2->data = val;
     temp2->lchild=temp2->rchild = NULL;
}
}
return(p);
}
/* a function to binary tree in inorder */
void inorder(struct tnode *p)
   {
      if(p != NULL)
        {
           inorder(p->lchild);
          printf("%d\t",p->data);
         inorder(p->rchild);
         }
   }
void main()
{
   struct tnode *root = NULL;
   int n,x;
   printf("Enter the number of nodes\n");
   scanf("%d",&n);
   while( n - > 0)
     {
         printf("Enter the data value\n");
         scanf("%d",&x);
         root = insert(root,x);
    }
     inorder(root);
 }

Explanation

1. To create a binary search tree, we use a function called insert, which creates a new node with the data value supplied as a parameter to it, and inserts it into an already existing tree whose root pointer is also passed as a parameter.
2. The function accomplishes this by checking whether the tree whose root pointer is passed as a parameter is empty. If it is empty, then the newly created node is inserted as a root node. If it is not empty, then it copies the root pointer into a variable temp1. It then stores the value of temp1 in another variable, temp2, and compares the data value of the node pointed to by temp1 with the data value supplied as a parameter. If the data value supplied as a parameter is smaller than the data value of the node pointed to by temp1, it copies the left link of the node pointed to by temp1 into temp1 (goes to the left); otherwise it copies the right link of the node pointed to by temp1 into temp1 (goes to the right).
3. It repeats this process until temp1 reaches 0. When temp1 becomes 0, the new node is inserted as a left child of the node pointed to by temp2, if the data value of the node pointed to by temp2 is greater than the data value supplied as a parameter. Otherwise, the new node is inserted as a right child of the node pointed to by temp2. Therefore the insert procedure is:
   • Input: 1. The number of nodes that the tree to be created should have
     2. The data values of each node in the tree to be created
   • Output: The data value of the nodes of the tree in inorder