final program

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

typedef struct Data {
    int id;
    char name[40];
}Data;

typedef struct Node{
    Data data;
    struct Node *left, *right;
}Node;

typedef Node Tree;


// FUNCTION TO GET DATA OF NODE
// #DATA
int data(Node *node){
    return node->data.id;
}
// FUNCTION TO GET DATA OF NODE

// START OF QUEUE STUFF
typedef struct qNode{
    Node* data;
    struct qNode *next;
}qNode;

typedef struct Queue{
    qNode *head,*tail;
    int numberOfElements;
}Queue;

void reset(Queue *q){ q->head = q->tail = NULL; q->numberOfElements=0; }
int isEmpty(Queue *q) { return !q->head; }
void push(Queue *q,Node* val) {
    qNode *node = (qNode*) malloc(sizeof(qNode));
    node->data = val;
    node->next = NULL;
    if(!q->head)
        q->tail = node;
    else
        q->head->next = node;
    q->head = node;
    q->numberOfElements++;
}

Node* pop(Queue *q) {
    if(!isEmpty(q)) {
        if(!q->tail)
            return NULL;
        else{
            Node* x = q->tail->data;
            if(!q->tail->next)
                reset(q);
            else
                q->tail = q->tail->next;
            q->numberOfElements--;
            return x;
        }
    }
    return NULL;
}

void empty(Queue *q){
    while(!isEmpty(q))
        pop(q);
}

Node* getFirst(Queue q){
    return pop(&q);
}

void display(Queue q){
    while(!isEmpty(&q)) {
        Node * node = pop(&q);
        printf("Name: %-20s,ID: %-4d,%p: \n",node->data.name,node->data.id,node );
    }
}

int count(Queue *q) { return q->numberOfElements;}
// END   OF QUEUE STUFF

Node * newNode(int id,char *name){
    Node* node = (Node*) malloc(sizeof(Node));
    node->data.id = id;
    strcpy(node->data.name, name);
    node->left = node->right = NULL;
    return node;
}

Node * addRight(Node *root,int id,char *name){
    if(root) {
        Node* new = newNode(id,name);
        root->right = new;
        return new;
    }
    return NULL;
}

Node * addLeft(Node *root,int id,char *name){
    if(root) {
        Node* new = newNode(id,name);
        root->left = new;
        return new;
    }
    return NULL;
}


void strtoupper(char *str){
    int i=0; for(i=0;i<strlen(str);i++) str[i] = toupper(str[i]);
}

// START OF TRAVERSING FUNCTIONS.
// #PRETRAVERS
void preTravers(Tree *root){
    if(root) {
        printf("Name: %-20s, ID: %d\t%p \n",root->data.name, root->data.id,root);
        preTravers(root->left);
        preTravers(root->right);
    }
}

// #POSTTRAVERS
void postTravers(Tree *root){
    if(root) {
        postTravers(root->left);
        postTravers(root->right);
        printf("Name: %-20s, ID: %d\t%p \n",root->data.name, root->data.id,root);
    }
}

// #INTRAVERS
void inTravers(Tree *root){
    if(root) {
        inTravers(root->left);
        printf("Name: %-20s, ID: %d\t%p \n",root->data.name, root->data.id,root);
        inTravers(root->right);
    }
}
// END OF TRAVERSING FUNCTIONS.


// START FUNCTION TO CHECK IF THERE ARE ANY CHILD FOR A NODE
// #HASCHILD
int hasChild(Node *node){
    return node->right || node->left;
}
// END   FUNCTION TO CHECK IF THERE ARE ANY CHILD FOR A NODE

// #SAVETOFILE
void saveToFile(Tree *root,FILE *fp){
    if(root) {
        saveToFile(root->left,fp);
        saveToFile(root->right,fp);
        fprintf(fp,"%s,%d",root->data.name,root->data.id); fprintf(fp, "\n");
    }
}

