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

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

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

typedef Node Tree;

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

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

Node * addLeft(Node *root,int id){
    if(root) {
        Node* new = newNode(id);
        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) {
        inShow(root->right,currentDepth+1);
        int i; for(i=0;i<currentDepth;i++) printf("\t");
        printf("%3d::%p ", 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){
    Node * node = newNode(id);
    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);
        }else{
            // GO RIGHT
            // if there is no right node
            if(!root->right)
                root->right = node;
            else
                insert(root->right,id);
        }
    }
    // 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;
}
// NED   OF FUNCTION TO GET PARENT OF NODE.

// START OF DELETING FROM BST FUNCTION.
/*
void delete(Tree *root,Node *parent,Node *node){
    if(root) {
        if(root==node){ // WE ARE AT THE NODE BEGIN DELETE OPERATION
            if(!node->left && !node->right) { // Check if there are no children
                (parent->left == node) ? (parent->left = NULL) : (parent->right = NULL);

            }else if(!node->left && node->right) { // check if there no left child for node "only right"
                (parent->left == node) ? (parent->left = node->right) : (parent->right=node->right);

            }else if(node->left && !node->right){ // check if there no right child for node "only left"
                (parent->left == node) ? (parent->left = node->left) : (parent->right=node->left );

            }else if(node->left && node->right){ // check if there both right and left children

                if(parent->right == node){ // Node is on right, we have to get smallest of right branch
                    Node * smallest = getSmallest(node->right);
                    printf("parent of smallest: [%d],smallest : [%d]\n", getParent(root,smallest)->data.id,smallest->data.id);
                }
                Node * smallest = getSmallest(node);
                Node * parentOfSmallest = getParent(root,smallest);

                if(parentOfSmallest->left == smallest)
                    parentOfSmallest->left = NULL;
                else
                    parentOfSmallest->right = NULL;

                if(parent->left==node) {
                    parent->left = smallest;
                }else{
                    parent->right = getSmallest(node->right);
                }
                smallest->left = node->left;
                smallest->right = node->right;

            }
            free(node);
        }else{
            // TRYING TO REACH THE NODE
            parent = root;
            if(node->data.id < root->data.id)
                root = root->left;
            else
                root = root->right;
            delete(root,parent,node);
        }
    }
}
*/
// END   OF DELETING FROM BST FUNCTION.

// 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.

int data(Node *node){
    return node->data.id;
}

int hasChild(Node *node){
    return node->right || node->left;
}

void delete(Tree * root, Node * parent, Node * node){
    if(!parent) {
        // root ==== node
        // printf("without parent\n");
        if(hasChild(node)){
            // printf("has child\n");
        }else{
            // printf("no child\n");
            free(root); // node hea hea el root == free(root);
            root = NULL;
        }
    }else  if(node){
        if(!node->left && !node->right){ // Not a single child
            if(parent)
                (parent->left == node) ? (parent->left = NULL) : (parent->right = NULL) ;
            else{ // case of no parents "root of tree"

            }
        }else if(!node->left && node->right){ // only RIGHT child
            if(parent)
                (parent->left == node) ? (parent->left = node->right) : (parent->right = node->right) ;
            else{ // case of no parents "root of tree"

            }
        }else if(node->left && !node->right){ // only LEFT child
            if(parent)
                (parent->left == node) ? (parent->left = node->left) : (parent->right = node->right) ;
            else{ // case of no parents "root of tree"

            }
        }else if(node->left && node->right){ // have BOTH children
            if(parent){
                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;
            }else{ // case of no parents "root of tree"

            }
        }
        free(node);
    }
}


void build(Tree *root){
    insert(root,100);
    insert(root,70);

    insert(root,50);
    insert(root,76);
    insert(root,90);
    insert(root,200);

    insert(root,40);
    insert(root,60);
    insert(root,73);
    insert(root,77);
    insert(root,95);
    insert(root,150);

    insert(root,72);
    insert(root,74);
}

void buildMohab(Tree *root){
    insert(root,40);
    insert(root,90);

    insert(root,30);
    insert(root,45);
    insert(root,80);
    insert(root,100);

    insert(root,20);
    insert(root,41);
    insert(root,49);
    insert(root,200);
}

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

    printf("[NUMBER VALUE]::[ADDRESS OF NODE]\n");
    printf("\n====================================================\n");

    Tree *root  = newNode(80);
    // Tree *root  = newNode(50);

    /*Tree *node1 = addLeft(root,2);
    Tree *node2 = addRight(root,10);
    addLeft(node1,1);
    addRight(addRight(node1,4),5);
    addLeft(node2,9);
    addRight(addLeft(addRight(node2,100),50),60);*/

    // preTravers(root);
    // postTravers(root);
    // inTravers(root);

    // inShow(root,0);

    // build(root);

    // insert(root,50);
    // insert(root,90);
    // insert(root,60);
    // insert(root,100);
    // insert(root,200);
    printf("origin tree\n");
    // free(root);
    root = NULL;
    inShow(root,0);
    printf("\n====================================================\n");

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


    printf("after tree\n");
    inShow(root,0);
    return 0;
}