#ifndef TREE_H
#define TREE_H

#include <stdlib.h>
#include <stdbool.h>

typedef struct{
    Node* root;
    int size;
} tree;



tree* create_new_tree(){
    tree* t = calloc(1, sizeof(tree));
    return t;
}

void private_insert(tree* t, Node *currRoot, Node* element){
    if(element->value <= currRoot->value){
        if(currRoot->left == NULL){
            element->previous = currRoot;
            currRoot->left = element;

        }
        else private_insert(t, currRoot->left, element);
    }
    else{
        if(currRoot->right == NULL){
            element->previous = currRoot;
            currRoot->right = element;
        }
        else private_insert(t, currRoot->right, element);
    }
}



void private_delete_tree(tree* t, Node* root){
    if(root != NULL){
        if(root->left != NULL) private_delete_tree(t, root->left);
        if(root->right != NULL) private_delete_tree(t, root->right);
        free(root);
    }
}

void private_print(tree* t, Node* root){
    if(root != NULL){
        printf(" (");
        private_print(t, root->left);
        printf(", %d,",root->value);
        private_print(t, root->right);
        printf(")");
    }
    else printf("n");
}

void public_insert(tree* t, int value){
    Node* element = createNode(value);
    if(t->root == NULL) t->root=element;
    else private_insert(t, t->root, element);
}

bool public_contains(tree* t, int value){
    Node* tmp = t->root;
    while(tmp != NULL){
        if(tmp->value == value) return true;
        else{
            if(value <= tmp->value) tmp = tmp->left;
            else tmp = tmp->right;
        }
    }
    return false;
}

void public_print(tree* t){
    private_print(t, t->root);
    printf("\n");
}

void public_delete_value(tree* t, int value){
    Node* curr = t->root;

    while(curr->value != value){
        if(value <= curr->value) curr = curr->left;
        else curr = curr->right;

    }
    //1. Fall
    if(curr->left == NULL && curr->right == NULL){
        free(curr);
    }

    //2. Fall
    Node* tmp = curr->previous;
    if(curr->left != NULL && curr->right == NULL){

        if(tmp->left == curr){
            tmp->left = curr->left;
            curr->left->previous = tmp;
            free(curr);
        }

        if(tmp->right == curr){
            tmp->right = curr->left;
            curr->left->previous = tmp;
            free(curr);
        }
    }

     if(curr->left == NULL && curr->right != NULL){

        if(tmp->left == curr){
            tmp->left = curr->right;
            curr->left->previous = tmp;
            free(curr);
        }

        if(tmp->right == curr){
            tmp->right = curr->right;
            curr->right->previous = tmp;
            free(curr);
        }
     }

     //3. Fall
     Node* previous_pos = curr->previous;
     Node* position = curr;
     Node* inorder = curr->right;

     while(inorder->left != NULL){
         inorder = inorder->left;
     }

     if(previous_pos->right == curr){

         previous_pos->right = inorder;
         inorder->previous = previous_pos;
         inorder->right = position->right;
         position->right->left = NULL;
         position->right->previous = position;
         inorder->left = position->left;
         free(curr);

     }

     if(previous_pos->left == curr){

         previous_pos->left = inorder;
         inorder->previous = previous_pos;
         inorder->right = position->right;
         position->right->left = NULL;
         position->right->previous = position;
         inorder->left = position->left;
         free(curr);

     }








}






#endif