Binary Search Tree | Searching

We assume that a key and the subtree in which the key is searched for are given as an input. We'll take the full advantage of the BST-property.

Suppose we are at a node. If the node has the key that is being searched for, then the search is over. Otherwise, the key at the current node is either strictly smaller than the key that is searched for or strictly greater than the key that is searched for. If the former is the case, then by the BST property, all the keys in th left subtree are strictly less than the key that is searched for. That means that we do not need to search in the left subtree. Thus, we will examine only the right subtree. If the latter is the case, by symmetry we will examine only the right subtree.

Searching | Best Case

It takes O(lg(n)) time to search in this tree. as the hight is lg(n).

        5
       / \
      1   6
     / \
    0   2

Searching | Wrost Case

It takes O(n) time to search in this tree. as the hight is n.

        5
       / 
      4   
     / 
    3 
   / 
  2

C Program

#include <stdio.h>
#include <stdlib.h>

typedef struct BST
{
   struct BST *lc, *rc;
   int data;
}BST;

void inorder(BST *t)
{
    if(t != NULL) {
        inorder(t->lc);
        printf("%d ",t->data);
        inorder(t->rc);
    }
}

BST *insertNode(BST *T,int item)
{
    BST *curr = T,*prev = NULL,*temp = NULL;
    int found = 0;
    //Search for the proper position of the node to insert...
    while(curr != NULL && !found)
    {
        //Keeping track of the previous node...
        prev = curr; 
        // If item already exists...
        if(curr->data == item) 
        {
            found = 1;
            printf("\nItem %d Already Exists In The BST.\n",item);
        }
        else if(curr->data > item) {
            curr = curr->lc;
        }
        else {
            curr = curr->rc;
        }
    }
    //Creating a new node...
    temp = (BST*)malloc(sizeof(BST));
    temp->data = item;
    temp->lc = NULL;
    temp->rc = NULL;
    //Only for first node or time...
    if(T == NULL)
        T = temp;
    else if(item > prev->data)
        prev->rc = temp;
    else
        prev->lc = temp;
    return T;
}

short searchNode(BST *T, int item)
{
 BST *curr = T,*prev = NULL,*temp = NULL;
    int found = 0;
    //Search for the proper position of the node to insert...
    while(curr != NULL && !found)
    {
        // If item already exists...
        if(curr->data == item) {
         return 1;
        }
        else if(curr->data > item) {
            curr = curr->lc;
        }
        else {
            curr = curr->rc;
        }
    }
    return 0;
}
int main()
{
    BST *T = NULL;
    int value;
    
    printf("Enter VAlues In BST:\n");
    scanf("%d",&value);
    while (value != -999) {
        T = insertNode(T, value);
        scanf("%d",&value);
    }
    
    inorder(T);

    printf("\nEnter A Search Value: ");
    scanf("%d",&value);
    printf("%d Is %sOn The Tree.\n",value,searchNode(T, value)?"":"Not ");
    
    printf("\nEnter Another Search Value: ");
    scanf("%d",&value);
    printf("%d Is %sOn The Tree.\n",value,searchNode(T, value)?"":"Not ");
    return 0;
}

Output

Enter VAlues In BST:
3 2 1 4 5 6 -999
1 2 3 4 5 6
Enter A Search Value: 5
5 Is On The Tree.

Enter Another Search Value: 7
7 Is Not On The Tree.