Binary Search Tree Difficulties

Question

As part of an exercise, in my effort to try to learn Programming, i am asked to create a program that uses 1. a structure 2. a doubled linked list 3. A Binary Search Tree

to create a database of customers.. I am ok with adding nodes, to the list and searching. However when trying to delete a customer the program doesnt work as is should be and crashes.. I have tracked down the problem to be to my BST_delete function starting in line 86, because if i don't run this function the program works far better. In more detail i think that i am not updating correcty BST_email_root that should be the most recent node of the Binary tree..

This is driving me crazy! I know that it is not the most elegant code, but i am still trying to learn! Thanks

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

#define MAX_STRING 250

void myflush();

// Defining a customer structure.
struct customer {
    char *name;
    char *address;
    char *email;
};

// A double linked list. The data field points to a customer struct.
struct double_linked_list {
    struct customer *data;
    struct double_linked_list *previous;
    struct double_linked_list *next;
};

// Defining a pointer for the first one of the customers in the double linked list.

struct double_linked_list *customers_head=0;

// A  node for a Binary Search Tree (BST).

struct BST_node {
    struct double_linked_list *data;
    struct BST_node *left;
    struct BST_node *right;
};

// Defining a variable for the root of the BST that is indexed by the email.
struct BST_node *BST_email_root = 0;

// Looking for a node with a specific email in the BST.

struct BST_node *BST_find_customer(struct BST_node *root, char *email) {
if (root==NULL)
    return NULL;
if (strcmp(email,root->data->data->email)==0)
    return root;
else
    {
    if (strcmp(email,root->data->data->email)==-1)
    return BST_find_customer(root->left,email);
    else
        return BST_find_customer(root->right,email);
    }
}

// A procedure to finding a customer according to his email.

void find_customer() {
    char email[MAX_STRING];
    struct double_linked_list *l;
    struct BST_node *b;
    printf("Give the email of the customer (up to %d characters) : ", MAX_STRING-1);
    gets(email);

    b = BST_find_customer(BST_email_root, email);
    if (b==0)
        printf("There is no customer with this email.\n");
    else
    {
        l = b->data;
        printf("Customer found! \n");
        printf("Name    : %s\n", l->data->name);
        printf("Address : %s\n", l->data->address);
        printf("Email   : %s\n", l->data->email);
    }
}

struct BST_node *findMaxNode(struct BST_node *root)
            {
                if(root->right == NULL) return root;
                findMaxNode(root->right);
            }

// Deleting a node in the BST, according to a given email.

// The function returns the (new?) root of the BST, which might have been changed or not.
struct BST_node *BST_delete(struct BST_node *root, char *email)
{

if (root==NULL)
    return root;
struct BST_node *father=NULL;
char which_son;
while (strcmp(email,root->data->data->email)!=0){ //first, finding root and remembering who's root father
if(root==NULL) {
     return root;
} else if (strcmp(email,root->data->data->email) <0){
     father = root;
     root = root->left;
     if(root==NULL)
        return;
     else which_son = 'l';
} else {
     father = root;
     root = root->right;
    if(root==NULL)
        return;
    else which_son = 'r';
}
}
// now you have both the root node, and its father
if ( (root->right == NULL) && (root->left == NULL) ){ //case 1, if it's a leaf
 free(root);

} else if (root->left == NULL) { //case 2
    if (which_son == 'l') {
        father->left = root->right;
    } else {
        father->right = root->right;
    }

} else { //case 3 : here i get the "rightest" son of root's left son
    struct BST_node *replacing_node = root->left;
    while (replacing_node->right != NULL) {
        replacing_node = replacing_node->right;
    } //now replacing_node is a leaf, and can replace root
    if (which_son == 'l') {
        father->left = replacing_node;
        replacing_node->left = root->left;
        replacing_node->right = root->right;
    } else {
        father->right = replacing_node;
        replacing_node->left = root->left;
        replacing_node->right = root->right;
    }
    }
    return root;
}


// This function adds a new node in the Binary Search Tree (BST) rooted by *root,

struct BST_node *new_BST_node(struct BST_node *root, struct double_linked_list *l)
    {
    if (root==NULL)
        {
        root= (struct BST_node *)malloc(sizeof(struct BST_node ));
        if (root==NULL)
            {
            printf("Out of Memory!");
            exit(1);
            }

        root->data=l;
        root->left=NULL;
        root->right=NULL;
        return root;
        }

    if ((strcmp(l->data->email,root->data->data->email))<0)
                root->left =new_BST_node(root->left,l);
    else
        root->right =new_BST_node(root->right,l);


    };


