#include <stdlib.h>
#include <stdio.h>
using namespace std;
struct node{
    int data;
    struct node *left;
    struct node *right;
};

typedef struct node node;

void _init(node **T){
    *T = NULL;
}

void insert(int value, node **T){
    if (*T == NULL) {
        *T = (node *) malloc(sizeof(node));
        (*T)->data = value;
        printf ("%d  \n", (*T)->data);
        (*T)->left = NULL;
        (*T)->right = NULL;
    }
    else if (value < (*T)->data)
        insert(value, &(*T)->left);
    else if (value > (*T)->data)
        insert(value, &(*T)->right);
}

int search(int value, node **T){
    if (*T == NULL)
        return 0;
    else if (value < (*T)->data)
        search(value, &(*T)->left);
    else if (value > (*T)->data)
        search(value, &(*T)->right);
    return 1;
}

node* remove_node(int value, node *T){
    node *save;
    //we need to create a copy to save the info
    if (T = NULL)
        printf("%s \n", "Number not found" );
    //First we check to see if we are at the right point for deletion
    if (T->data == value) {
        //IF we are removing a leaf
        if ( ( T->right == NULL) && ( (T->left == NULL)) ) {
            free(T);//free the node
            return NULL;
        }
        //Removing degree 1 branch, (only one child)
        else if ( ( T->right == NULL) || ( (T->left == NULL)) ){
            if(T->right == NULL) {
                save = T->left;
                free(T);
                return save;
            }
            else {
                save = T->right;
                free(T);
                return save;
            }
        }

        //if ( ( (*T)->right != NULL) && ( ((*T)->left != NULL)) ) //two children

    }

    //If not, find the proper location in the code
    else if (value < T->data)
        remove_node(value, T->left);
    else if (value > T->data)
        remove_node(value, T->right);

}


void print_ordered(node **T){
    if (*T == NULL)
        return;
    print_ordered(&(*T)->left);
    printf("%d    \n", (*T)->data);
    print_ordered(&(*T)->right);
}

int main(){
    node *T;
    _init(&T);

    //populate tree
    insert(5,&T);
    insert(24,&T);
    insert(19,&T);
    insert(17, &T);
    insert(93, &T);

    printf("%s ", "Search Result: ");
    printf("%d   \n",search(5,&T));
    printf("%s \n", "In Order:  ");
    print_ordered(&T);

    //remove element
    remove_node(2, T);
    return 0;
}