C program for Binary Search Tree with non duplicate values

Q. Write C language based code to create and operate on ADT : Binary Search Tree with unique positive integer values as Key Vaues:

(1). Create a BST with a single node as its Root Node;

(2). Add a node with a given Key Value (give error message, if Key Value already exists, else add a node); 

(3). Given a Key Value, delete a node if it exists; else give error message that the Key Value does not exist; 

(4). Perform search for a given Key Value; if it exists, output " Element Found", else output "Doesn't Exist in the tree";

(5). Perform In-order, Pre-order, Post-order traversal of a given BST and print Key Values in a row, separated by vertical bars; 

".C" file is available in downloadable format at :

https://drive.google.com/file/d/0ByF0OId1bLx6TFNUR0xnZE5za0U/view

(Open the link and click on the download arrow on the top right to download the file.)

Given below is the code for "C program for BST- Binary Search Tree with non duplicate values" :

-----------------------------------------------------------------------------------

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

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



node* create (node*); 
void insert (node*, node*);
node* search (node*, int);
node* del (node*, int);
node* preorder (node*);
node* inorder (node*);
node* postorder (node*);

node* create (node* root)
{
int no,ele,i=0;
node* n=NULL;
node *key;

printf("\nNumber of entries:\t");
scanf("%d", &no);

while (i<no)
{
printf("\n----INSERT----");
printf("\nEnter data:\t");
scanf("%d", &ele);
if (ele> 0)
{
key= search(root, ele);
if (key==NULL)
{
n=(node*)malloc(sizeof(node));
n->info = ele;
n->left=NULL; 
n->right=NULL;

if(root==NULL)
{
printf("\nIt's the first element of the tree.");
root=n;
}
else
{
insert(n, root);
}
i++;
}
else 
printf("The node data: %d already exists in the tree.",ele);
}
else printf("\nOnly Positive integers are allowed");
}
return root;
}


void insert (node* nw, node* root)
{
node *p;
node *q;
p=root; q=root;


while(q!=NULL)
{
p=q;

if(nw->info>q->info)
q=q->right;

else
q=q->left;
}

if(p->info > nw->info)
{
p->left = nw;
}
else
{
p->right = nw;
}
}


node* search(node* root, int ele)
{
node *q;
q=root;

while((q!=NULL)&&(q->info!=ele))
{
if(q->info>ele)
q=q->left;
else
q=q->right;
}
return q;
}


node* del(node* root, int ele)
{
node *temp, *r;
    if (root == NULL) return root;

    if (ele < root->info)
        root->left = del(root->left, ele);

    else if (ele > root->info)
        root->right = del(root->right, ele);

    else
    {
        if (root->left == NULL)
        {
            temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL)
        {
            temp = root->left;
            free(root);
            return temp;
        }

  r=root->right;
  while(r->left!=NULL)
  r=r->left;
 
        temp = r;
        
        root->info = temp->info;

        root->right = del(root->right, temp->info);
    }
    return root;
}

node* preorder (node* q)
{

if(q!=NULL)
{
printf("  |  %d  |  ", q->info);
q->left = preorder(q->left);
q->right = preorder(q->right);
}
return q;
}


node* inorder (node* q)
{

if(q!=NULL)
{
q->left=inorder(q->left);
printf("  |  %d  |  ", q->info);
q->right=inorder(q->right);
}
return q;
}  

node* postorder (node* q)
{

if(q!=NULL)
{
q->left=postorder(q->left);
q->right=postorder(q->right);
printf("  |  %d  |  ", q->info);
}
return q;
}  

void main()
{
node *root=NULL, *q, *exist_or_not;
int choice, val, check=0, ele;


while(1)
{
printf("\n\n\n1. Create\n2. Search\n3. Delete a node.\n4. Preorder Traversal\n5. Inorder Traversal\n6. Postorder Traversal.\n7. Exit program.\n\nEnter your choice:\t");
scanf("%d", &choice);

switch(choice)
{
case 1: root=create(root); check=1; printf("\n\nCREATED"); break;

case 2: printf("Enter value to be searched:\t"); scanf("%d", &ele); q= search(root, ele); 
if(q==NULL) 
{
printf("\n%d doesn't exist in the tree.", ele);
}
else 
{
printf("\n%d found",q->info);
} break;

case 3: printf("Enter value to be deleted:\t"); 
scanf("%d", &val); exist_or_not= search(root, val); 
if(exist_or_not==NULL) 
printf("\nERROR: The value doesnot exist"); 
else 
root = del(root, val); break;


case 4: if(check) 
{   
preorder(root);
}
else 
printf("\nNo data stored yet, first create the tree."); break;


case 5: if(check) 
{ 
inorder(root);
} 
else 
printf("\nNo data stored yet, first create the tree."); break;


case 6: if(check)
{ 
 postorder(root);
 } 
 else 
 printf("\nNo data stored yet, first create the tree."); break;


       case 7: if(root==NULL) 
        printf("\nExiting with empty tree\n\n"); 
        else 
        {
        root->right=NULL; root->left=NULL; 
        free(root); 
        printf("\nFREED ROOT\n\n");
        } exit(0);

default: printf("\n\nHey!! Choose an option from the choices mentioned!!\n And stop testing my program!!");
}


}

}