// A procedure to modify the data concerning an existing customer
void modify_customer() {
    char old_email[MAX_STRING];
    char new_email[MAX_STRING];
    char new_name[MAX_STRING];
    char new_address[MAX_STRING];
    char ans;

    struct BST_node *ind;
    struct double_linked_list *l;

    printf("Give the email of the customer you want to modify: ");
    gets(old_email);
    ind = BST_find_customer(BST_email_root, old_email);
    if (ind == 0)
    {
        printf("There is no customer with this email.\n");
        return;
    }

    l = ind->data;  // The node in the double linked list for the customer
    printf("Old name: %s\n", l->data->name);
    printf("Give the new name (up to %d characters, <Enter> if it does not change): ", MAX_STRING - 1);
    gets(new_name);
    if (new_name[0] == 0)
        strcpy(new_name, l->data->name);

    printf("Old address: %s\n", l->data->address);
    printf("Give the new address (up to %d characters, <Enter> if it does not change): ", MAX_STRING - 1);
    gets(new_address);
    if (new_address[0] == 0)
        strcpy(new_address, l->data->address);

    printf("Old email: %s\n", l->data->email);
    printf("Give the new email (up to %d characters, <Enter> if it does not change): ", MAX_STRING-1);
    gets(new_email);
    if (new_email[0] == 0)
        strcpy(new_email, l->data->email);

    if (strcmp(l->data->email, new_email))
    {
        if (BST_find_customer(BST_email_root, new_email))
        {
            printf("New email already exists. Modification aborted.\n");
            return;
        }
    }

    printf("\n\n");
    printf("REPLACE:\n");
    printf("Name    : %s\n", l->data->name);
    printf("Address : %s\n", l->data->address);
    printf("Email   : %s\n", l->data->email);
    printf("WITH:\n");
    printf("Name    : %s\n", new_name);
    printf("Address : %s\n", new_address);
    printf("Email   : %s\n\n", new_email);

    printf("Are you sure? (Y)es/(N)o\n");
    scanf(" %c", &ans);
    myflush();
    if (ans == 'Y' || ans == 'y')
    {
        free(l->data->name);
        l->data->name = strdup(new_name);
        free(l->data->address);
        l->data->address = strdup(new_address);

        if (strcmp(l->data->email, new_email) != 0)
            // Only in case the email has been changed, we have to maintain the BST
        {
            BST_email_root=BST_delete(BST_email_root, l->data->email);
            free(l->data->email);
            l->data->email = strdup(new_email);
            BST_email_root=new_BST_node(BST_email_root, l);
        }
    }
}

//  add a new customer
struct double_linked_list *new_customer()
{
    char name[MAX_STRING], address[MAX_STRING], email[MAX_STRING];
    struct BST_node *b;
    struct double_linked_list *l;
    struct customer *c;

    printf("\nADDING A CUSTOMER\n\n\n");
    printf("Give the name (up to %d characters): ", MAX_STRING-1);
    gets(name);

    printf("Give the address (up to %d characters): ", MAX_STRING - 1);
    gets(address);

    printf("Give the email (up to %d characters): ", MAX_STRING - 1);
    gets(email);

        // check for duplicate email
    b = BST_find_customer(BST_email_root, email);
    if (b)
    {
        printf("Duplicate email. Customer aborted.\n");
        return 0;
    }

    c = (struct customer *) malloc(sizeof(struct customer));
    if (c == 0)
    {
        printf("Not enough memory.\n");
        return 0;
    }

    c->name = strdup(name); // check for memory allocation problem
    if (c->name == 0) return 0;
    c->address = strdup(address);   // check for memory allocation problem
    if (c->address == 0) return 0;
    c->email = strdup(email);   // check for memory allocation problem
    if (c->email == 0) return 0;

    l = (struct double_linked_list*) malloc(sizeof(struct double_linked_list));
    if (l == 0)
    {
        printf("Not enough memory.\n");
        free(c->name);
        free(c->address);
        free(c->email);
        free(c);
        return 0;
    }

    l->data = c;
    l->previous = 0;
    l->next = customers_head;

    if (customers_head)
        customers_head->previous = l;

    customers_head = l;

