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

class BinaryTreeNode
{
public:
	int data;
	BinaryTreeNode * left;
	BinaryTreeNode *right;
	int height;

	// BinaryTreeNode()
	// {
	// 	data = 0;
	// 	left = NULL;
	// 	right = NULL;
	// }
	BinaryTreeNode(int data)
	{
		this->data = data;
		left = NULL;
		right = NULL;
	}
	~BinaryTreeNode()
	{
		delete left;
		delete right;
	}

};


class AVL
{
public:
	BinaryTreeNode *root;
	AVL()
	{
		this->root = NULL;
	}


	int getheight(BinaryTreeNode* root)
	{
		if (root == NULL)
			return 0;

		return 1 + max(getheight(root->left) , getheight(root->right));
	}

	int getbalanceFactor(BinaryTreeNode* node)
	{
		if ( node == NULL)
			return 0;
		return getheight(node->left) - getheight(node->right);
	}

	BinaryTreeNode* rightRotate(BinaryTreeNode* y)
	{


		/*

			 	y           x
			   / \		   / \
			  x   T3 ---->T1  y
			 / \			 / \
			T1  T2			T2  T3
			*/
		BinaryTreeNode* x = y->left;
		BinaryTreeNode *T2 = x->right;
		// T1 & T3 not required because their ptr not changes
		x->right = y;
		y->left = T2;
		//updation to heights
		// y->height = 1 + max(getHeight(y->left) , getHeight(y->right));
		// X->height = 1 + max(getHeight(x > left) , getHeight(x->right));
		return x;
		//as now x is root node
	}
	BinaryTreeNode* leftRotate(BinaryTreeNode* x)
	{
		/*  	y           x
			   / \		   / \
			  x   T3 <--- T1  y
			 / \			 / \
			T1  T2			T2  T3
			*/
		//before rotation
		BinaryTreeNode* y = x->right;
		BinaryTreeNode *T2 = y->left;
		// T1 & T3 not required because their ptr not changes
		//changes to rotation
		y->left = x;
		x->right = T2;
		//updation to heights
		// y->height = 1 + max(getHeight(y->left) , getHeight(y->right));
		// X->height = 1 + max(getHeight(x > left) , getHeight(x->right));
		return y;
		//as now y is root node
	}


// 1. insert
private:
	BinaryTreeNode * insert(BinaryTreeNode* node, int data)
	{
		if ( node == NULL)
		{
			BinaryTreeNode* newnode = new BinaryTreeNode (data);
			return newnode;
		}

		if (data <= node->data)
			node->left = this->insert( node->left , data);
		else if (data > node->data)
			node->right = this->insert(node->right , data);
		else
			return node;

		// node->height = 1 + max(getHeight(node > left) , getHeight(node->right));
		// //height update krni padegi as it is req in balfac

		int balfac =  getbalanceFactor(node) ;
		// left left case ..bf= leftH -rightH >1
		if (balfac > 1 && data < node->left->data)
		{	//insertion takes place at LST
			return this->rightRotate(node);
		}

		//right right case , bf= leftH -rightH < -1
		if (balfac < -1 && node->right->data < data)
		{
			return this->leftRotate(node);
		}

		//left rightcase,bf= leftH -rightH >1
		if (balfac > 1 && node->left->data < data)//bf>1 tabhi root k left me imbal
		{
			/*
				 r= 30          30     25
				   /   			/	  /	  \
				 20	   	   	  25     20	  30
				  \			 /
			  data=25		20
			*/

			node->left = leftRotate(node->left); //
			return this->rightRotate(node);
		}


		//right left case bf= leftH -rightH <-1
		if (balfac > 1 && node->left->data < data)//bf>1 tabhi root k left me imbal
		{
			/*
				 r= 20           20         25
				      \   		   \       /  \
				 	  30	   	    25    20   30
					 /	             \
			  data=25		          30
			*/

			node->right = rightRotate(node->right); //
			//now RR imbalance
			return this->leftRotate(node);
		}
		return node;
	}




public:
	BinaryTreeNode* insert ( int data)
	{
		// BinaryTreeNode *node = new BinaryTreeNode(data);
		this->root = insert(this->root , data);
		return  root;
	}



