Issues related to Desi Cow,Agriculture and Environment in India.

Issues related to Desi Cow,Agriculture and Environment in India.

Presentation on Generalised Quantum Secret Sharing a paper by Sudhir Kumar Singh and R.Srikant

Click on the below link to view my Presentation

Presentation

Quantum Computing Postulates used in Quantum Cryptography and Logic Gates Explained.

To Download my report made on above topic click on the link below.

 

Click To View PDF

C program to construct tree using Id3 algorithm.

GitHub : https://github.com/ShivamSaluja/ML-ID3

 

Link to golf database.

Steps to run the code :
1] Save the data file with name golf.data .
2] Save the below code in a C file and name it id3.c
3] Save both database and c code in the same folder.
4] Run the code and tree will be printed as output.

C Program for Id3 :

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


struct node
{
    int data;
    char name[15];
    struct node *next;
};

struct deci_tree
{
    int data;
    int datasetCol;
    double ent;
    int pos;
    int childno;
    int ivalue;
    struct deci_tree *c[50];
}root;


struct node  *createnewnode(struct node *head,char name[15],int d)
{
    struct node *ptr=head,*temp;

    temp=(struct node *)malloc(sizeof(struct node));
    strcpy(temp->name,name);
    temp->data=d;
    temp->next=NULL;
    if(head==NULL)
        head=temp;

    else
    {
        while(ptr->next!=NULL)
        {
            ptr=ptr->next;
        }
        ptr->next=temp;
    }

    return head;
}


int search(struct node *head,char name[15])
{
    struct node *temp=head;
    while(temp!=NULL)
    {
        if(strcmp(temp->name,name)==0)
            return temp->data;
        else
            temp=temp->next;
    }

    if(temp==NULL)
        return 3;
    else
return 0;
}


void display(struct node *head)// function to display the mapping of name and integer
{
    struct node *temp=head;

    if(temp==NULL)
        return;
    while(temp!=NULL)
    {
        printf("%d->%s\n",temp->data,temp->name);
        temp=temp->next;
    }
}


double entropy(int a[500][500],int obj,int attr,int attrpos,int val,struct deci_tree *head1)
{
    int x,k;
    x = a[1][attr-1];
    struct deci_tree *temp;
    temp = head1;
    int i;
    double b,c,d,total= 1.0;
    double count1 = 0,count2 = 0 ;

    if(temp == NULL && attrpos == attr-1)
    {
        for(i=1;i<obj;i++)
        {
            if(a[i][attrpos]==x)
                count1++;
            else
                count2++;
        }
    }

    if(temp==NULL  && attrpos != attr-1)
    {

        for(i=1; i<obj; i++)
        {
            if(a[i][attrpos] == val)
            {
                if(a[i][attr-1] == x)    
                    count1 = count1 + 1;

                else
                    count2 = count2 + 1;
            }
        }
    }
    b = count1/(count1+count2);
    c = count2/(count1+count2);


    if(count1 == 0.000000 || count2 == 0.000000)
        d = 0 ;
    else
        d =  ((count1+count2)/(obj-1)) *(-(b*(log(b)/log(2)) + c*(log(c)/log(2))));

    return d;
}

void findk(int a[500][500], int b[50][50],int obj,int attr){

    int i,j,k,count = 1;
    int flag  =0 ;

 
    for(k = 0; k < attr;k++)
    {
        b[k][1] = a[1][k];
        i = 1;
        while(i < obj){
            for(j = 1 ; j < count; j++){
                if(a[i][k] == b[k][j])
                {
                    flag = 1;  
                }
            }
            if(flag  == 0 ){
                b[k][count] = a[i][k];
                count++;
            }
            flag =0;
            i++;

        }
        b[k][0] = count-1;

        count = 1;
    }
}  


int findmax(double *gain1 , int attr){

    int i = 0 ;
    int max1 = 0 ;
    double max;
    max = gain1[0];
    for(i = 1; i <= attr; i++ ){
        if(gain1[i] > max){
            max1 = i;
            max = gain1[i];
        }
    }
    return max1;
}


double findsum(double col1[50],int len){

    int i,j;
    double sum =0;  
    for(i = 0;i < len ;i ++){
        sum =sum +col1[i];
    }      
    return sum;
}


