#include<stdio.h>
#include<stdlib.h>

#define MAX_QUEUE 100

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

struct Node *root = NULL;

struct Node* createNode(int data){
	struct Node *newNode = (struct Node*)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) return createNode(data);
	if(data < root->data)
		root->left = insert(root->left, data);
	else if(data > root->data)
		root->right = insert(root->right, data);
	else
		printf("Duplicate value %d not inserted.\n", data);
	return root;
}

struct Node* search(struct Node *root, int key){
	if(root == NULL || root->data == key)
		return root;
	if(key < root->data)
		return search(root->left, key);
	return search(root->right, key);
}

struct Node* findMin(struct Node *root){
	if(root == NULL){
		printf("Tree is empty!\n");
		return NULL;
	}
	while(root->left != NULL)
		root = root->left;
	return root;
}

struct Node* findMax(struct Node *root){
	if(root == NULL){
		printf("Tree is empty!\n");
		return NULL;
	}
	while(root->right != NULL)
		root = root->right;
	return root;
}

struct Node* deleteNode(struct Node *root, int key){
	if(root == NULL){
		printf("Value %d not found!\n", key);
		return root;
	}
	if(key < root->data)
		root->left = deleteNode(root->left, key);
	else if(key > root->data)
		root->right = deleteNode(root->right, key);
	else {
		// Case 1: No child (leaf)
		if(root->left == NULL && root->right == NULL){
			free(root);
			return NULL;
		}
		// Case 2: One child
		if(root->left == NULL){
			struct Node *temp = root->right;
			free(root);
			return temp;
		}
		if(root->right == NULL){
			struct Node *temp = root->left;
			free(root);
			return temp;
		}
		// Case 3: Two children - replace with inorder successor
		struct Node *successor = findMin(root->right);
		root->data = successor->data;
		root->right = deleteNode(root->right, successor->data);
	}
	return root;
}

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

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

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

void levelOrder(struct Node *root){
	if(root == NULL){
		printf("Tree is empty!\n");
		return;
	}
	struct Node *queue[MAX_QUEUE];
	int front = 0, rear = 0;
	queue[rear++] = root;
	while(front < rear){
		struct Node *current = queue[front++];
		printf("%d ", current->data);
		if(current->left != NULL)
			queue[rear++] = current->left;
		if(current->right != NULL)
			queue[rear++] = current->right;
	}
}

int height(struct Node *root){
	if(root == NULL) return -1;
	int leftH = height(root->left);
	int rightH = height(root->right);
	return (leftH > rightH ? leftH : rightH) + 1;
}

int countNodes(struct Node *root){
	if(root == NULL) return 0;
	return 1 + countNodes(root->left) + countNodes(root->right);
}

int countLeaves(struct Node *root){
	if(root == NULL) return 0;
	if(root->left == NULL && root->right == NULL) return 1;
	return countLeaves(root->left) + countLeaves(root->right);
}

void display(struct Node *root, int space){
	if(root == NULL) return;
	space += 5;
	display(root->right, space);
	printf("\n");
	for(int i = 5; i < space; i++) printf(" ");
	printf("%d\n", root->data);
	display(root->left, space);
}

int main(){
	int choice, value;

	printf("\n========================================\n");
	printf("   BINARY SEARCH TREE IMPLEMENTATION\n");
	printf("========================================\n");

	do {
		printf("\n--- BST Menu ---\n");
		printf(" 1. Insert\n");
		printf(" 2. Delete\n");
		printf(" 3. Search\n");
		printf(" 4. Inorder Traversal\n");
		printf(" 5. Preorder Traversal\n");
		printf(" 6. Postorder Traversal\n");
		printf(" 7. Level Order Traversal\n");
		printf(" 8. Find Minimum\n");
		printf(" 9. Find Maximum\n");
		printf("10. Height of Tree\n");
		printf("11. Count Nodes\n");
		printf("12. Count Leaves\n");
		printf("13. Display Tree\n");
		printf(" 0. Exit\n");
		printf("Enter choice: ");
		scanf("%d", &choice);

		switch(choice){
			case 1:
				printf("Enter value to insert: ");
				scanf("%d", &value);
				root = insert(root, value);
				printf("Inserted %d\n", value);
				break;
			case 2:
				printf("Enter value to delete: ");
				scanf("%d", &value);
				root = deleteNode(root, value);
				printf("Deleted %d\n", value);
				break;
			case 3:
				printf("Enter value to search: ");
				scanf("%d", &value);
				if(search(root, value))
					printf("Found %d in the tree.\n", value);
				else
					printf("%d not found.\n", value);
				break;
			case 4:
				printf("Inorder: ");
				inorder(root);
				printf("\n");
				break;
			case 5:
				printf("Preorder: ");
				preorder(root);
				printf("\n");
				break;
			case 6:
				printf("Postorder: ");
				postorder(root);
				printf("\n");
				break;
			case 7:
				printf("Level Order: ");
				levelOrder(root);
				printf("\n");
				break;
			case 8:
				{
					struct Node *min = findMin(root);
					if(min) printf("Minimum: %d\n", min->data);
				}
				break;
			case 9:
				{
					struct Node *max = findMax(root);
					if(max) printf("Maximum: %d\n", max->data);
				}
				break;
			case 10:
				printf("Height: %d\n", height(root));
				break;
			case 11:
				printf("Total nodes: %d\n", countNodes(root));
				break;
			case 12:
				printf("Leaf nodes: %d\n", countLeaves(root));
				break;
			case 13:
				printf("Tree Structure:\n");
				display(root, 0);
				break;
			case 0:
				printf("Exiting...\n");
				break;
			default:
				printf("Invalid choice!\n");
		}
	} while(choice != 0);

	return 0;
}