	//2. delete : trick think node as leaf or any internal node
private:
	BinaryTreeNode * deleteData(BinaryTreeNode* node , int data)
	{
		if (node == NULL)
			return NULL;
		if (data < node->data)
		{
			node ->left = deleteData(node->left , data);
			return node;
		}
		else if (node->data < data)
		{
			node->right = deleteData(node -> right , data);
			return node;
		}
		else // if value matche
		{
			if (node->left == NULL && node->right == NULL) //a leaf
			{
				delete node;
				return NULL;
			}
			else if (node->left == NULL)
			{
				BinaryTreeNode *rightsubtree = node->right;
				node ->right = NULL;
				delete node;
				return rightsubtree;
			}
			else if (node->right == NULL)
			{
				BinaryTreeNode *leftsubtree = node->left;
				node->left = NULL;
				delete node;
				return leftsubtree;
			}
			else // both rst and lst exists
			{
				BinaryTreeNode * minNode = node ->right;
				while (minNode->left != NULL)
				{
					minNode = minNode->left;
				}
				int minFromRST = minNode->data;
				node->data = minFromRST;
				node->right = deleteData(node->right, minFromRST);
				return node;
			}
		}


		int balfac = getbalanceFactor(node);

		if (balfac == 2 && getbalanceFactor(node->left ) >= 0)
		{
			/*
				 r= 30         			 30                 30      20
				   / \  				/ \	                /	   /  \
				 20	  40**del 	or    20   40 **del =     20	  10   30
				 /\					 /					 /
			   10  25				10					10
			*/
			// 25 case will be taken care by rightrotate

			BinaryTreeNode*newnode = rightRotate(node);
			return newnode;
		}
		else if (balfac == 2 && getbalanceFactor(node->left) == -1)
		{
			/*
				 r= 30         			 30                        25
				   / \  				/ 	                 	  /  \
			(-1) 20	  40**del or (-1) 20  	lr imbalance	=    20	  30
				  \					 	\
			      25					 25
			*/
			// 25 case will be taken care by rightrotate

			node->left = leftRotate(node->left);
			BinaryTreeNode*newnode = rightRotate(node);
			return newnode;
		}
		else if (balfac == -2 && getbalanceFactor(node->right) <= 0)
		{
			/*
			 20			20		   	 30
			/ \			/ \		     / \
			del 10  30  del(10) 30        20  40
			   /\			 \
			  25 40 		 40

			  // 25 case will be taken care by leftrotate
			*/
			BinaryTreeNode * newnode = leftRotate(node);
			return newnode;
		}
		else if (balfac == -2 && getbalanceFactor(node->right) == 1)
		{
			/*
			 20			 	 20                25
			/ \			 	   \			   / \
			del 10  30 (1)          30	rl imbal  20  30
			   / 			 	/
			  25 		  	  25
			  	*/
			node->right  =  leftRotate(node->right);
			BinaryTreeNode * newnode = leftRotate(node);
			return newnode;
		}
	}
public:
	BinaryTreeNode* deleteData( int data)
	{
		this->root = deleteData(this->root , data);
		return root;
	}


	//3.search
private:
	bool search(BinaryTreeNode* node , int data)
	{
		if (node == NULL)
			return false;
		if (node->data == data)
			return true;
		else if (node->data < data)
			return search (node->right , data);
		else
			return search(node->left , data);
	}
public:
	bool search(int data)
	{
		return search(root, data);
	}



