Thursday 24 May 2012

Binary Search Tree : Insert and Search, C code


Implement a Binary Search Tree


// Binary Search Tree - O(logn) for search and insert operation.
// For more info. BST - en.wikipedia.org/wiki/Binary_search_tree 
 
#include<stdio.h>
#include<stdlib.h>
typedef struct treetype
    {
    int value;
    struct tree *right;
    struct tree *left;
    }tree;
tree *root;
int rootvalue;
void insert(tree *node,int x);
void display(tree *node);
void search(tree *node,int x);
int main()
{
int y,x,z;
printf("Enter root value\n");
scanf("%d",&rootvalue);
root=(tree *)malloc(sizeof(tree));
root->value=rootvalue;
root->left=NULL;
root->right=NULL;

while(y!=4)
{
printf("Enter your choice\n");
printf("1.Insert\n2.Display\n3.Search\n4.Exit\n");
scanf("%d",&y);
switch(y)
{
case 1:
printf("Enter the element value\n");
scanf("%d",&x);
insert(root,x);
break;
case 2:
display(root);
break;
case 3:
printf("Which number are u looking for\n");
scanf("%d",&z);
search(root,z);
break;
}
}
}

void insert(tree *node,int x)
{
tree *new;
if(x>node->value)
{
    if(node->right==NULL)
    {
    new=(tree *)malloc(sizeof(tree));
    new->value=x;
    new->left=NULL;
    new->right=NULL;
    node->right=new;
    }
    else
    {
    insert(node->right,x);
    }
}

else
if(x<node->value)
{
    if(node->left==NULL)
    {
    new=(tree *)malloc(sizeof(node));
    new->value=x;
    new->left=NULL;
    new->right=NULL;
    node->left=new;
    }
    else
    {
    insert(node->left,x);
    }
}
else
{
printf("Enter discrete number\n");
}
}

// In-order traversal
void display(tree *node)
{
if(node!=NULL)
{
display(node->left);
printf("%d\t",node->value);
display(node->right);
}
}

// O(logn) approach
void search(tree *node,int x)
{
if(node->value==x)
{
printf("Yes,%d is present in BST\n",x);
}
else if((x>node->value) && (node->right!=NULL))
{
search(node->right,x);
}
else if((x<node->value) && (node->left!=NULL))
{
search(node->left,x);
}
else
{
printf("%d Not found\n ",x);
}
}


Time Complexity 
  1. Insertion - O(logn)
  2. Search - O(logn)

No comments:

Post a Comment