#include <iostream>
using namespace std;
 
struct Node{
	int data;
	struct Node *left;
	struct Node *right;
};
 
class BinarySearchTree{
	public:
	struct Node *root;
 
	BinarySearchTree(){
		root = NULL;
	}
 
	Node *getNode(int val){
		Node *newNode = new Node;
 
		newNode->data = val;
		newNode->left = newNode->right = NULL;
 
		return newNode;
	}
 
	void insert(int &val){
		if(!root){
			root = getNode(val);
			return;
		}
 
		insertHelper(root, NULL, val, false);
	}
 
	void insertHelper(Node *rt, Node *parent, int &val, bool isLeft){
 
		if(!rt){
			isLeft ? parent->left = getNode(val) : parent->right = getNode(val);
			return;
		}
 
		if(val < rt->data)
			insertHelper(rt->left, rt, val, true);
		else 
			insertHelper(rt->right, rt, val, false);
	}
 
	void searchNode(Node *rt, int &val){
		if(!rt || rt->data == val){
			cout<<"Element "<<val<<(rt ? " ": " not ")<<"found in the tree.\n";
			return;
		}
 
		if(val < rt->data)
			searchNode(rt->left, val);
		else
			searchNode(rt->right, val);
	}
 
	bool deleteNode(int &val){
		Node *rt = root;
		
		if(!rt)
			return false;
 
		if(rt->data == val){
			if(!rt->left && !rt->right)
				root = NULL;
			else if(!rt->left)
				root = rt->right;
			else if(!rt->right)
				root = rt->left;
			else
				return deleteNodeHelper(rt, NULL, val, false);
 
			delete rt;
			return true;
		}
		
		return deleteNodeHelper(rt, NULL, val, false);
	}
 
	bool deleteNodeHelper(Node *rt, Node *parent, int &val, bool isLeft){
		if(!rt)
			return false;
			
		if(rt->data == val){
			
			if(!rt->left && !rt->right){
				isLeft ? parent->left = NULL : parent->right = NULL;
				delete rt;
			}
			else if(!rt->left){
				isLeft ? parent->left = rt->right : parent->right = rt->right;
				delete rt;
			}
			else if(!rt->right){
				isLeft ? parent->left = rt->left : parent->right = rt->left;
				delete rt;
			}
			else{
				Node *minNode = min(rt->right);
				rt->data = minNode->data;
				deleteNodeHelper(rt->right, rt, rt->data, false);
			}
			return true;
		}
 
		if(val < rt->data)
			return deleteNodeHelper(rt->left, rt, val, true);
 
		return deleteNodeHelper(rt->right, rt, val, false);
	}
 
	Node *min(Node *rt){
		if(!rt->left){
			return rt;
		}
 
		return min(rt->left);
	}
 
	Node *max(Node *rt){
		if(!rt->right){
			return rt;
		}
 
		return max(rt->right);
	}
 
	void inOrder(Node *rt){
		if(!rt)
			return;
 
		inOrder(rt->left);
		cout<<rt->data<<" ";
		inOrder(rt->right);
	}
 
	void postOrder(Node *rt){
		if(!rt)
			return;
 
		postOrder(rt->left);
		postOrder(rt->right);
		cout<<rt->data<<" ";
	}
 
	void preOrder(Node *rt){
		if(!rt)
			return;
 
		cout<<rt->data<<" ";
		preOrder(rt->left);
		preOrder(rt->right);
	}
	
	void insertSortedArray(int *arr, int n){
		int low = 0, high = n-1;
		
		root = insertSortedArrayHelper(arr, low, high);
	}
	
	Node *insertSortedArrayHelper(int *a, int l, int h){
		if(l > h)
			return NULL;
		
		int mid = l + (h-l)/2;
		
		Node *rt = getNode(a[mid]);
		
		rt->left = insertSortedArrayHelper(a, l, mid-1);
		rt->right = insertSortedArrayHelper(a, mid+1, h);
		
		return rt;
	}
};
 
int main(){
 
	int opt, val;
	int *arr;
	
	BinarySearchTree tree;
	
	cout<<"Operations available on BST are:\n";
	cout<<"1. Insert an element\n2. Insert sorted array of elements\n"
	"3. Search an element\n4. Delete an element\n5. Minimum element in tree\n"
	"6. Maximum element in tree\n7. InOrder\n8. PreOrder\n9. PostOrder\n10. Exit\n";
	cout<<"************************************************\n";
	while(true){
		cin>>opt;
		switch(opt){
			case 1:
				cin>>val;
				tree.insert(val);
				cout<<"Element "<<val<<" is inserted into the tree.\n";
				break;
			case 2:
				cin>>opt;
				arr = new int[opt];
				cout<<"Sorted array elements ";
				for(int i=0; i<opt; ++i){ 
					cin>>arr[i]; cout<<arr[i]<<" ";
				}
				tree.insertSortedArray(arr, opt);
				cout<<"are inserted into the tree.\n";
				break;
			case 3:
				cin>>val;
				tree.searchNode(tree.root, val);
				break;
			case 4:
				cin>>val;
				cout<<"Element "<<val<<(tree.deleteNode(val) ? " is deleted\n": " not found for delete.\n");
				break;
			case 5:
				cout<<"The minimum element in the BST is: "<<tree.min(tree.root)->data<<"\n";
				break;
			case 6:
				cout<<"The maximum element in the BST is: "<<tree.max(tree.root)->data<<"\n";
				break;
			case 7:
				cout<<"InOrder: ";
				tree.inOrder(tree.root); cout<<"\n";
				break;
			case 8:
				cout<<"PreOrder: ";
				tree.preOrder(tree.root); cout<<"\n";
				break;
			case 9:
				cout<<"PostOrder: ";
				tree.postOrder(tree.root); cout<<"\n";
				break;
			case 10:
				exit(0);
		}
		cout<<"************************************************\n";
	}
 
	return 0;
}