int* funcModiA(int a[500][500],int modifiedA[500][500],int max1,int attr,int obj,int val,int dim[2]){

    int i,j,k;  
    int row = 0,col =0,temp=0,col2=0;
 
    for(j = 0 ; j < obj ; j++){
        if(j == 0 ){
            for(k =0 ; k < attr ; ){
                if(k == max1 ){
                    k++;
                }
                else{
                    modifiedA[row][col2] = a[j][k];
                    k++;
                    col2++;
                }  
            }
            row++;
        }
        else{
            if(a[j][max1] == val){
                for(i = 0 ; i < attr ;){
                    if(i == max1){
                        i++;
                    }  
                    else {              
                        modifiedA[row][col] = a[j][i];
                        temp = col++;
                        i++;
                    }
                }  
                col = 0;      
                row++;
            }
        }      
    }
    dim[0] = row;
    dim[1] = attr-1;  
    return dim;
}

struct deci_tree* infoGainRecursive(int Z[500][500],int b[50][50],struct deci_tree * parent,double entr,int max1,int attr,int obj,int flag,int initattr,int a[500][500]){

    int i =0 ;
    int j;
    int modifiedA[500][500],modifiedB[50][50];
    double col3[50],col1[50],entr1[50],entropy1[50][50],gain1[50];
    int dim[2];
    if(flag == 1){
        flag = 0;
        parent->ent = entr;
        parent->data = 0;
        for(i = 0 ; i  < attr ;i++){
            for(j = 0 ; j <  obj;j++){
                modifiedA[j][i] = Z[j][i];
            }
        }          
        findk(modifiedA,modifiedB,obj,attr);

 
    }
 
    else{

          for(i = 0 ; i  < attr ;i++){

            for(j = 0 ; j <  obj;j++){
                modifiedA[j][i] = Z[j][i];

            }
        }

        funcModiA(modifiedA,modifiedA,max1,attr,obj,parent->pos,dim);
        obj = dim[0];
        attr = dim[1];
        parent->ent = entropy(modifiedA,obj,attr,i,modifiedB[i][j],NULL);
        if(parent->ent == 0 ){
             int sd =  parent->data ;
             parent->data = modifiedA[1][attr-1];
             parent->datasetCol = attr-1;
             parent->childno = 0;      
             printf("\n\tnode %d is terminated with row value %d ,  child of %d i posotion value %d\n",parent->data , parent->pos ,sd,parent->ivalue);
             return 0;
        }
        else{
            findk(modifiedA,modifiedB,obj,attr);      
        }  
    }

    for(i= 0; i < attr-1 ; i++){
        for(j= 1 ; j <= modifiedB[i][0]; j++){  
            col3[j-1] = entropy(modifiedA,obj,attr,i,modifiedB[i][j],NULL);
     
        }
        entr1[i] =  findsum(col3,modifiedB[i][0]);
        gain1[i] =  parent->ent  - entr1[i];
    }

    int temp = max1;
    max1 = findmax(gain1,attr-1);
    parent->data = modifiedA[0][max1];
    parent->childno = modifiedB[max1][0];

    for(i = 0; i <= initattr;i++){
        if(parent->data    == a[0][i]){
            parent->datasetCol = i;
            break;
        }  
    }

    printf("\n\tCurrent node is %d and is child of %d , through  row value %d,i position %d coloum number %d \n", parent->data,Z[0][temp],parent->pos,parent->ivalue,parent->datasetCol);
 
    for(i = 1; i <= modifiedB[max1][0] ;i++) {
        parent->c[i] = (struct deci_tree *)malloc(sizeof(struct deci_tree ));  
        parent->c[i]->pos = modifiedB[max1][i];        
        parent->c[i]->data = modifiedA[0][max1];
        parent->c[i]->ent = parent->ent;
        parent->c[i]->ivalue = i;
        infoGainRecursive(modifiedA,modifiedB,parent->c[i],parent->c[i]->ent,max1,attr,obj,flag,initattr,a);
    }

    return parent;
}

int* get_test_value(int a[500][500],int attr,int obj){
 
    int i,j,flag = 0,*class,temp,counter=1;
    temp = a[1][attr-1];
    class = (int *)malloc(obj*sizeof(int));

    class[1] = temp;

    for(i = 2; i <= obj; i++ ){
        for(j = 1; j <= counter ; j++){
               if(a[i][attr-1] == class[j] ){
                    flag = 1;
                    break;
               }
        }
        if(flag == 0){
            counter++;
            class[counter] = a[i][attr-1];              
        }
        flag = 0;
    }

    class[0]=counter;
        printf("\n");
    return class;
}