// START SHOWING FUNCTIONS.
// #INSHOW
void inShow(Tree *root,int currentDepth){
    if(root && data(root)!=~(1<<31)) {
        inShow(root->right,currentDepth+1);
        int i; for(i=0;i<currentDepth;i++) printf("\t");
        printf("Name: %s,ID: %3d::%p ",root->data.name,root->data.id,root);
        inShow(root->left,currentDepth+1);
    }else
        printf("\n");
}
// END SHOWING FUNCTIONS.

// START OF INSERTING IN NST FUNCTION.
// #INSERTINID
void insertInId(Tree *root,int id,char *name){
    Node * node = newNode(id,name);
    if(root) {
        if(id < root->data.id ){
            // GO LEFT
            // if there is no left node
            if(!root->left)
                root->left = node;
            else // there is a node insert to it
                insertInId(root->left,id,name);
        }else{
            // GO RIGHT
            // if there is no right node
            if(!root->right)
                root->right = node;
            else
                insertInId(root->right,id,name);
        }
    }
    // return node;
}

// #INSERTINNAME
void insertInName(Tree *root,int id,char *name){
    Node *node = newNode(id,name);
    if(root){
        char fname[strlen(name)], froot[strlen(root->data.name)];
        strcpy(fname,name); strcpy(froot,root->data.name);
        strtoupper(fname); strtoupper(froot);
        if(strcmp(froot,fname) > 0){ // root->data.name is larger than name
            if(!root->left)
                root->left = node;
            else
                insertInName(root->left,id,name);
        }else{
            if(!root->right)
                root->right = node;
            else
                insertInName(root->right,id,name);
        }
    }
}
// END   OF INSERTING IN BST FUNCTION.

// START OF FUNCTION TO GET SMALLEST ELEMENT.
// #GETSMALLEST
Node * getSmallest(Tree *root){
    if(root->left || root->right) {
        if(root->left) return getSmallest(root->left);
        if(root->right && !root->left) return root;
    }
    return root;

}
// END   OF FUNCTION TO GET SMALLEST ELEMENT.

Queue q; int dummy=0;

// START OF SEARCHING IN BST FUNCTION.
// #SEARCHBYID
Node * searchById (Tree *root,int id){
    if (!root)
        return NULL;
    if (root->data.id == id)
        return root;
    if (id < root->data.id)
        return searchById(root->left,id);
    else
        return searchById(root->right,id);
}

// #SEARCHBYNAME
Node * searchByName (Tree *root,char *name,int id){
    char fname[strlen(name)], froot[strlen(root->data.name)];
    strcpy(fname,name); strcpy(froot,root->data.name);
    strtoupper(fname); strtoupper(froot);
    if (!root)
        return NULL;
    if(strstr(froot,fname)){
        // printf("%-20s:%-4d:%p\n",root->data.name,data(root),root );
        if(id!=-1 && ((root->data.id)==id)){
            empty(&q);
            dummy = 1;
            push(&q,root);
            return root;
            exit(0);
        }else if(!dummy)
            push(&q,root);
        if(root->left)
            searchByName(root->left,name,id);
        if(root->right)
            searchByName(root->right,name,id);
    }else{
        /*if(strcmp(froot,fname) < 0){ // root->data.name is larger than name (go right)
            // printf("comparing: %s,%s...go right\n",froot,fname);
            if(root->left)
                return searchByName(root->left,name,id);
        }else if(strcmp(froot,fname) > 0){
            // printf("comparing: %s,%s...go left\n",froot,fname);
            if(root->right)
                return searchByName(root->right,name,id);
        }*/
            if(root->right)
                searchByName(root->right,name,id);
            if(root->left)
                searchByName(root->left,name,id);
    }
    return NULL;
}

// END   OF SEARCHING IN BST FUNCTION.

// START OF FUNCTION TO GET PARENT OF NODE.
// #GETPARENT
Node * getParent(Tree *root,Node *node){
    if(root) {
        if(root->left == node || root->right == node) {
            return root;
        }else{
            if(node->data.id < root->data.id)
                root = root->left;
            else
                root = root->right;
            return getParent(root,node);
        }
    }
    return NULL;
}

