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

/* Tree structure */
struct tree {
	int data;
	struct tree *left;
	struct tree *right;
} *root = NULL, *node = NULL, *temp = NULL;

/* Function for Insert data into the Tree */
struct tree* insert(int key,struct tree *leaf) {
	if(leaf == 0) {
		struct tree *temp;
		temp = (struct tree *)malloc(sizeof(struct tree));
		temp->data = key;
		temp->left = 0;
		temp->right = 0;
		printf("Data inserted!\n");
		return temp;
	}
	else {
		if(key < leaf->data)
			leaf->left = insert(key,leaf->left);
		else
			leaf->right = insert(key,leaf->right);
	}
	return leaf;					
}

/* Function for search data from Tree */
struct tree* search(int key,struct tree *leaf) {
	if(leaf != NULL) {
		if(key == leaf->data) {
			printf("Data found!\n");
			return leaf;
		}
		else {
			if(key < leaf->data)
				return search(key,leaf->left);
			else
				return search(key,leaf->right);
		}
	}
	else {
		printf("Data not found!\n");
		return NULL;
	}
}
										
/* Function for find minimum value from the Tree */
struct tree* minvalue(struct tree *node) {
	if(node == NULL)
		return NULL;

	/* Go to the left sub tree to find the min element */
	if(node->left)
		return minvalue(node->left);
	else
		return node;									
}

/* Function for find maximum value from the Tree */
struct tree* maxvalue(struct tree *node) {
	if(node == NULL)
		return NULL;

	/* Go to the left sub tree to find the max element */
	if(node->right)
		return maxvalue(node->right);
	else
		return node;									
}

/* Function for print binary tree in Preorder format */
void preorder(struct tree *leaf) {
	if(leaf == NULL)
		return;
	printf("%d\n",leaf->data);
	preorder(leaf->left);
	preorder(leaf->right);									
}

/* Function for print binary tree in Inorder format */
void inorder(struct tree *leaf) {
	if(leaf == NULL)
		return;
	preorder(leaf->left);
	printf("%d\n",leaf->data);
	preorder(leaf->right);									
}

/* Function for print binary tree in Postorder format */
void postorder(struct tree *leaf) {
	if(leaf == NULL)
		return;
	preorder(leaf->left);
	preorder(leaf->right);
	printf("%d\n",leaf->data);									
}

/* Function for delete node from the Tree */
struct tree* delete(struct tree *leaf, int key) {
	if(leaf == NULL)
		printf("Element Not Found!\n");
	else if(key < leaf->data)
		leaf->left = delete(leaf->left, key);
	else if(key > leaf->data)
		leaf->right = delete(leaf->right, key);
	else {
		if(leaf->right && leaf->left) {

			/* Replace with minimum element in the right sub tree */
			temp = minvalue(leaf->right);
			leaf->data = temp->data;

			/* Delete that node */
			leaf->right = delete(leaf->right,temp->data);
		}	
		else {
			/* If there is only one or zero children then directly remove it from the tree and connect its parent to its child */
			temp = leaf;
			if(leaf->left == NULL) 
				leaf = leaf->right;
			else if(leaf->right == NULL)
				leaf = leaf->left;
			free(temp);
			printf("Data delete successfully!\n");
		}
	}									
}

int main() {
	int key, choice;
	while(choice != 7) {
		printf("1. Insert\n2. Search\n3. Delete\n4. Display\n5. Min Value\n6. Max Value\n7. Exit\n");
		printf("Enter your choice:\n");
		scanf("%d", &choice);
		switch(choice) {
			case 1:
				printf("\nEnter the value to insert:\n");
				scanf("%d", &key);
				root = insert(key, root);
				break;
			case 2:
				printf("\nEnter the value to search:\n");
				scanf("%d", &key);
				search(key,root);
				break;
			case 3:
				printf("\nEnter the value to delete:\n");
				scanf("%d", &key);
				delete(root,key);
				break;
			case 4:
				printf("Preorder:\n");
				preorder(root);
				printf("Inorder:\n");
				inorder(root);
				printf("Postorder:\n");
				postorder(root);
				break;
			case 5:
				if(minvalue(root) == NULL)
					printf("Tree is empty!\n");
				else
					printf("Minimum value is %d\n", minvalue(root)->data);
				break;
			case 6:
				if(maxvalue(root) == NULL)
					printf("Tree is empty!\n");
				else
					printf("Maximum value is %d\n", maxvalue(root)->data);
				break;
			case 7:
				printf("Bye Bye!\n");
				exit(0);
				break;
			default:
				printf("Invalid choice!\n");
		}
	}
	return 0;
}


          /****** Output ******/
          
1. Insert

2. Search

3. Delete

4. Display

5. Min Value

6. Max Value

7. Exit

Enter your choice:

1

Enter the value to insert:

5

1. Insert

2. Search

3. Delete

4. Display

5. Min Value

6. Max Value

7. Exit

Enter your choice:

1

Enter the value to insert:

3

1. Insert

2. Search

3. Delete

4. Display

5. Min Value

6. Max Value

7. Exit

Enter your choice:

1

Enter the value to insert:

6

1. Insert

2. Search

3. Delete

4. Display

5. Min Value

6. Max Value

7. Exit

Enter your choice:

1

Enter the value to insert:

2

1. Insert

2. Search

3. Delete

4. Display

5. Min Value

6. Max Value

7. Exit

Enter your choice:

1

Enter the value to insert:

7

1. Insert

2. Search

3. Delete

4. Display

5. Min Value

6. Max Value

7. Exit

Enter your choice:

1

Enter the value to insert:

9

1. Insert

2. Search

3. Delete

4. Display

5. Min Value

6. Max Value

7. Exit

Enter your choice:

2

Enter the value to search:

2

Data found!

1. Insert

2. Search

3. Delete

4. Display

5. Min Value

6. Max Value

7. Exit

Enter your choice:

3

Enter the value to delete:

9

Data delete successfully!

1. Insert

2. Search

3. Delete

4. Display

5. Min Value

6. Max Value

7. Exit

Enter your choice:

4

Preorder:

5

3

2

6

7

Inorder:

2

3

5

6

7

Postorder:

2

3

7

6

5

1. Insert

2. Search

3. Delete

4. Display

5. Min Value

6. Max Value

7. Exit

Enter your choice:

5

Minimum value is 2

1. Insert

2. Search

3. Delete

4. Display

5. Min Value

6. Max Value

7. Exit

Enter your choice:

6

Maximum value is 7

1. Insert

2. Search

3. Delete

4. Display

5. Min Value

6. Max Value

7. Exit

Enter your choice:

7

Bye Bye!