BST

//Implemented by: Tariq Zaghal
#include <stdlib.h>
#include <stdio.h>
#include <math.h>


typedef struct BstNode* TNode;

struct BstNode{
    int data;
    TNode left;
    TNode right;
    int count;
};


TNode makeEmpty(TNode root);
TNode find(int x, TNode root);
TNode findMin(TNode root);
TNode findMax(TNode root);
TNode insert(int data, TNode root);
TNode delete(int x, TNode T);
int findHeight(TNode root);
int max(int x, int y);
void trace(TNode T);
struct BstNode* getNewNode(int data);

int main(){
    TNode root = NULL;

    root = insert(13,root);
    root = insert(3,root);
    root = insert(7,root);
    root = insert(20,root);
    root = insert(8,root);
    root = delete(5,root);
    trace(root);

    return 0;
}


void trace(TNode T){
    if(T!=NULL){
        trace(T->left);
        printf("%d\n ",T->data);
        trace(T->right);
    }

}

int findHeight(TNode root){

    if(root == NULL)
        return -1;
    else
        return max(findHeight(root->left),findHeight(root->left))+1;
}



int max(int x, int y){
    if(x>=y)
        return x;
    else
        return y;
}


TNode makeEmpty(TNode root){
    if(root!=NULL){
        return makeEmpty(root->left);
        return makeEmpty(root->right);
        free(root);
    }

    return NULL;
}


TNode find(int x, TNode root){
    if(root == NULL)
        return NULL;
    if(root->data == x){
        return root;
    }else if(x<root->data){
        return find(x,root->left);
    }else{
        return find(x,root->right);
    }
}


TNode findMin(TNode root){
    if(root == NULL)
        return NULL;
    else if (root->left == NULL)
        return root;
    else
        return findMin(root->left);
}



TNode findMax(TNode root){
    if(root == NULL)
        return NULL;
    else if (root->right == NULL)
        return root;
    else
        return findMax(root->right);
}





TNode delete(int x, TNode T){
    TNode temp;
    if(T==NULL){
        printf("Didn't find the node to be deleted!\n");
        return NULL;
    }
    else if (x<T->data) T->left = delete(x,T->left);
    else if (x>T->data) T->right = delete(x,T->right);

    else{//element Found!!




        if(T->left == NULL && T->right == NULL){//No children
            free(T);
            T = NULL;
        }else if(T->left == NULL){  //one right child
            TNode temp = T;
            T = T->right;
            free(temp);
        }else if(T->right == NULL){ //one left child
            TNode temp = T;
            T = T->left;
            free(temp);
        }else{  //two children
            TNode temp = findMin(T->right);
            T->data = temp->data;
            delete(T->data, T->right);
        }



    }

    return T;


}




struct BstNode* getNewNode(int data){
    struct BstNode* newNode = malloc(sizeof(struct BstNode));

    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->count = 1;

    return newNode;
}


struct BstNode* insert (int data, TNode root){
    if(root == NULL ){//the tree is empty
        root = getNewNode(data);
       // printf("%d\n",root->data);
        return root;
    }else if(data == root->data){
        //printf("%d\n",root->data);
        root->count++;
    }else if (data<root->data)
    {
        root->left = insert(data , root->left);
    }else{
        root->right = insert(data , root->right);
    }

}