char * name(Node* node){
    strtoupper(node->data.name);
    return (node->data.name);
}


// #fast
Node * getParentName(Tree *root,Node *node){
    if(root) {
        if( root->left == node || root->right == node)
            return root;
        else{
            char fname[strlen(root->data.name)]; strcpy(fname,root->data.name) ;
            char lname[strlen(node->data.name)]; strcpy(lname,node->data.name);
            strtoupper(fname); strtoupper(lname);
            if(strcmp(fname,lname) < 0 ){
                root = root->right;
            }else{
                root = root->left;
            }
            return getParentName(root,node);
        }
    }
    return NULL;
}
// END   OF FUNCTION TO GET PARENT OF NODE.

// START OF FUNCTION GETTING MAX,MIN VALUE IN A TREE.
// #GETMAX
Node * getMax(Tree *root){
    return !root->right ? root : getMax(root->right);
}
// #GETMIN
Node * getMin(Tree *root){
    return !root->left  ? root : getMin(root->left);
}

Node * getMaxName(Tree *root){
    return !root->right ? root : getMaxName(root->right);
}
Node * getMinName(Tree *root){
    return !root->left ? root : getMinName(root->left);
}

// END   OF FUNCTION GETTING MAX,MIN VALUE IN A TREE.

// START OF DELETING FROM BST FUNCTION.
// #DELETE
void delete(Tree ** root, Node * parent, Node * node){
    if(!parent && node) {
        if(!node->left && !node->right){ // Not a single child
            (*root)->data.id = ~(1<<31);
        }else if(!node->left && node->right){ // only RIGHT child
            Node *minNode = getMin((*root)->right); Node *parentMinNode = getParent((*root),minNode);
            (parentMinNode->left == minNode) ? (parentMinNode->left = minNode->right) : (parentMinNode->right =  minNode->right);
            minNode->right = (*root)->right;
            (*root) = minNode;
        } else if(node->left && !node->right){ // only LEFT child
            Node *maxNode = getMax((*root)->left); Node * parentMaxNode = getParent((*root),maxNode);
            (parentMaxNode->left == maxNode) ? (parentMaxNode->left = maxNode->left) : (parentMaxNode->right = maxNode->left);
            maxNode->left = (*root)->left;
            (*root) = maxNode;
        } else if(node->left && node->right){ // have BOTH children
            Node *maxNode = getMax((*root)->left); Node * parentMaxNode = getParent((*root),maxNode);
            (parentMaxNode->left == maxNode) ? (parentMaxNode->left = NULL) : (parentMaxNode->right = NULL);
            maxNode->left = (*root)->left; maxNode->right = (*root)->right;
            (*root) = maxNode;
        }
        return ;
    }else if(parent && node){
        if(!node->left && !node->right){ // Not a single child
            (parent->left == node) ? (parent->left = NULL) : (parent->right = NULL) ;
        }else if(!node->left && node->right){ // only RIGHT child
            (parent->left == node) ? (parent->left = node->right) : (parent->right = node->right) ;
        }else if(node->left && !node->right){ // only LEFT child
            (parent->left == node) ? (parent->left = node->left) : (parent->right = node->right) ;
        }else if(node->left && node->right){ // have BOTH children
            Node *maxNode = getMax(node->left); Node *parentMaxNode = getParent((*root),maxNode);
            (parentMaxNode->left == maxNode )? (parentMaxNode->left = NULL) : (parentMaxNode->right = NULL);
            (parent->left == node) ? (parent->left = maxNode) : (parent->right = maxNode);
            maxNode->left = node->left; maxNode->right = node->right;
        }
        free(node);
    }
}