int classification(int a[500][500],struct deci_tree *head,int test_data_pos,int *test_value){

    int temp,store,flag=0,class,i;
     
    struct deci_tree *ptr;
    ptr = head;
                                 
    while(flag != 1){  
        temp = a[test_data_pos][ptr->datasetCol];
        for(i =1 ; i <= ptr->childno;i++ ){
                if(ptr->c[i]->pos == temp){
                    ptr = ptr->c[i];

              }  
            }
             for(i = 1; i <= test_value[0] ; i++){
                 if(test_value[i] == ptr->data){
                    class = test_value[i];
                    flag = 1;
                 }                        
                }
    }
    return class;
}


int main(){

    struct node *first = NULL;
    struct deci_tree *head = NULL,*parent = NULL,*temphead = NULL;

    int i,j,k,t;      
    int a[500][500],obj,attr,x,*d,training,test, *test_value,class;
     
    double r,database,error=0,accuracy=0,total;

    FILE *fp;

    char *tok;  
    const char s[2]=",";

    char buff[200];

    fp=fopen("golf.data","r");

    k=4;i=0;

    while(fgets(buff,200,fp)!=NULL)
    {
        j=0;
        tok=strtok(buff,s);
        while(tok != NULL)
        {
            t=search(first,tok);
            if(t!=3)
            {
                a[i][j]=t;
                j++;
            }    
            if(t==3)// this value is understood if it is checked in search method
            {
                first= createnewnode(first,tok,k);
                a[i][j]=k;
                j++;
                k++;
            }
            tok=strtok(NULL,s);
        }

        i++;
        attr=j;
    }
    obj=i;
    display(first);

    fclose(fp);

    d = (int *)malloc(attr * sizeof(int));
    for(k = 0 ; k < attr ; k++){
        d[k] = k;
    }
    for(i=0;i<obj;i++)
    {
        printf("\n");
        for(j=0;j<attr;j++)
        {
            printf("%d\t", a[i][j]);
        }
    }

        training =obj*75/100;
        test=training;
    printf("\nTraining Data\n");
    for(i=0;i<training;i++)
    {
        printf("\n");
        for(j=0;j<attr;j++)
        {
            printf("%d\t", a[i][j]);
        }
    }
        printf("\nTest Data");
    for(i=test;i<obj;i++){
        printf("\n");
        for(j=0;j<attr;j++){
                printf("%d\t",a[i][j]);
        }
    }  


    database =  entropy(a , training,attr, attr-1,0,NULL);
    int flag = 1;
     
    parent =(struct deci_tree *)malloc(sizeof(struct deci_tree));

    head = infoGainRecursive(a,NULL,parent,database,attr,attr,training,flag,attr,a);
    return 0;
}

Golf Database used for ID3

outlook,temperature,humidity,wind,e_tennis
sunny, 85, 85, false, Don't Play
sunny, 80, 90, true, Don't Play
overcast, 83, 78, false, Play
rain, 70, 96, false, Play
rain, 68, 80, false, Play
rain, 65, 70, true, Don't Play
overcast, 64, 65, true, Play
sunny, 72, 95, false, Don't Play
sunny, 69, 70, false, Play
rain, 75, 80, false, Play
sunny, 75, 70, true, Play
overcast, 72, 90, true, Play
overcast, 81, 75, false, Play
rain, 71, 80, true, Don't Play

C Program to find all Relative Prime Numbers toa given number.(less than that number)

#include<stdio.h>

void main(){
        int p,i,j;
        int remainder = 2;
        int divident,divisor;

        printf("Enter Number\n");
        scanf("%d",&p);

        for(i = 2 ; i < p ; i++){

                divident  = p;
                divisor = i;

                while(divisor != 0){

                        remainder = divident % divisor;
                        divident  = divisor;
                        divisor  = remainder;
                }
       
                if(divident  == 1){
                        printf("Relatively Prime Number is : %d \n" ,i);
                }
        }

}

A C program to perform 3 binary Set Operations i.e Union , Intersection and Set Differance.

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

int  insert(int *A, int a,int size){       
    int flag = 0;
    int i;

    for(i = 0; i <= size ; i++){
        if(A[i] == a){
            flag = 1;
            printf("Dulicate not allowed in Set\n");
        }   
    }
   
    if(flag == 0){
        A[size] = a;
        return 1;
    }
    else
        return 0;
}

