binary search tree - eliminate duplicates in array

binary search tree is best algorithm in eleminating duplicates in array.

algorithm:
step 1) construct root node with 1st element in array
step 2) scan next element in array say elem and compare with root node of tree. node=tree
 step 3) if elem < node->data   and there is no left node in tree ,
               then insert elem in left node
              else repeat step3 by node = node -> left ;
step 4)  if elem > node->data  and there is no right node in tree ,

               then insert elem in right node

              else repeat step 4 by node=node->right.

 step 5) if elem == node->data , then there is duplicate in array.

the advantage of this algorithm is no need to traverse through all elements in array, duplicate element can be found once we reach it .

the worst case of this algorithm is when duplicate element is at the end of array.

C program for binary search:


#include "stdafx.h"
#include

typedef struct node{
int data;
node *left;
node *right;
}tree;

tree *t1=NULL,*t2=NULL, *t4=NULL, *root=NULL ;
int i=0;
void construct_tree(int *p,int count);
void insert(tree *t,int data);
//void insert_right(tree *t,int data);

int main(int argc, _TCHAR* argv[])
{
 int a[100]; int count=0;
printf("\n enter how many nodes for numericals");
scanf("%d",&count);
printf("\n enter numericals");
for(int i=0;i < count;i++)
scanf("%d",&a[i]);
construct_tree(a,count);
return 0;
}

void construct_tree(int *p,int count)
{
//printf("%d\t",p[i]);
root=new tree();
root->data=p[0];
root->left=NULL;
root->right=NULL;
for(t4=root,i=1;i
insert(t4,p[i]);
} // end func

void insert(tree *temp,int data){
if(data < temp->data ){
if(temp->left == NULL){
tree *t2=new tree();
t2->data=data;
t2->left=NULL;
t2->right=NULL;
temp->left=t2;
}
else
insert(temp->left,data);
}
else if(data > temp->data){
if(temp->right == NULL){
tree *t2=new tree();
t2->data=data;
t2->left=NULL;
t2->right=NULL;
temp->right=t2;
}
else
insert(temp->right,data);
}
else if(data == temp->data )
printf("\n %d duplicate found",data);
     // end else
}