#include <bits/stdc++.h>
using namespace std;

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

class AVLTree{
	public:
	Node *root;
	
	AVLTree(){
		root = NULL;
	}
	
	Node *getNode(int &val){
		Node *newNode = new Node;
		newNode->data = val;
		newNode->height = 0;
		newNode->left = newNode->right = NULL;
		
		return newNode;
	}
	
	int nodeHeight(Node *nd){
		if(!nd)
			return -1;
		
		return nd->height;
	}
	
	int balanceFactor(Node *nd){
		if(!nd)
			return 0;
		
		return nodeHeight(nd->left) - nodeHeight(nd->right); 
	}
	
	void insertNode(int &val){
		if(!root){
			root = getNode(val);
			return;
		}
		
		insertNodeHelper(root, NULL, val, false);
	}
	
	void insertNodeHelper(Node *rt, Node *parent, int &val, bool isLeft){
		if(!rt){
			isLeft ? parent->left = getNode(val) : parent->right = getNode(val);
			return;
		}
		
		if(val < rt->data)
			insertNodeHelper(rt->left, rt, val, true);
		else
			insertNodeHelper(rt->right, rt, val, false);
		
		/*======================= Re-Balancing =========================*/	
		rt->height = 1 + max(nodeHeight(rt->left), nodeHeight(rt->right));
		
		int balance_fact = balanceFactor(rt);
		
		if(balance_fact > 1 && val < rt->left->data){//LL rotation
			rightRotate(rt, parent, isLeft);
		}
		
		else if(balance_fact < -1 && val > rt->right->data){//RR rotation
			leftRotate(rt, parent, isLeft);
		}
		
		else if(balance_fact < -1 && val < rt->right->data){//RL rotation
			rightRotate(rt->right, rt, false);
			leftRotate(rt, parent, isLeft);
		}
		
		else if(balance_fact > 1 && val > rt->left->data){//LR rotation
			leftRotate(rt->left, rt, true);
			rightRotate(rt, parent, isLeft);
		}
		/*======================= Re-Balancing =========================*/
	}
	
	void leftRotate(Node *rootedNode, Node *parent, bool isLeft){
		Node *rightNode = rootedNode->right;
		Node *rightNodechild = rightNode->left;
		
		rightNode->left = rootedNode;
		rootedNode->right = rightNodechild;
		
		rootedNode->height = 1 + max(nodeHeight(rootedNode->left),
									nodeHeight(rootedNode->right));
		
		rightNode->height = 1 + max(nodeHeight(rightNode->left),
									nodeHeight(rightNode->right));
		
		if(parent){
			isLeft ? parent->left = rightNode : parent->right = rightNode;
		}
		else{
			root = rightNode;
		}
	}
	