    BST_email_root = new_BST_node(BST_email_root, l);

    return l;
}

// This function deletes a customer, based on its email
void delete_customer() {
    char email[MAX_STRING];
    struct BST_node *n_del;
    printf("Give the email of the customer you want to delete(up to %d characters) : ", MAX_STRING-1);
    gets(email);

    n_del = BST_find_customer(BST_email_root, email);
    if (n_del==0)
        printf("There is no customer with this email.\n");

    else
    {
    struct double_linked_list *current = n_del->data;
    //struct double_linked_list *temp;
    //struct double_linked_list *prev = customers_head;

    if (current->next==NULL &&current->previous==NULL)
        {
        free(current);
        customers_head=0;
        }

    else if (current->next==NULL) //TA EXOUN ANAPODA??i oxi..Den exw katalaveiNEXT=0 EINAI GIA TO PROTO STOIXEIO pou vazw. An exw mono ena stoixeio ti ginete? prepei na to dw..
        {
        printf("1");
        current->previous->next=NULL;
        free(current);
        }

    else if (current->previous==NULL)
        { printf("2");
            current->next->previous=NULL;   //Apla kane to previous tou proigoumenou apo ton teleytaio pou thes na kaneis na mi deixnei pouthena..
        customers_head=current->next;
        free(current);
        }
    else
       {
        printf("3");
        current->next->previous = current->previous;  //vle ton proigoumeno komvo na deixnei ston epomeno kai ton epomeno ston proigoumeno
        current->previous->next = current->next;      //Ftiakse to customer's head na deixnei sto proigoumeno pou einai pleon to pio prosfato sti lista
       }
    }

    BST_email_root=BST_delete(BST_email_root, email);
}


void displaymenu() {
    printf("\n\n");
    printf("1. New customer\n");
    printf("2. Find customer using email\n");
    printf("3. Modify customer\n");
    printf("4. Delete customer\n");
    printf("0. Exit\n\n");
    printf("Give a choice (0-6) : ");
}

// This function empties the buffer of the standard input (stdin), that is, of the keyboard
void myflush()
{
    char ch;
    while ((ch = getchar()) != '\n' && ch != EOF);
}


// The main function
int main() {
    int choice;
    do {
        displaymenu();
        scanf("%d", &choice);
        myflush();
        switch (choice) {
        case 1:
            new_customer();
            break;
        case 2:
            find_customer();
            break;
        case 3:
            modify_customer();
            break;
        case 4:
            delete_customer();
            break;

        default:
            printf("Wrong selection.\n\n");
        }
    } while (choice != 0);

    return 0;
}

Answer 1

After testing the provided source code and inserting the remark of @StephanLechner, the main problem is that the BST_find_customer() is not able find any nodes due the gap between the BST_find_customer() algorithm and the one used by new_BST_node().

Error 1 - in the BST_find_customer() function, before looking for left or right nodes, explore the root->data (a struct double_linked_list *).

// explore the list from root->data;
struct double_linked_list *ldata = root->data;
while (ldata!=NULL) {
    if (strcmp(email,ldata->data->email)==0) {
        return (root);
    }
    ldata=ldata->next;
}
if (strcmp(email,root->data->data->email)<0) { // ERROR ==-1) {
    return BST_find_customer(root->left,email);
}
else {
    return BST_find_customer(root->right,email);
}

Instead of:

if (strcmp(email,root->data->data->email)==0)
    return root;
else {
    if (strcmp(email,root->data->data->email)==-1)
        return BST_find_customer(root->left,email);
    else
        return BST_find_customer(root->right,email);
}

Error 2 - In the BST_delete() function, check the validity of root before exploring its data.

Add the if-condition (root!=NULL) in the while-loop to prevent end-of-tree.

The function shall return a value return (NULL); instead of return;, otherwise undefined behavior.

while ((root!=NULL) && (strcmp(email,root->data->data->email)!=0)){ 
    if (strcmp(email,root->data->data->email) < 0){
         father = root;
         root = root->left;
         which_son = 'l';
    } else {
         father = root;
         root = root->right;
         which_son = 'r';
    }
}
if(root==NULL) {
     return (root);
}

Instead of:

while (strcmp(email,root->data->data->email)!=0) { //first, finding root and remembering who's root father
    if(root==NULL) {
         return root;
    } else if (strcmp(email,root->data->data->email) <0){
         father = root;
         root = root->left;
         if(root==NULL)
            return;
         else which_son = 'l';
    } else {
         father = root;
         root = root->right;
        if(root==NULL)
            return;
        else which_son = 'r';
    }
}

