bst

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

#define bigNum ~(1<<31)

typedef struct Data {
    int id;
    char firstName[20];
    char lastName[20];
}Data;

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

typedef Node Tree;

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

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

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

// START OF TRAVERSING FUNCTIONS.
void preTravers(Tree *root){
    if(root) {
        printf("[%d]\n", root->data.id);
        preTravers(root->left);
        preTravers(root->right);
    }
}

void postTravers(Tree *root){
    if(root) {
        postTravers(root->left);
        postTravers(root->right);
        printf("[%d]\n", root->data.id);
    }
}

void inTravers(Tree *root){
    if(root) {
        inTravers(root->left);
        printf("[%d]\n", root->data.id);
        inTravers(root->right);
    }
}
// END OF TRAVERSING FUNCTIONS.

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

// START OF INSERTING IN BST FUNCTION.
void insert(Tree *root,int id,char firstName[],char lastName[]){
    Node * node = newNode(id,firstName,lastName);
    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
                insert(root->left,id,firstName,lastName);
        }else{
            // GO RIGHT
            // if there is no right node
            if(!root->right)
                root->right = node;
            else
                insert(root->right,id,firstName,lastName);
        }
    }
    // return node;
}
// END   OF INSERTING IN BST FUNCTION.

// START OF FUNCTION TO GET SMALLEST ELEMENT.
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.

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

// START OF FUNCTION TO GET PARENT OF NODE.
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;
}
// END   OF FUNCTION TO GET PARENT OF NODE.

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

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

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

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

// START OF DELETING FROM BST FUNCTION.
void delete(Tree ** root, Node * parent, Node * node){
    if(!parent) {
        if(!node->left && !node->right){
            (*root)->data.id = ~(1<<31);
        }else if(!node->left && node->right){
            Node *minNode = getMin((*root)->right); Node *parentMinNode = getParent((*root),minNode);
            (parentMinNode->left == minNode) ? (parentMinNode->left = NULL) : (parentMinNode->right = NULL);
            minNode->left = (*root)->left; minNode->right = (*root)->right;
            (*root) = minNode;
        } else if(node->left && !node->right){
            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;
        } else if(node->left && node->right){
            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){
        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);
    }
}
// END   OF DELETING FROM BST FUNCTION.

int main(){
    system("clear");

    printf("\n====================================================\n");

    Tree *root  = newNode(80,"Ramy","Tamer");
    insert(root,2162,"Mohab","Osama");


    inShow(root,0);
    printf("\n====================================================\n");

    Node *node = search(root,80);
    delete(&root,getParent(root,node),node);

    inShow(root,0);
    return 0;
}