	void rightRotate(Node *rootedNode, Node *parent, bool isLeft){
		Node *leftNode = rootedNode->left;
		Node *leftNodechild = leftNode->right;
		
		leftNode->right = rootedNode;
		rootedNode->left = leftNodechild;
		
		rootedNode->height = 1 + max(nodeHeight(rootedNode->left),
									nodeHeight(rootedNode->right));
		
		leftNode->height = 1 + max(nodeHeight(leftNode->left),
									nodeHeight(leftNode->right));
		
		if(parent){
			isLeft ? parent->left = leftNode : parent->right = leftNode;
		}
		else{
			root = leftNode;
		}
	}
	
	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 *minNd = minNode(rt->right);
				rt->data = minNd->data;
				deleteNodeHelper(rt->right, rt, rt->data, false);
			}
			
			return true;
		}
		
		bool result=false;
		
		if(val < rt->data){
			result = deleteNodeHelper(rt->left, rt, val, true);
		}
		else{
			result = deleteNodeHelper(rt->right, rt, val, false);
		}
		
		/*======================= Re-Balancing =========================*/
		rt->height = 1 + max(nodeHeight(rt->left), nodeHeight(rt->right));
		
		int balance_fact = balanceFactor(rt);
		
		if(balance_fact > 1 && balanceFactor(rt->left) >= 0){//LL rotation
			rightRotate(rt, parent, isLeft);
		}
		
		else if(balance_fact < -1 && balanceFactor(rt->right) <= 0){//RR rotation
			leftRotate(rt, parent, isLeft);
		}
		
		else if(balance_fact < -1 && balanceFactor(rt->right) > 0){//RL rotation
			rightRotate(rt->right, rt, false);
			leftRotate(rt, parent, isLeft);
		}
		
		else if(balance_fact > 1 && balanceFactor(rt->left) < 0){//LR rotation
			leftRotate(rt->left, rt, true);
			rightRotate(rt, parent, isLeft);
		}
		/*======================= Re-Balancing =========================*/
		
		return result;
	}
	
	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);
	}
	
	Node *minNode(Node *rt){
		if(!rt->left){
			return rt;
		}
 
		return minNode(rt->left);
	}
 
	Node *maxNode(Node *rt){
		if(!rt->right){
			return rt;
		}
 
		return maxNode(rt->right);
	}
	
	void heightWiseTraversal(){
		if(!root){
			cout<<"The tree is empty!!\n";
			return;
		}
		
		int count=0, hgt = root->height;
		
		queue<Node*> qu;
		qu.push(root);
		
		cout<<"The elements at the,\n";
		
		while(!qu.empty()){
			
			int n = qu.size();
			
			cout<<"Height-"<<hgt--<<": ";
			
			while(n--){
				
				Node *temp = qu.front(); qu.pop();
				
				cout<<temp->data<<" "; ++count;
				
				if(temp->left){
					qu.push(temp->left);
				}
				
				if(temp->right){
					qu.push(temp->right);
				}
			}
			
			cout<<"\n";
		}
		
		cout<<"Total # nodes in the tree are(n): "<<count<<"\n";
		cout<<"Height of the tree is: "<<floor(log2(count))<<" { = O(log2(n)) }\n";
	}
	
	void searchNode(Node *rt, int &val){
		if(!root){
			cout<<"The tree is empty!!\n";
			return;
		}
		
		if(!rt || rt->data == val){
			cout<<"Element "<<val<<(rt ? " ": " not ")<<"found for search.\n";
			return;
		}
 
		if(val < rt->data)
			searchNode(rt->left, val);
		else
			searchNode(rt->right, val);
	}
};

int main() {
	int opt, val;
 
	AVLTree tree;
 
	cout<<"Operations available on AVL tree are:\n";
	cout<<"1. Insert an element\n2. Search an element\n3. Delete an element\n"
	"4. Minimum element in tree\n5. Maximum element in tree\n"
	"6. InOrder traversal\n7. PreOrder traversal\n8. PostOrder traversal\n"
	"9. Height wise traversal\n10. Exit\n";
	cout<<"************************************************\n";
	while(true){
		cin>>opt;
		switch(opt){
			case 1:
				cin>>val;
				tree.insertNode(val);
				cout<<"Element "<<val<<" is inserted into the AVL tree.\n";
				break;
			case 2:
				cin>>val;
				tree.searchNode(tree.root, val);
				break;
			case 3:
				cin>>val;
				cout<<"Element "<<val<<(tree.deleteNode(val) ? " is deleted.\n": " not found for delete.\n");
				break;
			case 4:
				cout<<"The minimum element in the AVL tree is: "<<tree.minNode(tree.root)->data<<"\n";
				break;
			case 5:
				cout<<"The maximum element in the AVL tree is: "<<tree.maxNode(tree.root)->data<<"\n";
				break;
			case 6:
				cout<<"InOrder: ";
				tree.inOrder(tree.root); cout<<"\n";
				break;
			case 7:
				cout<<"PreOrder: ";
				tree.preOrder(tree.root); cout<<"\n";
				break;
			case 8:
				cout<<"PostOrder: ";
				tree.postOrder(tree.root); cout<<"\n";
				break;
			case 9:
				tree.heightWiseTraversal();
				break;
			case 10:
				exit(0);
		}
		cout<<"************************************************\n";
	}
	return 0;
}