-----------------------------------------------------------------------------------

C program for creation of Binary Search Tree with Preorder, Postorder and Inorder Traversals

".C" file is available in downloadable format at :

https://drive.google.com/file/d/0ByF0OId1bLx6ZHdHNFJaVGJ2R1E/view

(Open the link and click on the download arrow on the top right to download the file.)

Given Below is the code for creation of Binary Search Tree with Preorder, Postorder and Inorder Traversals :

---------------------------------------------------------------------------------

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

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



node* create (node*); 
void insert (node*, node*);
node* search (node*);
void display (node*);
node* del (node*, int);
node* preorder (node*);
node* inorder (node*);
node* postorder (node*);

node* create (node* root)
{

int no,ele,i;
node* n=NULL;

printf("\nNumber of entries:\t");
scanf("%d", &no);

for(i=0; i<no; i++)
{
printf("\n-------INSERT-------");
printf("\nEnter data:\t");
scanf("%d", &ele);

n=(node*)malloc(sizeof(node));
n->info = ele;
n->left=NULL; 
n->right=NULL;

if(root==NULL)
{
printf("\nIt's the first element of the tree.");
root=n;
}
else
{
insert(n, root);
}
}

printf("\n\nCREATED"); 

return root;
}


void insert (node* nw, node* root)
{
node *p;
node *q;
p=root; q=root;


while(q!=NULL)
{
p=q;

if(nw->info>q->info)
q=q->right;

else
q=q->left;
}

if(p->info > nw->info)
{
p->left = nw;
}
else
{
p->right = nw;
}
printf("\nInserted");
}


void display (node* root)
{

node *disp;
printf("\nDisplay Function.");

if(root!=NULL)
{
printf("\nLEFT:\t");
for(disp=root->left; disp!=NULL ; disp=disp->left)
printf(" %d ", disp->info);

printf("\nROOT:\t %d",root->info);

printf("\nRIGHT:\t");
for(disp=root->right; disp!=NULL ; disp=disp->right)
printf(" %d ", disp->info);
}

else
return;
printf("\n\n");
}


node* search(node* root)
{
node *q;
int ele;
q=root;

printf("Enter value to be searched:\t");
scanf("%d", &ele);

while((q!=NULL)&&(q->info!=ele))
{
if(q->info>ele)
q=q->left;
else
q=q->right;
}
printf("\nSearch Complete");
if(q==NULL) 
{
printf("\n%d doesn't exist in the tree.", ele);
}
else 
{
printf("\n%d found",q->info);
}
return q;
}


node* del(node* root, int ele)
{
node *temp, *r;
    if (root == NULL) return root;

    if (ele < root->info)
        root->left = del(root->left, ele);

    else if (ele > root->info)
        root->right = del(root->right, ele);

    else
    {
        if (root->left == NULL)
        {
            temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL)
        {
            temp = root->left;
            free(root);
            return temp;
        }

  r=root->right;
  while(r->left!=NULL)
  r=r->left;
 
        temp = r;
        
        root->info = temp->info;

        root->right = del(root->right, temp->info);
    }
    return root;
}

node* preorder (node* root)
{
node* q;
q=root;

if(q!=NULL)
{
printf("  |  %d  |  ", q->info);
q->left = preorder(q->left);
q->right = preorder(q->right);
}
return q;
}


node* inorder (node* q)
{
if(q!=NULL)
{
q->left=inorder(q->left);
printf("  |  %d  |  ", q->info);
q->right=inorder(q->right);
}
return q;
}  

node* postorder (node* q)
{
if(q!=NULL)
{
q->left=postorder(q->left);
q->right=postorder(q->right);
printf("  |  %d  |  ", q->info);
}
return q;
}  

void main()
{
node *root=NULL, *key;
int choice, val, check=0;


while(1)
{
printf("\n\n\n1. Create\n2. Display\n3. Search\n4. Delete a node.\n5. Preorder Traversal\n6. Inorder Traversal\n7. Postorder Traversal.\n8. Exit program.\n\nEnter your choice:\t");
scanf("%d", &choice);

switch(choice)

{
case 1: root=create(root); check=1; break;
case 2: if(check) display(root); else printf("\nNo data stored yet, first create the tree."); break;
case 3: key = search(root); break;
case 4: printf("Enter value to be deleted:\t"); scanf("%d", &val); root = del(root, val); printf("\nDeleted"); break;
case 5: preorder(root); break;
case 6: root=inorder(root); break;
case 7: root=postorder(root); break;
       case 8: if(root==NULL) printf("\nExiting with empty tree\n\n"); else { root->right=NULL; root->left=NULL; free(root); printf("\nFREED ROOT\n\n");} exit(0);


default: printf("\n\nHey!! Choose an option from the choices mentioned!!\n And stop testing my program!!");
}


}

}

---------------------------------------------------------------------------------