Error 3 - In the delete_customer(), abort the deletion when no customer has the entered email.

n_del = BST_find_customer(BST_email_root, email);
if (n_del==0) {
    printf("There is no customer with this email.\n");
    return;
}
else

Instead of:

n_del = BST_find_customer(BST_email_root, email);
if (n_del==0)
    printf("There is no customer with this email.\n");
    // ABORT HERE
else

Answer 2

Here is my modified version. I think the double_linked_list is not needed. You can directly use customer for BST_node.data. I tested add new customer, find customer, delete customer and all worked as expected. But I didn't test modifying a customer which I think is rather straight forward.

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

#define MAX_STRING 250

void myflush();

// Defining a customer structure.
struct customer {
    char *name;
    char *address;
    char *email;
};

// A double linked list. The data field points to a customer struct.
struct double_linked_list {
    struct customer *data;
    struct double_linked_list *previous;
    struct double_linked_list *next;
};

// Defining a pointer for the first one of the customers in the double linked list.

struct double_linked_list *customers_head=0;

// A  node for a Binary Search Tree (BST).

struct BST_node {
    struct double_linked_list *data;
    struct BST_node *top;
    struct BST_node *left;
    struct BST_node *right;
};

// Defining a variable for the root of the BST that is indexed by the email.
struct BST_node *BST_email_root = 0;

// Looking for a node with a specific email in the BST.

struct BST_node *BST_find_customer(struct BST_node *root, char *email) {
if (root==NULL)
    return NULL;

int rv = strcmp(email,root->data->data->email);

if (rv==0)
    return root;
else
    {
    if (rv<0)
    return BST_find_customer(root->left,email);
    else
        return BST_find_customer(root->right,email);
    }
}

// A procedure to finding a customer according to his email.

void find_customer() {
    char email[MAX_STRING];
    struct double_linked_list *l;
    struct BST_node *b;
    printf("Give the email of the customer (up to %d characters) : ", MAX_STRING-1);
    gets(email);

    b = BST_find_customer(BST_email_root, email);
    if (b==0)
        printf("There is no customer with this email.\n");
    else
    {
        l = b->data;
        printf("Customer found! \n");
        printf("Name    : %s\n", l->data->name);
        printf("Address : %s\n", l->data->address);
        printf("Email   : %s\n", l->data->email);
    }
}

struct BST_node *findMaxNode(struct BST_node *root)
            {
                if(root->right == NULL) return root;
                findMaxNode(root->right);
                return NULL;
            }

// Deleting a node in the BST, according to a given email.

// The function returns the (new?) root of the BST, which might have been changed or not.
struct BST_node *BST_delete(struct BST_node *root, char *email)
    {

    if (root==NULL)
        return root;
    struct BST_node *father=NULL;
    char which_son;
    while (strcmp(email,root->data->data->email)!=0){ //first, finding root and remembering who's root father
    if(root==NULL) {
         return NULL;
    } else if (strcmp(email,root->data->data->email) < 0){
         father = root;
         root = root->left;
         which_son = 'l';
    } else {
         father = root;
         root = root->right;
         which_son = 'r';
    }
}
    // now you have both the root node, and its father
    if ( (root->right == NULL) && (root->left == NULL) ){ //case 1, if it's a leaf
     free(root);

    } else if (root->left == NULL) { //case 2
        if (which_son == 'l') {
            father->left = root->right;
        } else {
            father->right = root->right;
        }

    } else { //case 3 : here i get the "rightest" son of root's left son
        struct BST_node *replacing_node = root->left;
        while (replacing_node->right != NULL) {
            replacing_node = replacing_node->right;
        } //now replacing_node is a leaf, and can replace root
        if (which_son == 'l') {
            father->left = replacing_node;
            replacing_node->left = root->left;
            replacing_node->right = root->right;
        } else {
            father->right = replacing_node;
            replacing_node->left = root->left;
            replacing_node->right = root->right;
        }
        }
        return root;
    }


// This function adds a new node in the Binary Search Tree (BST) rooted by *root,