	//4. occurences
private :
	int count_occurence(BinaryTreeNode*node , int data)
	{
		if (node == NULL)
			return 0;

		if (node ->data == data)
			return 1 + count_occurence(node->left, data) + count_occurence(node->right, data);
		else if (node->data < data)
			return count_occurence(node->right, data);
		else if (data < node->data )
			return count_occurence(node->left, data);
		return 0;
	}

public:
	int count_occurence(int data)
	{
		return count_occurence(this->root , data);
	}

private:
	int upper_bound(BinaryTreeNode*node, int data)
	{
		if (node == NULL)
			return 0;

		//leaf data=15  leaf=14(node->data)(rightmost)
		if (node->left == NULL && node->right == NULL && node->data <= data)
		{
			return 0;
		}

		//data=12 ex=  null (12) 13(root)  or   11 (12) 13(root) or 12 (12) 13(root)
		if ((data < node->data && node->left == NULL) || (node->left->data <= data && data < node->data))
		{
			return node->data;
		}
		//data=12  11(root) (12)  or   12(root) (12)
		if (node->data <= data)
		{	//node->left->data se compare wali cond already checked above
			return upper_bound(node->right, data);
		}
		else if (data < node->data)
		{
			//data=12  14(root->left)  15(root)
			return upper_bound(node->left , data);
		}
		return 0;
	}
public:
	int upper_bound(int data)
	{
		return upper_bound(this->root , data);
	}


private:
	int lower_bound(BinaryTreeNode*node, int data)
	{
		if (node == NULL)
			return 0;

		//reachd to leaf data =14 leaf=15(node->data) leftmost node
		if (node->left == NULL && node->right == NULL &&  data < node->data )
		{
			return 0;
		}
		//itsef a leaf
		if (node->left == NULL  && node->right == NULL &&  data == node->data)
			return node->data;

		//data=12  11(root) null or   11(root) 13  or  12(root)   13
		if ((node->data < data   && node->right == NULL) || (node->data < data && data < node->right->data))
		{
			return node->data;
		}
		//data=12  12 13(root)  or   (12)   12(root)
		if ( data <= node->data)
		{
			return lower_bound(node->left, data);
		}
		else if ( node->data < data)
		{	//node->right->data se compare wali cond already checked above
			//data=12  10(root)  11(root->right) 12
			return lower_bound(node->right, data);
		}
		return 0;
	}
public:
	int lower_bound(int data)
	{
		return lower_bound(this->root , data);
	}

public:
	int lesser_bound(BinaryTreeNode*node , int data)
	{
		if (node == NULL)
			return 0;

		//reachd to leaf data =14 leaf=15(node->data) leftmost node
		if (node->left == NULL && node->right == NULL &&  data < node->data )
		{
			return 0;
		}
		//itsef a leaf
		if (node->left == NULL  && node->right == NULL &&  data == node->data)
			return 0;

		//data=12  11(root) null or   11(root) 13  or  12(root)   13
		if ((node->data < data   && node->right == NULL) || (node->data < data && data < node->right->data))
		{
			return node->data;
		}
		//data=12  12 13(root)  or   (12)   12(root)
		if ( data <= node->data)
		{
			return lesser_bound(node->left, data);
		}
		else if ( node->data < data)
		{	//node->right->data se compare wali cond already checked above
			//data=12  10(root)  11(root->right) 12
			return lesser_bound(node->right, data);
		}
		return 0;
	}



private:
	int closest_element(BinaryTreeNode*node , int data)
	{
		if (node == NULL)
			return -1;
		if (node->data == data)
			return node->data;
		int x = upper_bound(node, data);
		int y = lesser_bound(node, data);
		//y----------data ---------x
		if (y != 0 && x != 0)
			return (data - y) > (x - data) ? x : y;
		else if (y == 0 && x != 0)
			return x;
		else
			return y;

	}
public:
	int closest_element(int data)
	{
		return closest_element(this->root , data);
	}


private:
	BinaryTreeNode* Element_Kth_largest(BinaryTreeNode*node , int &k)
	{
		// if (node == NULL || c > k )
		// 	return -1;
		// //reverse inorder traversal
		// Element_Kth_largest(node->right, k, c );
		// c++;
		// if (k == c)
		// 	return node->data;
		// Element_Kth_largest(node->left, k , c);
		// return -1;
		if (node == NULL)
			return NULL;

		BinaryTreeNode* newnode = Element_Kth_largest(node->right, k);
		if (newnode  != NULL)
			return newnode;
		k--;

		if (k == 0)
			return node;

		return Element_Kth_largest(node->left, k);
	}
public:
	int Element_Kth_largest(int k)
	{

		BinaryTreeNode*newnode = Element_Kth_largest(this->root, k );
		int c = -1;
		if (newnode == NULL)
			return c;
		else
			c = newnode->data;
		return c;
	}

private:
	int count_range(BinaryTreeNode*node, int eLeft, int eRight)
	{
		if (node == NULL)
			return 0;
		// if (node->data == eLeft && node->data == eRight)
		// 	return 1;

		int count = 0;
		// Special Optional case for improving efficiency
		// if (eLeft <= node->data  && node->data <= eRight)
		// 	return 1 + count_range(node->left , eLeft, eRight) + count_range(root->right , eLeft, eRight);

		if (eLeft <= node->data  && node->data <= eRight)
			count += 1;
		count += count_range(node->left , eLeft, eRight);

		return count + count_range(node->right , eLeft, eRight);
		// else if (node->data < eLeft )
		// 	return count_range(node->right, eLeft, eRight)	;
		// else
		// 	return count_range(root->left , eLeft, eRight);
	}
public:
	int count_range(int eLeft , int eRight)
	{
		return count_range(this->root, eLeft, eRight);
	}


};



