Node* rotateR(Node* n) {
		n->left->right = n;
		Node* temp = n->left;		
		n->left = NULL;
		return temp;
	}

	Node* rotateL(Node* n) {
		n->right->left = n;
		Node* temp = n->right;
		n->right = NULL;
		return temp;
	}

	Node* balance(Node* n)
	{
		if(!n) return n;
		int factor = setHeight(n->left)-setHeight(n->right);
		if(factor < -1) {
			int subfactor = setHeight(n->right->left)-setHeight(n->right->right);
			if(subfactor<=0) return rotateL(n);
			else if(subfactor==1) {
				n->right = rotateR(n->right);
				return rotateL(n);
			}
		}
		else if (factor > 1) {
			int subfactor = setHeight(n->left->left)-setHeight(n->left->right);
			if(subfactor>=0) n = rotateR(n);
			else if(subfactor==-1) {
				n->left = rotateL(n->left);
				return rotateR(n);
			}
		}
		checkHeights(root);
		return n;
	}

	void insert(ItemType item)
	{
		root = insert(root, item);
		cout << "After setting root:  " << endl; print(cout);
	}

	Node* insert(Node* t, const ItemType& item)
	{	
		checkHeights(t);
		if(t==NULL) 
		{
			Node* newNode = new Node(item);
			if(size==0) 
			{
				root = newNode;
				cout << "Root was successfully set." << endl;
			}
			size++;
			return newNode;
		}
		else if (item< t->item)	
		{
			t->left = insert(t->left, item);
		}
		else if (item> t->item)	
		{
			t->right = insert(t->right, item);
		}
		cout << "Before balancing: " << endl; print(cout);
		t = balance(t);
		checkHeights(t);
		return t;
	}