void new_BST_node(struct BST_node *root, struct double_linked_list *l)
{
    if ((strcmp(l->data->email,root->data->data->email))<0)
    {
        if(root->left == NULL)
        {
            root->left = (struct BST_node *)malloc(sizeof(struct BST_node ));
            root->left->data = l;
            root->left->top = root;
            root->left->left = NULL;
            root->left->right = NULL;
        }
        else
        {
            new_BST_node(root->left,l);
        }
    }
    else
    {
        if(root->right == NULL)
        {
            root->right = (struct BST_node *)malloc(sizeof(struct BST_node ));
            root->right->data = l;
            root->right->top = root;
            root->right->left = NULL;
            root->right->right = NULL;
        }
        else
        {
            new_BST_node(root->right,l);
        }
    }
}


// A procedure to modify the data concerning an existing customer
void modify_customer() {
    char old_email[MAX_STRING];
    char new_email[MAX_STRING];
    char new_name[MAX_STRING];
    char new_address[MAX_STRING];
    char ans;

    struct BST_node *ind;
    struct double_linked_list *l;

    printf("Give the email of the customer you want to modify: ");
    gets(old_email);
    ind = BST_find_customer(BST_email_root, old_email);
    if (ind == 0)
    {
        printf("There is no customer with this email.\n");
        return;
    }

    l = ind->data;  // The node in the double linked list for the customer
    printf("Old name: %s\n", l->data->name);
    printf("Give the new name (up to %d characters, <Enter> if it does not change): ", MAX_STRING - 1);
    gets(new_name);
    if (new_name[0] == 0)
        strcpy(new_name, l->data->name);

    printf("Old address: %s\n", l->data->address);
    printf("Give the new address (up to %d characters, <Enter> if it does not change): ", MAX_STRING - 1);
    gets(new_address);
    if (new_address[0] == 0)
        strcpy(new_address, l->data->address);

    printf("Old email: %s\n", l->data->email);
    printf("Give the new email (up to %d characters, <Enter> if it does not change): ", MAX_STRING-1);
    gets(new_email);
    if (new_email[0] == 0)
        strcpy(new_email, l->data->email);

    if (strcmp(l->data->email, new_email))
    {
        if (BST_find_customer(BST_email_root, new_email))
        {
            printf("New email already exists. Modification aborted.\n");
            return;
        }
    }

    printf("\n\n");
    printf("REPLACE:\n");
    printf("Name    : %s\n", l->data->name);
    printf("Address : %s\n", l->data->address);
    printf("Email   : %s\n", l->data->email);
    printf("WITH:\n");
    printf("Name    : %s\n", new_name);
    printf("Address : %s\n", new_address);
    printf("Email   : %s\n\n", new_email);

    printf("Are you sure? (Y)es/(N)o\n");
    scanf(" %c", &ans);
    myflush();
    if (ans == 'Y' || ans == 'y')
    {
        free(l->data->name);
        l->data->name = strdup(new_name);
        free(l->data->address);
        l->data->address = strdup(new_address);

        if (strcmp(l->data->email, new_email) != 0)
            // Only in case the email has been changed, we have to maintain the BST
        {
            BST_email_root=BST_delete(BST_email_root, l->data->email);
            free(l->data->email);
            l->data->email = strdup(new_email);
            new_BST_node(BST_email_root, l);
        }
    }
}

//  add a new customer
struct double_linked_list *new_customer()
{
    char name[MAX_STRING], address[MAX_STRING], email[MAX_STRING];
    struct BST_node *b;
    struct double_linked_list *l;
    struct customer *c;

    printf("\nADDING A CUSTOMER\n\n\n");
    printf("Give the name (up to %d characters): ", MAX_STRING-1);
    gets(name);

    printf("Give the address (up to %d characters): ", MAX_STRING - 1);
    gets(address);

    printf("Give the email (up to %d characters): ", MAX_STRING - 1);
    gets(email);

        // check for duplicate email
    b = BST_find_customer(BST_email_root, email);
    if (b)
    {
        printf("Duplicate email. Customer aborted.\n");
        return 0;
    }

    c = (struct customer *) malloc(sizeof(struct customer));
    if (c == 0)
    {
        printf("Not enough memory.\n");
        return 0;
    }

    c->name = strdup(name); // check for memory allocation problem
    if (c->name == 0) return 0;
    c->address = strdup(address);   // check for memory allocation problem
    if (c->address == 0) return 0;
    c->email = strdup(email);   // check for memory allocation problem
    if (c->email == 0) return 0;

