#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"

struct Node {
    struct Node* left;
    int data;
    struct Node* right;
};

bool IsBstUtil(struct Node* root, int minValue, int maxValue) {
    if (root == NULL) return true;

    if (root->data > minValue && root->data < maxValue
        && IsBstUtil(root->left, minValue, root->data)
        && IsBstUtil(root->right, root->data, maxValue))
        return true;
    else
        return false;
}

bool IsBinarySearchTree(struct Node* root) {    //return true if BTS
    return IsBstUtil(root, INT_MIN, INT_MAX);  //aditional function
}

struct Node *GetNewNode(int data) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

struct Node* Insert(struct Node *root, int data) {
    if (root == NULL) {
        root = GetNewNode(data);
        return root;
    }
    else if (data <= root->data) {
        root->left = Insert(root->left, data);
    }
    else {
        root->right = Insert(root->right, data);
    }
    return root;
}

bool Search(struct Node* root, int data) {
    if (root == NULL)return false;
    if (root->data == data)return true;
    else if (data <= root->data)return Search(root->left, data);
    else return Search(root->right, data);
}

int FindMin(struct Node* root) {
    if (root == NULL) {
        printf("ERROR, THE TREE IS EMPTY");
        return -1;
    }
    if (root->left == NULL) {
        return root->data;
    }

    return FindMin(root->left);
}

int FindMax(struct Node* root) {
    if (root == NULL) {
        printf("ERROR;THE TREE IS EMPTY");
        return -1;
    }
    if (root->right == NULL) {
        return root->data;
    }

    return FindMax(root->right);
}

int height(struct Node *root) {
    if (root == NULL) {
        return -1;
    }
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);

    if (leftHeight > rightHeight) {
        return leftHeight + 1 ;
    }
    else {
        return rightHeight + 1;
    }
}

void InOrderPrint(struct Node* root) {
    if (root == NULL) {
        return;
    }
    if (root->left == NULL && root->right == NULL) {
        printf("%d  ", root->data);
        return;
    }
    if (root->left != NULL) {
        InOrderPrint(root->left);
    }
    printf("%d  ", root->data);
    if (root->right != NULL) {
        InOrderPrint(root->right);
    }
}

struct Node* MinAdress(struct Node* root) {
    if (root == NULL) {
        return NULL;
    }
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

struct Node* Delete(struct Node* root, int data) {
    if (root == NULL) {
        return NULL;
    }
    if (data < root->data) {
        root->left = Delete(root->left, data);
    }
    if (data > root->data) {
        root->right = Delete(root->right, data);
    }
    else {   // i found it =D
        // case 1 : no child
        if (root->left == NULL && root->right == NULL) {
            free(root);
            root = NULL;
        }
        // Case 2 : 1 child
        else if (root->left != NULL && root->right == NULL) {
            struct Node* temp = root;
            root = root->left;
            free(temp);
        }
        else if (root->right != NULL && root->left == NULL) {
            struct Node* temp = root;
            root = root->right;
            free(temp);
        }
        // case 3 : 2 children
        else{
            struct Node *temp = MinAdress(root->right);
            root->data = temp->data;
            root->right = Delete(root->right, temp->data);
        }
    }
    return root;
}

struct Node* Find(struct Node* root,int num) {
    if (root == NULL) return NULL;
    while (root->left != NULL && root->right != NULL) {

        if (num< root->data) root = root->left;
        if (num> root->data) root = root->right;
        if (num == root->data) return root;
    }
    return NULL;
}

struct Node* GetSuccessor(struct Node* root, int data) {
    // Search the node - o(h)
    struct Node* current = Find(root,data);
    if (current == NULL) return NULL;
    // Case 1 : Node has right subtree
    if (current->right != NULL) {
        struct Node *temp = current->right;
        while (temp->left != NULL) temp = temp->left;
        return temp;
    }
    // Case 2 : No right subtree
    else {
        struct Node* successor = NULL;
        struct Node* ancestor = root;
        while (ancestor != current) {
            if (current->data < ancestor->data) {
                successor = ancestor;
                ancestor = ancestor->left;
            }
            else {
                ancestor = ancestor->right;
            }
        }
        return successor;
    }
}

int main() {

    struct  Node *root = NULL;
    root = Insert(root, 15);
    root = Insert(root, 10);
    root = Insert(root, 20);
    root = Insert(root, 25);
    root = Insert(root, 8);
    root = Insert(root, 12);

    bool Bst = IsBinarySearchTree(root);
    if (Bst == false) {
        printf("This is not a Binary Search Tree \n \n");
    }
    else {
        printf("This is a Binary Search Tree \n \n");
    }

    int number;
    printf("Enter a number to search \n");
    scanf("%d", &number);
    if (Search(root, number) == true) {
        printf("found it \n \n");
    }
    else {
        printf("not found \n \n");
    }

    int Minimo = FindMin(root);
    printf("The Min of the tree is %d \n \n", Minimo);

    int Maximo = FindMax(root);
    printf("The Max of the tree is %d \n \n", Maximo);

    int TreeHeight = height(root);
    printf("the Height of the tree is %d \n \n", TreeHeight);

    printf("In Order Visit of the Tree is : ");
    InOrderPrint(root);

    int pred = 0;
    printf("\nChose a number and i will give you it's successor \n");
        scanf("%d", &pred);
    struct Node* successor = GetSuccessor(root, pred);
    printf("%d \n", successor->data);

    printf(" \nDelete a number \n");
    int k = 0;
    scanf("%d", &k);
    root = Delete(root, k);
    InOrderPrint(root);
}