void  intersection(int *A,int *B,int sizeA,int sizeB){   
    int ni,i,j;
    int sizei=0;
    if(sizeA < sizeB)
        ni = sizeA;
    else   
        ni = sizeB;
    int itr = 0;
    int *intsec = malloc(ni * sizeof(int));
    for(i = 0;i < sizeA;i++){
        for(j = 0;j < sizeB;j++){
            if(A[i] == B[j]){
                intsec[sizei] = A[i];
                sizei++;   
                    continue;           
            }
            itr++;
        }
    }

    printf("\nIntersection Result is\n");
    for(i = 0; i < sizei ; i++)   
        printf("%d \n",intsec[i]);
   
}

void setdifferance(int *A,int *B,int sizeA,int sizeB,int ch){
    int i ,j,ni;
    int flag =0;
    int k = 0;

    if(sizeA > sizeB)
                ni = sizeA;
        else
                ni = sizeB;

    int *setdiff = malloc(ni * sizeof(int));   

    if(ch == 1) {
      for(i = 0 ; i < sizeA ; i++){
        for(j = 0 ; j < sizeB; j++){
            if(A[i] == B[j]){
                flag = 1;
            }   
        }           
        if(flag == 0){
            setdiff[k] = A[i];
            k++;
        }
        flag = 0;   
       }
    }
    if(ch == 2){
      for(i = 0 ; i < sizeB ; i++){
                for(j = 0 ; j < sizeA ; j++){
                        if(B[i] == A[j]){
                                flag = 1;
                        }
        }
               if(flag == 0){
                      setdiff[k] = B[i];
                      k++;
               }
               flag = 0;
      }
    }

    printf("\nSet Differance Result is\n");
   
    if(k == 0)
        printf("NULL\n");
       
        for(i = 0; i < k ; i++)
                printf("%d \n",setdiff[i]);
}

void unionOp(int *A,int *B,int sizeA, int sizeB){
    int size = sizeA + sizeB;
    int *uni = malloc(size * sizeof(int));
    int i,j;
    int k=0;
    int flag =0;
    for(i = 0 ; i < sizeA; i++){
        uni[i] = A[i];   
    }
        for(j = 0 ; j < sizeB ; j++){
        for(i = 0 ; i < sizeA ; i++){
            if(B[j] == A[i]){
                flag =1;
            }
        }
        if(flag == 0){
            k++;
            uni[sizeA+k-1] = B[j];
        }
        flag = 0;
    }

   
    printf("\nUnion Result is\n");
       
    for(i = 0; i < sizeA+k ; i++)
                printf("%d \n",uni[i]);
          
}

void main(){
    int na,nb,a,b,sizeA,sizeB,flag,diffch;
    int ch=1;
    //struct set *s, *B;
    sizeA = 0;
    sizeB = 0;
    printf("Enter number of elements of set 1\n");
    scanf("%d",&na);
    int *A = malloc(na * sizeof(int));
    int *B = malloc(nb * sizeof(int));
    while(sizeA < na){
        printf("\nInsert elements in set 1\n");
        scanf("%d",&a);
        sizeA +=  insert(A,a,sizeA);
    }
   
    printf("\nEnter number of elements of set 2\n");
        scanf("%d",&nb);

    while(sizeB < nb){
        printf("Insert elements in set 2\n");   
        scanf("%d",&b);
        sizeB += insert(B,b,sizeB);
    }

    while(ch){
    printf("\nPress 1 for intersection\n"
        "Press 2 for union\n"
        "Press 3 for set differance\n"
        "Press 0 for exit \n");

    scanf("%d",&ch);

    switch(ch){
        case 1:
            intersection(A,B,sizeA,sizeB);
            break;
        case 2:
            unionOp(A,B,sizeA,sizeB);
            break;       
        case 3:
            printf("\nFor (Set 1 - set2) press 1 "
                "Else press 2\n");
            scanf("%d",&diffch);
            setdifferance(A,B,sizeA,sizeB,diffch);
            break;
        case 0:
            printf("Good-Bye\n");
            break;   
        default:
            printf("Invalid Input\n");   
        }
    }
}

Relativity of time v/s Absolute present (pure consciousness )

Time waits for you. It will forever come back again and again in a recursive loop till you find out the way to come out of it.

The moment you rise above this loop that moment is the moment when time becomes absolute.

 

To know what Vedanta(Indian Vedic Litrature) says about higgs boson watch the below video

To know what Vedanta(Indian Vedic Litrature) says about higgs boson watch the below video:

https://www.youtube.com/watch?v=fXlWqzazAkY

