#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);



}