    l = (struct double_linked_list*) malloc(sizeof(struct double_linked_list));
    if (l == 0)
    {
        printf("Not enough memory.\n");
        free(c->name);
        free(c->address);
        free(c->email);
        free(c);
        return 0;
    }

    l->data = c;
    l->previous = 0;
    l->next = customers_head;

    if (customers_head)
        customers_head->previous = l;

    customers_head = l;

    if (BST_email_root==NULL)
    {
        BST_email_root = (struct BST_node *)malloc(sizeof(struct BST_node ));

        BST_email_root->data = l;
        BST_email_root->top = NULL;
        BST_email_root->left = NULL;
        BST_email_root->right = NULL;
    }
    else
    {
      new_BST_node(BST_email_root, l);
    }

    return l;
}

void print_customers(struct BST_node *node)
{
    if(node == NULL)
    {
        printf("No customers yet\n");
    }
    else if(node->left)
    {
        print_customers(node->left);
        printf("%s %s %s\n", node->data->data->name,
                             node->data->data->address,
                             node->data->data->email);
        if(node->right)
        {
            print_customers(node->right);
        }
    }
    else if(node->right)
    {
        printf("%s %s %s\n", node->data->data->name,
                             node->data->data->address,
                             node->data->data->email);
        print_customers(node->right);
    }
    else
    {
        printf("%s %s %s\n", node->data->data->name,
                             node->data->data->address,
                             node->data->data->email);
    }
}

// This function deletes a customer, based on its email
void delete_customer() {
    char email[MAX_STRING];
    struct BST_node *n_del;
    printf("Give the email of the customer you want to delete(up to %d characters) : ", MAX_STRING-1);
    gets(email);

    n_del = BST_find_customer(BST_email_root, email);
    if (n_del==0)
        printf("There is no customer with this email.\n");

    else
    {
        if(n_del->left && n_del->right)
        {
           if(n_del->top->left == n_del)
           {
                n_del->top->left = n_del->left;
           }
           else
           {
                n_del->top->right = n_del->left;
           }

           struct BST_node *node = n_del->left;
           while(node->right)
           {
              node = node->right;
           }
           node->right = n_del->right;
        }
        else if(n_del->left)
        {
           if(n_del->top->left == n_del)
           {
               n_del->top->left = n_del->left;
           }
           else  // must be right node
           {
               n_del->top->right = n_del->left; 
           }
        }
        else if(n_del->right)
        {
           if(n_del->top->left == n_del)
           {
               n_del->top->left = n_del->right;
           }
           else  // must be right node
           {
               n_del->top->right = n_del->right; 
           }
        }
        else {   /* a leaf */
           if(n_del->top->left == n_del)
           {
               n_del->top->left = NULL; 
           }
           else  // must be right node
           {
               n_del->top->right = NULL; 
           }
        }

        free(n_del->data->data->name);
        free(n_del->data->data->email);
        free(n_del->data->data->address);
        free(n_del->data->data);
        free(n_del->data);
        free(n_del);
    }

}


void displaymenu() {
    printf("\n\n");
    printf("1. New customer\n");
    printf("2. Find customer using email\n");
    printf("3. Modify customer\n");
    printf("4. Delete customer\n");
    printf("5. List customers\n");
    printf("0. Exit\n\n");
    printf("Give a choice (0-5) : ");
}

// This function empties the buffer of the standard input (stdin), that is, of the keyboard
void myflush()
{
    char ch;
    while ((ch = getchar()) != '\n' && ch != EOF);
}


// The main function
int main() {
    int choice;
    do {
        displaymenu();
        scanf("%d", &choice);
        myflush();
        switch (choice) {
        case 1:
            new_customer();
            break;
        case 2:
            find_customer();
            break;
        case 3:
            modify_customer();
            break;
        case 4:
            delete_customer();
            break;
        case 5:
            print_customers(BST_email_root);
            break;

        default:
            printf("Wrong selection.\n\n");
        }
    } while (choice != 0);

    return 0;
}

Answer 3

Without diving to deep into your code, there's one thing that I saw immediately. Your statement

...  if (strcmp(email,root->data->data->email) == -1) {

assumes that if the one is smaller than the other, the return value is exactly -1. The return value of strcmp in this case is, however, just guaranteed to be < 0, not exactly -1 (cf. strcmp reference).

Hence, it is likely that, while searching for the "father", you do not find the node you are looking for...