HERE IS ALL YOU NEED TO KNOW ABOUT CRYPTOGRAPHY.

HERE IS ALL YOU NEED TO KNOW ABOUT CRYPTOGRAPHY

CLICK ON THE LINK BELOW :-
https://www.youtube.com/channel/UC1usFRN4LCMcfIV7UjHNuQg/videos

C Program To Implement Bank Token Generation Machine(Using threads and Semaphores)

/*
Problem Description
A bank has three entrances and eight counters. Each entrance has a token issuing machine next to it. A customer enters or exits the bank through any of the entrances. He/she then collects a token and waits for the token number to be 'called' by any counter. The calling of a token is taken to mean that the customer finishes his/her job and exits from the bank.

It must be ensured that:

• Tokens must be issued in strict sequence.
• No token number must be skipped or issued twice.
• Counters should call the tokens in a strict ascending order.
• No token should be skipped or called twice.
• No counter can call a token number that has not been issued at that time.

Write a program that uses multiple threads for the token issuing machines and counters with appropriate synchronisation primitives*/

//Solution

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

#define MAXCUSTOMERS        2000000
#define TOKEN_MACHINES      3
#define SEVICE_COUNTERS     8

int nitems;
int buff[MAXCUSTOMERS];
struct {
  sem_t mutexpro, mutexcon , nstored;  
  int nput;
  int nval;
  int nvalcon;
} shared;

void *prod(void *), *cons(void *);

int main (int argc, char *argv[])
{
     int i, nthreads, countpro[3],countcon[8], totalsum = 0;
     pthread_t tid_prod[TOKEN_MACHINES], tid_cons[SEVICE_COUNTERS];

     if (argc != 2) {
 fprintf(stderr, "Usage: mutexes #maxnumberOfCUSTOMER\n");
 exit(1);
     }

     if ((nitems = atoi (argv[1])) > MAXCUSTOMERS)
 nitems = MAXCUSTOMERS;

     sem_init (&shared.mutexpro, 0, 1);
     sem_init (&shared.mutexcon, 0, 1);
     sem_init (&shared.nstored, 0, 0);

     for (i=0; i<3; i++) {
 countpro[i] = 0;
 pthread_create(&tid_prod[i], NULL, prod, &countpro[i]);
     }
     
     for (i=0; i<8; i++) {      
 countcon[i]=0;
 pthread_create(&tid_cons[i], NULL, cons, &countcon[i]);
     }

     for (i=0; i<3; i++) {
 pthread_join(tid_prod[i], NULL);
  totalsum += countpro[i];
     }
     
     for (i=0; i<8; i++) {
pthread_join(tid_cons[i], NULL);
      printf("\nCustomers served by %d counter are %d\n", i, countcon[i]);
     }

     sem_destroy (&shared.mutexpro);
     sem_destroy (&shared.mutexcon);
     sem_destroy (&shared.nstored);
     exit(0);
}

void *prod(void *arg)
{
     for ( ; ; ) {
 sem_wait (&shared.mutexpro);
 if (shared.nput >= nitems) {
      sem_post (&shared.mutexpro);
      return (NULL);
 }

 buff[shared.nput] = shared.nval;
 printf("The token issued at entrance %d \n",buff[shared.nput]);
 shared.nput++;
 shared.nval++;
 sem_post (&shared.mutexpro); 
 sem_post (&shared.nstored);
 *((int *) arg) += 1;
     }
}

void *cons(void *arg)
{
     int i;
     
     for ( ; ;) {
 sem_wait (&shared.mutexcon);
 if (shared.nvalcon >= nitems) {
      sem_post (&shared.mutexcon);
      return (NULL);
 }
          sem_wait (&shared.nstored);    
          printf("The customer served is %d \n",buff[shared.nvalcon]);
 shared.nvalcon = shared.nvalcon + 1;
 sem_post (&shared.mutexcon);
       *((int *) arg) += 1;
     }     
     return(NULL);

}

Introduction to Socket Programming.

Prerequisites :

Before you start learning socket programming make sure you already have a certain basic knowledge to network such as understand what is IP address, TCP, UDP.

Introduction to Client-Server communication

Server

• passively waits for and responds to clients
• passive socket

Client

• initiates the communication
• must know the address and the port of the server
• active socket

The server and client both are software but not hardware. It means what is happening on the top is there are two different software executed. To be more precise, the server and client are two different processes with different jobs. 

Understand sockets

