SEARCHING FOR A TARGET KEY IN A BINARY SEARCH TREE

Program

A complete C program for this search is as follows:

#include <stdio.h>
#include <stdlib.h>
struct tnode
{
  int data;
  struct tnode *lchild, *rchild;
};
/* A function to serch for a given data value in a binary search tree*/
struct tnode *search( struct tnode *p,int key)
   {
     struct tnode *temp;
      temp = p;
     while( temp != NULL)
       {
         if(temp->data == key)
                return(temp);
         else
   if(temp->data > key)
      temp = temp->lchild;
   else
      temp = temp->rchild;
        }
return(NULL);
}

/*an iterative function to print the binary tree in inorder*/
void inorder1(struct tnode *p)
{
  struct tnode *stack[100];
  int top;
  top = −1;
 if(p != NULL)
 {
    top++;
    stack[top] = p;
    p = p->lchild;
    while(top >= 0)
       {
          while ( p!= NULL)/* push the left child onto stack*/
           {
                       top++;
                 stack[top] =p;
                 p = p->lchild;
         }
         p = stack[top];
         top-;
         printf("%d\t",p->data);
         p = p->rchild;


         if ( p != NULL) /* push right child*/
           {
               top++;
                              stack[top] = p;
               p = p->lchild;
                 }

         }
    }
}
/* A function to insert a new node in binary search tree to
get a tree created*/
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);
}
void main()
{
   struct tnode *root = NULL, *temp = NULL;
   int n,x;
   printf("Enter the number of nodes in the tree\n");
   scanf("%d",&n);
   while( n - > 0)
       {
         printf("Enter the data value\n");
         scanf("%d",&x);
         root = insert(root,x);
       }
      printf("The created tree is :\n");
      inorder1(root);
      printf("\n Enter the value of the node to be searched\n");
      scanf("%d",&n);
      temp=search(root,n);
      if(temp != NULL)
          printf("The data value is present in the tree \n");
      else
          printf("The data value is not present in the tree \n");
}

Explanation

• 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
  3. The key value
• Output: If the key is present and appears in the created tree, then a message
  "The data value is present in the tree" appears. Otherwise the message
  "The data value is not present in the tree" appears.