void deleteFromName(Tree **root,Node *parent,Node * node){
    if(!parent && node) {
        if(!node->left && !node->right) {
            (*root)->data.id = ~(1<<31);
        }else if(!node->left && node->right){
            Node *minNode = getMinName((*root)->right);
            Node *parentMinNode = getParentName((*root),minNode);
            (parentMinNode->left == minNode) ? (parentMinNode->left = minNode->right) : (parentMinNode->right =  minNode->right);
            minNode->right = (*root)->right;
            (*root) = minNode;
        }else if(node->left && !node->right){
            Node *maxNode = getMaxName((*root)->left);
            Node * parentMaxNode = getParentName((*root),maxNode);
            (parentMaxNode->left == maxNode) ? (parentMaxNode->left = maxNode->left) : (parentMaxNode->right = maxNode->left);
            maxNode->left = (*root)->left;
            (*root) = maxNode;
        } else if(node->left && node->right){
            Node *maxNode = getMaxName((*root)->left);
            Node * parentMaxNode = getParentName((*root),maxNode);
            (parentMaxNode->left == maxNode) ? (parentMaxNode->left = NULL) : (parentMaxNode->right = NULL);
            maxNode->left = (*root)->left; maxNode->right = (*root)->right;
            (*root) = maxNode;
        }
        return ;
    }else if(parent && node) {
        if(!node->left && !node->right) {
            (parent->left == node ) ? (parent->left=NULL) : (parent->right=NULL);
        }else if(!node->left && node->right){
            (parent->left == node) ? (parent->left = node->right) : (parent->right = node->right);
        } else if(node->left && !node->right){
            (parent->left == node ) ? (parent->left = node->left) : (parent->right = node->left);
        }else if(node->left && node->right){
            Node * maxNode = getMaxName((*root)->left);
            Node * parentMaxNode = getParentName((*root),maxNode);
            (parentMaxNode->left == maxNode )? (parentMaxNode->left = NULL) : (parentMaxNode->right = NULL);
            (parent->left == node) ? (parent->left = maxNode) : (parent->right = maxNode);
            maxNode->left = node->left; maxNode->right = node->right;
        }
        free(node);
    }
}
// END   OF DELETING FROM BST FUNCTION.

// START OF FUNCTION THAT LOADS NAMES FROM FILE
// #LOADIDTREE
void loadIdTree(Tree **root){
    char line[50]; int id;
    FILE *fp = fopen("students_info.txt", "r");
    while (fgets(line,50,fp)){
        char name[40];
        strcpy(name,strtok(line,","));
        id = atoi(strtok(NULL,"\n")); // convert string to number
        (!*root) ? *root = (newNode(id,name)) : (insertInId((*root),id,name));
    }
    fclose(fp);
}

// #LOADNAMETREE
void loadNameTree(Tree **root){
    char line[50]; int id;
    FILE *fp = fopen("students_info.txt", "r");
    while (fgets(line,50,fp)){
        char name[40];
        strcpy(name,strtok(line,","));
        id = atoi(strtok(NULL,"\n")); // convert string to number
        (!*root) ? *root = (newNode(id,name)) : (insertInName((*root),id,name));
    }
    fclose(fp);
}
// END   OF FUNCTION THAT LOADS NAMES FROM FILE

void displaySortedTree(Tree *root){ inTravers(root); }

void edit(Tree **idTree,Tree **nameTree,Node * idNode,Node *nameNode,char *name,int id){
    deleteFromName(nameTree,getParentName(*nameTree,nameNode),nameNode);
    delete(idTree,getParent(*idTree,idNode),idNode);
    insertInId(*idTree,id,name);
    insertInName(*nameTree,id,name);
}