Imagine a socket as a seaport that allows a ship to unload and gather shipping, whereas socket is the place where a computer gathers and puts data into the internet.

Socket Types

When a socket is created, the program has to specify the address domain and the socket type. Two processes can communicate with each other only if their sockets are of the same type and in the same domain. There are two widely used address domains, the unix domain, in which two processes which share a common file system communicate, and the Internet domain, in which two processes running on any two hosts on the Internet communicate. Each of these has its own address format.


The address of a socket in the Unix domain is a character string which is basically an entry in the file system.


The address of a socket in the Internet domain consists of the Internet address of the host machine (every computer on the Internet has a unique 32 bit address, often referred to as its IP address). In addition, each socket needs a port number on that host. Port numbers are 16 bit unsigned integers. The lower numbers are reserved in Unix for standard services. For example, the port number for the FTP server is 21. It is important that standard services be at the same port on all computers so that clients will know their addresses. However, port numbers above 2000 are generally available.


There are two widely used socket types, stream sockets, and datagram sockets. Stream sockets treat communications as a continuous stream of characters, while datagram sockets have to read entire messages at once. Each uses its own communciations protocol. Stream sockets use TCP (Transmission Control Protocol), which is a reliable, stream oriented protocol, and datagram sockets use UDP (Unix Datagram Protocol), which is unreliable and message oriented.

Sockets - Procedures

Primitives      Meaning

Socket                Create New Communication End Point                      
Bind                    Attach A Local  Address To Socket
Listen                  Announce Willingness to Accept Connections
Accept                Block A Caller until Connection Request Arrives
Connect             Actively Attempt to establish a Connection.
Send                  Send some data over Connection.
Receive              Receive data over the connection
Close                  Close the connection.

The flow chart below shows the interaction between client and server In Case Of Stream(TCP). Every process on the flow chart is needed and it acts a very important roles on network connection.

For Details Refer To Link:

http://www.codeproject.com/Articles/586000/Networking-and-Socket-programming-tutorial-in-C

http://www.csd.uoc.gr/~hy556/material/tutorials/cs556-3rd-tutorial.pdf

For Programming Details Refer:

http://www.cs.rpi.edu/~moorthy/Courses/os98/Pgms/socket.html

Binary Search Tree(Insertion,traversal,deletion)- Input the names of cities and insert them in to tree.Traverse the tree and also delete elements from the tree.

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

struct node{
char city[20];
struct node *left;
struct node *right;
struct node *parent;
};


void display(struct node *);
struct node * delete(struct node *root,char del[20]);

struct node * insert(char city[20],struct node *root){
struct node *temp = (struct node *)malloc(sizeof(struct node));
struct node *prev = (struct node *)malloc(sizeof(struct node));
struct node *new = (struct node *)malloc(sizeof(struct node));
strcpy(new->city,city);
new->left = NULL;
new->right = NULL;
if(root->parent == NULL){
                        //printf("inside root if\n");
                        root = new;
                        new->parent = root;
        }
else{
int right=0;
int left =0;
temp = root;
while(temp != NULL ){
prev = temp;
left = 0;
right = 0;
if(strcmp(temp->city,new->city) < 0){
//printf("insertion in right\n");
temp = temp->right;
right = 1;
}
else{
//printf("insertion in left\n");
temp = temp->left;
left = 1;
}
}
if(right == 1){
//printf("inside right\n");
//printf("parent %s \n",prev->city);
prev->right = new;
new->parent = prev;
right =0;
left = 0;
}
if(left == 1){
//printf("inside left\n");
//printf("parent %s \n",prev->city);
prev->left = new;
new->parent = prev;
right =0;
left =0;
}
}
return root;
}

void display(struct node *current){
if(current !=NULL){
display(current->left);
printf("%s \n",current->city);
display(current->right);
}
}

void main(){
char city[20];
struct node *root = (struct node *)malloc(sizeof(struct node));
root->left = NULL;
root->right = NULL;
root->parent = NULL;
int i;
int num;
char del[20];
int ch=0;
while(1){
printf("press 1 to insert,2 to delete and 3 to exit\n");
scanf("%d",&ch);
switch(ch){
case 1 :
printf("Enter the number of elements you wana insert in tree \n");
scanf("%d",&num);
for(i=0;i<num;i++){
printf("Enter the name of the city\n");
scanf("%s",city);
root = insert( city , root);
//printf("root city is %s\n",root->city);
}
printf("the list is as follows\n");
display(root);
break;
case 2 :
printf("enter the number of elements you wana delete\n");
scanf("%d",&num);
for(i=0;i<num;i++){
printf("Enter the city to be deleated \n");
scanf("%s",del);
root = delete( root , del);
printf("the list is as follows\n");
display(root);
}
break;
case 3 :
exit(0);
break;
default :
printf("invalid input\n");
break;
}
}
}