void preorder(BinaryTreeNode * root)
{
	if (root == NULL)
		return;
	cout << root->data << " ";
	preorder(root->left);
	preorder(root->right);
}
void inorder(BinaryTreeNode * root)
{
	if (root == NULL)
		return;
	inorder(root->left);
	cout << root->data << " ";
	inorder(root->right);
}



int main()
{
#ifdef ONLINE_JUDGE
	freeopen("input.txt", "r", stdin);
	freeopen("output.txt", "r", stdin);
#endif


	AVL obj_avl;


	//segmentationfault state
	// obj_avl.root = obj_avl.insert(30);
	// obj_avl.root = obj_avl.insert(31);
	// obj_avl.root = obj_avl.insert(30);
	// obj_avl.root = obj_avl.insert(30);
	// obj_avl.root = obj_avl.insert(30);
	// obj_avl.root = obj_avl.insert(60);
	// obj_avl.root = obj_avl.insert(30);
	// obj_avl.root = obj_avl.insert(30);
	// obj_avl.root = obj_avl.insert(30);
	// obj_avl.root = obj_avl.insert(30);
	// obj_avl.root = obj_avl.insert(40);


	// int option;
	// do {
	// 	cout << "What operation do you want to perform? " <<
	// 	     " Select Option number. Enter 0 to exit." << endl;
	// 	cout << "1. Insert Node" << endl;
	// 	cout << "2. Delete Node" << endl;
	// 	cout << "3. Search Node" << endl;
	// 	cout << "4.  " << endl;
	// 	cout << "5.  " << endl;
	// 	cout << "6.  " << endl;
	// 	cout << "0. Exit Program" << endl;
	// 	cin >> option;
	// 	//Node n1;
	// 	int val;

	// 	switch (option) {
	// 	case 0:
	// 		break;
	// 	case 1:
	// 		cout << "Enter VALUE of TREE NODE to INSERT in AVL Tree: ";
	// 		cin >> val;

	// 		obj_avl.root = obj_avl.insert(val);
	// 		cout << endl;
	// 		break;

	// 	case 2:
	// 		cout << "Enter VALUE of TREE NODE to delete in AVL Tree: ";
	// 		cin >> val;
	// 		obj_avl.root = obj_avl.deleteData(val);
	// 		break;


	// 	case 3:
	// 		cout << "Enter VALUE of TREE NODE to search in AVL: ";
	// 		cin >> val;
	// 		cout << obj_avl.search(val);
	// 		break;

	// 	default:
	// 		cout << "Enter Proper Option number " << endl;
	// 	}

	// } while (option != 0);




	int n = 5;
	int ins[11] = {1, 12, 23, 34, 45, 63, 67, 30, 89, 39, 4};
	for (int i = 0; i < n; ++i)
	{
		obj_avl.root = obj_avl.insert(ins[i]);
	}


	cout << endl;
	cout << "\npreorder :";
	preorder(obj_avl.root);
	cout << "\ninorder  :";
	inorder(obj_avl.root);
	cout << endl;

	int arr[10] = { -1, 9, 20, 23 , 44 , 5, 6 , 40, 50, 67 };
	int k = 7;
	int lar[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	// for (int i = 0; i < k; ++i)
	// {
	// 	int u;
	// 	int e = lar[i];
	// 	cout << "\nkth largest element : " << e  ;
	// 	u = obj_avl.Element_Kth_largest(e);
	// 	cout << " is:" << u;
	// }
	cout << endl;

	for (int i = 2; i < 8; ++i)
	{
		int l = arr[i];
		int h = arr[i + 1];
		if (l > h)
			swap(l, h);
		cout << "Count of nodes between [" << l << ", " << h << "] is " << obj_avl.count_range(l, h) << endl;
	}

	// for (int i = 0; i < k; ++i)
	// {
	// 	int u;
	// 	int e = arr[i];
	// 	cout << "\nclosest element to : " << e  ;
	// 	u = obj_avl.closest_element(e);
	// 	cout << " is:" << u;
	// }
	// cout << endl;

	// for (int i = 0; i < k; ++i)
	// {
	// 	int u;
	// 	int e = arr[i];
	// 	cout << "\nlower bound of : " << e  ;
	// 	u = obj_avl.lower_bound(e);
	// 	cout << " is:" << u;
	// }
	// cout << endl;
	// for (int i = 0; i < k; ++i)
	// {
	// 	int u;
	// 	int e = arr[i];
	// 	cout << "\nupper bound of :" << e  ;
	// 	u = obj_avl.upper_bound(e);
	// 	cout << ":" << u;
	// }


	// int count_o[10] = {30, 55, 38, 40, 60, 89, 31, 35, 47, 69};
	// for (int i = 0; i < 10; ++i)
	// {
	// 	int s = count_o[i];
	// 	int r  ;

	// 	cout << "\n\ncount:" << s;
	// 	r = obj_avl.count_occurence(s);
	// 	cout << "\nnumber of  " << s << " are :" << r  ;
	// }



	// int find[10] = {30, 55, 38, 40, 60, 89, 31, 35, 47, 69};
	// for (int i = 0; i < 10; ++i)
	// {
	// 	int s = find[i];
	// 	int r = 0;
	// 	cout << "\n\nsearch:" << s;
	// 	r = obj_avl.search(s);
	// 	if (r)
	// 		cout << "\nyes " << s << " is found";
	// 	else
	// 		cout << "\nno. :" << s << " is not found";
	// }


	// cout << endl;
	// cout << "\npreorder :";
	// preorder(obj_avl.root);
	// cout << "\ninorder  :";
	// inorder(obj_avl.root);

	// int del[10] = {50, 38, 60, 56, 3, 30, 60};
	// for (int i = 0; i < 10; ++i)
	// {
	// 	int v = find[i];
	// 	int r = 0;
	// 	cout << "\n\ndelete :" << v << endl;
	// 	r = obj_avl.search(v);
	// 	if (!r)
	// 	{

	// 		cout << "no.    :" << v << " is not found";
	// 	}
	// 	else
	// 	{
	// 		obj_avl.root = obj_avl.deleteData(v);
	// 		cout << "sucessfully deleted :" << v << endl;
	// 		cout << "preorder :";
	// 		preorder(obj_avl.root);
	// 		cout << "\ninorder  :";
	// 		inorder(obj_avl.root);
	// 	}

	// }





	return 0;
}