Tree *idTree=NULL ,*nameTree=NULL;
int main(){
    reset(&q);
    char menu[2];
    do{
        system("cls");
        printf("1.Load Students info (from file).\n");
        printf("2.Add new student.\n");
        printf("3.Update student info.\n");
        printf("4.Remove student.\n");
        printf("5.Search for a student.\n");
        printf("6.Save what you did in file.\n");
        printf("7.Show all info (inOrder).\n");
        printf("8.Show all info (preOrder).\n");
        printf("9.Show all info (postOrder).\n");
        printf("10.Show all info (TreeShape).\n");
        printf("11.Exit\n");
        printf("\n\nChoice: "); scanf("%s",menu);
    }while(atoi(menu)<=0 || atoi(menu)>=12);
    int choice = atoi(menu);

    system("cls");
    switch(choice){
        case 1:
            printf("Loading from file...\n");
            loadNameTree(&nameTree); loadIdTree(&idTree);
            printf("Loaded successfully.\n");
            system("pause");
            break;
        case 2:
            if(!idTree || !nameTree){
                printf("Error ! , you didn't load the info first.\n");
                system("pause");
                printf("Importing data for you.\n");
                loadNameTree(&nameTree); loadIdTree(&idTree);
                printf("\n\nLoaded successfully.\n");
            }
            printf("Adding student:\n");
            printf("Enter his name: "); char name[40]; getchar(); gets(name);
            char idString[10];
            do{
                printf("Enter valid id: "); scanf("%s",idString);
            }while(atoi(idString)<=0);
            int id= atoi(idString);
            insertInName(idTree,id,name);
            insertInName(nameTree,id,name);
            printf("Successfully added\n");
            inTravers(nameTree);
            system("pause");
            break;
        case 3:
            if(!idTree || !nameTree){
                printf("Error ! , you didn't load the info first.\n");
                system("pause");
                printf("Importing data for you.\n");
                loadNameTree(&nameTree); loadIdTree(&idTree);
                printf("\n\nLoaded successfully.\n\n");
            }
            printf("Updating student info : \n");
            printf("How do you want to search ?\n");
            printf("1.By ID.\n");
            printf("2.By Name.\n");
            printf("Choice: "); scanf("%s",menu);
            if(atoi(menu)==1) { // search by id
                char idString[10];
                do{
                    printf("Enter valid id : "); scanf("%s",idString);
                }while(atoi(idString)<=0);
                int id = atoi(idString);
                Node * idNode = searchById(idTree,id);
                if(idNode){
                    printf("Name: %-20s,ID: %-4d,%p: \n\n",idNode->data.name,idNode->data.id,idNode );
                    // i have the node
                    // go edit it , but first get node of name tree
                    printf("Enter his new name: "); char newname[40]; getchar(); gets(newname);
                    char newidString[10];
                    do{
                        printf("Enter his new valid id: "); scanf("%s",newidString);
                    }while(atoi(newidString)<=0);
                    int newid = atoi(newidString);
                    searchByName(nameTree,"",id);
                    Node *namenode = pop(&q);
                    edit(&idTree,&nameTree,idNode,namenode,newname,newid);
                }else
                    printf("No search results !\n");
            }else if(atoi(menu)==2){
                char name[40];
                printf("Enter valid name : "); scanf("%s",name);
                searchByName(nameTree,name,-1);
                if(!isEmpty(&q)){
                    display(q);
                    printf("Choose specific id.\n");
                    char newidString[10];
                    do{
                        printf("Enter valid id you want to edit : "); scanf("%s",newidString);
                    }while(atoi(newidString)<=0);
                    int id = atoi(newidString);
                    searchByName(nameTree,name,id);
                    if(!isEmpty(&q)) {
                        Node *node = pop(&q);
                        printf("Name: %-20s,ID: %-4d,%p: \n\n",node->data.name,node->data.id,node );
                        char newname[40];
                        printf("Enter new name: "); getchar(); gets(newname);
                        char newidString[10];
                        Node * idnode = searchById(idTree,id);
                        do{
                            printf("Enter valid id: "); scanf("%s",newidString);
                        }while(atoi(newidString)<=0);
                        int newid = atoi(newidString);
                        edit(&idTree,&nameTree,idnode,node,newname,newid);
                    }else
                        printf("No search results !\n");
                }
                else
                    printf("No search results\n");
            }
            inTravers(idTree);
            system("pause");
            break;
        case 5:
            if(!idTree || !nameTree){
                printf("Error ! , you didn't load the info first.\n");
                system("pause");
                printf("Importing data for you.\n");
                loadNameTree(&nameTree); loadIdTree(&idTree);
                printf("\n\nLoaded successfully.\n");
            }
            printf("How do you want to search ?\n");
            printf("1.By ID.\n");
            printf("2.By Name.\n");
            printf("Choice: "); scanf("%s",menu);
            if(atoi(menu)==1) {
                char idString[10];
                do{
                    printf("Enter valid id : "); scanf("%s",idString);
                }while(atoi(idString)<=0);
                int id = atoi(idString);
                Node * node = searchById(idTree,id);
                if(node)
                    printf("Name: %-20s,ID: %-4d,%p: \n",node->data.name,node->data.id,node );
                else
                    printf("No search results !\n");
            }else if(atoi(menu)==2){
                char name[40];
                printf("Enter valid name : "); scanf("%s",name);
                searchByName(nameTree,name,-1);
                if(!isEmpty(&q))
                    display(q);
                else
                    printf("No search results\n");
            }
            system("pause");
            break;
        case 6:
            printf("Saving changes..\n");
            FILE *fp = fopen("students_info.txt","w");
            saveToFile(idTree,fp);
            fclose(fp);
            printf("Saved successfully.\n");
            system("pause");
            break;
        case 7:
            if(!idTree || !nameTree){
                printf("Error ! , you didn't load the info first.\n");
                system("pause");
                printf("Importing data for you.\n");
                loadNameTree(&nameTree); loadIdTree(&idTree);
                printf("\n\nLoaded successfully.\n");
            }
            printf("In which way you want it to be sorted ? \n");
            printf("1.Sorted By ID.\n");
            printf("2.Sorted By Name.\n");
            printf("choice: "); scanf("%s",menu);
            printf("%d\n", atoi(menu));
            atoi(menu)==1 ? inTravers(idTree) : inTravers(nameTree);
            system("pause");
            break;
        case 8:
            if(!idTree || !nameTree){
                printf("Error ! , you didn't load the info first.\n");
                system("pause");
                printf("Importing data for you.\n");
                loadNameTree(&nameTree); loadIdTree(&idTree);
                printf("\n\nLoaded successfully.\n");
            }
            printf("In which way you want it to be sorted ? \n");
            printf("1.Sorted By ID.\n");
            printf("2.Sorted By Name.\n");
            printf("choice: "); scanf("%s",menu);
            printf("%d\n", atoi(menu));
            atoi(menu)==1 ? preTravers(idTree) : preTravers(nameTree);
            system("pause");
            break;
        case 9:
            if(!idTree || !nameTree){
                printf("Error ! , you didn't load the info first.\n");
                system("pause");
                printf("Importing data for you.\n");
                loadNameTree(&nameTree); loadIdTree(&idTree);
                printf("\n\nLoaded successfully.\n");
            }
            printf("In which way you want it to be sorted ? \n");
            printf("1.Sorted By ID.\n");
            printf("2.Sorted By Name.\n");
            printf("choice: "); scanf("%s",menu);
            printf("%d\n", atoi(menu));
            atoi(menu)==1 ? postTravers(idTree) : postTravers(nameTree);
            system("pause");
            break;
        case 10:
            if(!idTree || !nameTree){
                printf("Error ! , you didn't load the info first.\n");
                system("pause");
                printf("Importing data for you.\n");
                loadNameTree(&nameTree); loadIdTree(&idTree);
                printf("\n\nLoaded successfully.\n");
            }
            printf("In which way you want it to be sorted ? \n");
            printf("1.Sorted By ID.\n");
            printf("2.Sorted By Name.\n");
            printf("choice: "); scanf("%s",menu);
            printf("%d\n", atoi(menu));
            atoi(menu)==1 ? inShow(idTree,0) : inShow(nameTree,0);
            system("pause");
            break;
        case 11:
            exit(0);
            break;

    }

    // main();
    return 0;
}