struct node * delete(struct node *root,char del[20]){
int flag;
int right = 0;
int left = 0 ;
int rt =0;
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp = root;
struct node *prev =(struct node *)malloc(sizeof(struct node));
struct node *temp2 =(struct node *)malloc(sizeof(struct node));
while(temp != NULL){
//printf("current city to be compared is %s\n",temp->city);
//printf("left child is left %s and right child is %s and parent is %s\n",temp->left->city,temp->right->city,temp->parent->city);
if(strcmp(temp->city,del) == 0){
//printf("the city to be deleated is %s right value= %d left value = %d\n",temp->city,right,left);
if(temp == root){
rt = 1;
}
if(temp->right == NULL && temp->left == NULL && (right ==1 || rt == 1)){
if(rt == 1){
printf("tree is empty \n");
rt = 0;
temp->parent = NULL;
free(temp);
}
else{
//printf("the node has no child and is the right child\n");
temp->parent->right = NULL;
temp->parent = NULL;
right = 0;
left  = 0;
free(temp);
}
}
else if(temp->right == NULL && temp->left == NULL && (left == 1 || rt==1)){
if(rt == 1){
printf("TREE IS EMPTY\n");
rt = 0;
temp->parent = NULL;
free(temp);
}
else{
//printf("the node has no child and is the left child\n");
temp->parent->left = NULL;
temp->parent = NULL;
right = 0;
left = 0;
free(temp);
}
}
else if(temp->right == NULL && (left == 1 || rt == 1)){
//printf("the node has left child and is left child to its parent\n");
if(rt == 1){
root =root->left;
root->parent = root;
temp->left = NULL;
temp->right = NULL;
rt = 0;
free(temp);  
}
else{
//printf("the parent of node to be deleted is %s\n",temp->parent->city);
temp->parent->left = temp->left;
//printf("new left child of parent is %s\n",temp->parent->left->city);
//printf("original parent of left child is %s\n",temp->left->parent->city);
temp->left->parent = temp->parent;
//printf("the new parent is %s\n",temp->left->parent->city);
temp->left = NULL;
temp->parent = NULL;
left = 0;
right = 0;
free(temp);
}
}
else if(temp->right == NULL && (right == 1 || rt == 1)){
printf("the node has left child and is right child to its parent\n");
if(rt == 1){
root = root->left;
root->parent = root;
temp->left = NULL;
temp->parent = NULL;
rt =0;
free(temp);
}
else{
//printf("the parent of node to be deleted is %s\n",temp->parent->city);
temp->parent->right = temp->left;
//printf("new right child of parent is %s\n",temp->parent->right->city);
temp->left->parent = temp->parent;
temp->left = NULL;
temp->parent = NULL;
left =0;
right =0;
free(temp);
}
}
else if(temp->left == NULL && (right ==1 || rt == 1)){
//printf("the node has right child and itself is a right child\n");
if(rt == 1){
root = root->right;
root->parent = root;
temp->left = NULL;
temp->parent = NULL;
rt = 0;
free(temp);
}
else{
temp->parent->right = temp->right;
temp->right->parent = temp->parent;
temp->right = NULL;
temp->parent =NULL;
left = 0;
right = 0;
free(temp);
}
}
else if(temp->left == NULL && (left == 1 || rt == 1)){
//printf("the node has right child and itself is left child\n");
if(rt == 1){
root = root->right;
root->parent = root;
temp->left = NULL;
temp->parent = NULL;
rt = 0;
free(temp);
}
else{
temp->parent->left = temp->right;
temp->right->parent = temp->parent;
temp->right = NULL;
temp->parent = NULL;
left = 0;
right = 0;
free(temp);
}
}
else{
//printf("the city to be delated has both left and right child\n");
prev = temp;
temp = temp->right;
printf("the right child of city to be deleated is %s\n",temp->city);
if(temp->left == NULL && (left == 1 || rt == 1)){
if(rt == 1 ){
root = root->right;
                                        root->parent = root;
                                        root->left  = prev->left;
prev->left->parent = root;
prev->left = NULL;
prev->right = NULL;
                                        prev->parent = NULL;
                                        rt = 0;
                                      free(prev);
}
else{
prev->parent->left =prev->right;
prev->right->parent = prev->parent;
prev->left->parent = prev->right;
prev->right->left = prev->left;
prev->parent =NULL;
prev->left = NULL;
prev->right =  NULL;
right = 0;
left = 0;
free(prev);
}
break;
}
if(temp->left == NULL && right == 1){
//printf("the child of city to be deleated has no left child and itself is a right child\n");
                                        prev->parent->right =prev->right;
                                        prev->right->parent = prev->parent;
                                        prev->left->parent = prev->right;
                                        prev->right->left = prev->left;
                                        prev->parent =NULL;
                                        prev->left = NULL;
                                        prev->right =  NULL;
                                        right = 0;
                                        left = 0;
                                        free(prev);
                                        break;
                                }                                                          
else{
temp = temp->left;
}
//printf("before while left child been pionted is %s  and its left child is %s\n",temp->city,temp->left->city);
while(temp->left != NULL){
temp = temp->left;
}
//printf("the child to be replaced with the child to be deleated is %s\n",temp->city);
if(temp->right == NULL && (left == 1 ||rt == 1)){
//printf("the child has no further child and is in the left subtree of del child\n");
if(rt == 1){
root = temp;
rt = 0 ;
                                                temp->parent->left = NULL;
                                                temp->left = prev->left;
                                                temp->right = prev->right;
                                                temp->parent = root;
                                                prev->left->parent = root;
                                                prev->right->parent = root;
                                                prev->left = NULL;
                                                prev->right = NULL;
                                                prev->parent = NULL;
                                                left = 0;
                                                right = 0;
                                                free(prev);

}
else{
temp->parent = prev->parent;
temp->parent->left = NULL;
temp->left = prev->left;
temp->right = prev->right;
temp->parent = prev->parent;
prev->left->parent = temp;
prev->right->parent = temp;
prev->parent->left = temp;
prev->left = NULL;
prev->right = NULL;
prev->parent = NULL;
left = 0;
right = 0;
free(prev);
}
}
else if(temp->right == NULL && right == 1){
//printf("no further children of the child and it is in left right\n ");
temp->parent->left = NULL;
temp->left = prev->left;
temp->right = prev->right;
temp->parent = prev->parent;
prev->left->parent = temp;
prev->right->parent = temp;
prev->parent->right = temp;
prev->left = NULL;
prev->right = NULL;
prev->parent = NULL;
left = 0;
right = 0;
free(prev);
}
else if(temp->right != NULL && (right == 1 || rt == 1)){
//printf("the child has further a right child and is in right subtree of del\n");
if(rt == 1){
root  = temp;
rt = 0;
temp->parent->left = temp->right;
                                        temp->right->parent = temp->parent;
                                        temp->left = prev->left;
                                        temp->right = prev->right;
                                        temp->parent = root;
                                        prev->left->parent = root;
                                        prev->right->parent = root;
                                        prev->left = NULL;
                                        prev->right = NULL;
                                        prev->parent = NULL;
                                        left = 0;
                                        right = 0;
                                        free(prev);
}
else{
temp->parent->left = temp->right;
temp->right->parent = temp->parent;
temp->left = prev->left;
                                        temp->right = prev->right;
                                        temp->parent = prev->parent;
                                        prev->left->parent = temp;
                                        prev->right->parent = temp;
                                        prev->parent->right = temp;
                                        prev->left = NULL;
                                        prev->right = NULL;
                                        prev->parent = NULL;
                                        left = 0;
                                        right = 0;
                                        free(prev);
}
}
else if(temp->right != NULL && left == 1){
                                        //printf("the child has further children and is in left subtree of del\n");
temp->parent->left = temp->right;
                                        temp->right->parent = temp->parent;
                                        temp->left = prev->left;
                                        temp->right = prev->right;
                                        temp->parent = prev->parent;
                                        prev->left->parent = temp;
                                        prev->right->parent = temp;
                                        prev->parent->left = temp;
                                        prev->left = NULL;
                                        prev->right = NULL;
                                        prev->parent = NULL;
                                        left = 0;
                                        right = 0;
                                        free(prev);
                                }
}
return root;
}
else{
if(strcmp(temp->city,del)>0){
temp = temp->left;
left = 1;
right = 0;
rt  = 0;
}
else if(strcmp(temp->city,del)<0){
temp = temp->right;
right =1;
left = 0;
rt = 0;
}
}

}
return root;
}