December 7, 2022

A Binary Search is such a Binary Tree in which the info field of any of the nodes to the left of a particular node nd will be < that of nd and of those to the right of nd will be >= nd. The in-order traversal of such a tree will give the sorted form of the original file.

Below is a simple implementation of Binary Search in C to find duplicates in a file. I have included full code for your ease, sample test scenario, Binary Tree Traversal and output. As a tip and food for thought to the students .. implement and include intrav(PTREE) to the last of main() to implement a Binary Tree Sort process!

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

struct nodetype{
                int info;
                struct nodetype * left;
                struct nodetype * right;
typedef struct nodetype * NODEPTR;


      NODEPTR maketree(int);
      void setleft(NODEPTR p, int);
      void setright(NODEPTR p, int);
      NODEPTR p,q,PTREE, int num;

      printf("Enter original file of integers>");
      /*scans first number*/

      PTREE = maketree(num); /*make num the root node*/

      while(scanf("%d", &num) != EOF){
           p = q = PTREE; /*p,q always initialized to root node for checking*/

           while(q != NULL){
               p = q;
               if(num < p->info)
                   q = p->left;
                   q = p->right;

           if(num < p->info)
                if(num == p->info)
                    printf("\n%d is a duplicate",num);

NODEPTR maketree(int x){
              NODEPTR getnode (void); NODEPTR p;
              p = getnode();
              p->info = x;
              p->left = p->right = NULL;
              p->father = NULL;

NODEPTR getnode(void){              
              return((NODEPTR) malloc(size of struct nodetype));

void setright(NODEPTR p, int x){
              NODEPTR maketree(int);
              if(p == NULL)
                    printf("\nVoid insertion\n");
              elseif(p->right != NULL)
                    printf("\nInvalid insertion\n");
                    p->right = maketree(x);

void setleft(NODEPTR p, int x){
              NODEPTR maketree(int);
              if(p == NULL)
                    printf("\nVoid insertion\n");
              elseif(p->left!= NULL)
                    printf("\nInvalid insertion\n");
                    p->left= maketree(x);

/*END Program Binary Search*/

Sample Input: 

Enter original file of integers>12 13 12 10 9 6 13 10

Binary Tree formed:
                    /   \
                  10    13
                 /  \   /  \
                9   10  12  13
Inorder Tree Traversal: 
              6 9 10 10 12 12 13 13

      10 is a duplicate
      12 is a duplicate
      13 is a duplicate