public class Tree<T> {

	public void print(Node<T> root){
		if(root==null)
			return;
		else{
			print(root.left);
			System.out.println(root.toString());
			print(root.right);
		}
	}

	public int height(Node<T> pos){
		return pos==null ? -1 : pos.height;
	}


	public Node<T> rotateToRight(Node<T> pos){
		Node<T> leftPos = pos.left;
		pos.left = leftPos.right;
		leftPos.right=pos;

		leftPos.height = Math.max(height(leftPos.left), height(leftPos.right))+1;
		pos.height = Math.max(height(pos.left), height(pos.right))+1;

		return leftPos;
	}

	public Node<T> rotateToLeft(Node<T> pos){
		Node<T> rightPos = pos.right;
		pos.right=rightPos.left;
		rightPos.left=pos;

		rightPos.height = Math.max(height(rightPos.left), height(rightPos.right))+1;
		pos.height = Math.max(height(pos.left), height(pos.right))+1;

		return rightPos;
	}


	public Node<T> doubleRotateToRight(Node<T> pos){

		pos.left=rotateToLeft(pos.left);

		return rotateToRight(pos);

	}

	public Node<T> doubleRotateToLeft(Node<T> pos){
		pos.right = rotateToRight(pos.right);

		return rotateToLeft(pos);
	}


	public Node<T> balance(Node<T> pos){
		if(pos==null)
			return pos;

		if(height(pos.left)-height(pos.right) > 1){
			if(height(pos.left.left) >= height(pos.left.right))
				pos = rotateToRight(pos);
			else
				pos = doubleRotateToRight(pos);
		}

		else if(height(pos.right)-height(pos.left) > 1){
			if(height(pos.right.right) >= height(pos.right.left))
				pos=rotateToLeft(pos);
			else
				pos=doubleRotateToLeft(pos);
		}

		pos.height = Math.max(height(pos.left), height(pos.right))+1;

		return pos;
	}

	public Node<T> insert(Node<T> root,T data){
		if(root==null){
			root= new Node<>(data);
			//root.height = Math.max(height(root.left), height(root.right))+1;
			return root;
		}
		if(root.compareTo(data)<0){
			root.right=insert(root.right, data);

			//root.height = Math.max(height(root.left), height(root.right))+1;

			return balance(root);
		}
		if(root.compareTo(data)>0){
			root.left=insert(root.left, data);

			//root.height = Math.max(height(root.left), height(root.right))+1;

			return balance(root);
		}
		else
			return null;
	}

	/*	public Node<T> insertComplete(Node<T> root,T data){
		if(root==null){
			root=  new Node<>(data);
			root.height = Math.max(height(root.left), height(root.right))+1;
			return root;
		}
		if(root.left==null){
			root.left = insertComplete(root.left, data);

			root.height = Math.max(height(root.left), height(root.right))+1;
			return root;
		}
		if(root.right == null){
			root.right = insertComplete(root.right, data);
			root.height = Math.max(height(root.left), height(root.right))+1;

			return root;
		}
		else{
			if(height(root.left)-height(root.right)==0){
				Node<T> pos= root.left;
				if(pos.left != null && pos.right!=null)
					return insertComplete(root.right, data);
				else
					return insertComplete(root.left, data);
			}
			if(height(root.left)-height(root.right)==1){
				Node<T> pos= root.left;
				if(pos.left != null && pos.right!=null)
					return insertComplete(root.right, data);
				else
					return insertComplete(root.left, data);
			}

		}*/
	public void recurInsert(Node<T> root, Node<T> newNode, int height) {
		if (newNode == null) {
			System.out.println("InsertNode is empty, please create new one");
			return;
		}
		else{
			if (height == 1) {
				if (root == null)
					return;
				else if (root.left == null) {
					root.left = newNode;
					System.out.println("left" + newNode.data);
				}
				else {
					root.right = newNode;
					System.out.println("right" + newNode.data);
				}
			}
			else{
				if (root.left != null)
					recurInsert(root.left, newNode, height-1);
				//else (root.rightChild != null)
				//    recurInsert(root.rightChild, newNode, height-1);
				if (root.right != null)
					recurInsert(root.right, newNode, height-1);
			}
		}
	}


	public void printGivenLevel (Node<T> root ,int level){
		if (root == null)
			return;
		if (level == 1)
			System.out.print(root.data + " ");
		else if (level > 1)
		{
			printGivenLevel(root.left, level-1);
			printGivenLevel(root.right, level-1);
		}
	}

	public Node<T> findMax(Node<T> root) {
		if (root.right == null)
			return root;

		return findMax(root.right);

	}

	public Node<T> findMin(Node<T> root) {
		if (root.left == null)
			return root;

		return findMin(root.left);

	}

	public boolean isLeaf(Node<T> data) {
		return (data.left == null && data.right == null);
	}
	public Node<T> delete1(T value, Node<T> node) {
		if (node == null)
			return null;

		if (node.compareTo(value) > 0){
			node.left = delete1(value, node.left);
			node.height = Math.max(height(node.left), height(node.right))+1;

		}
		else if (node.compareTo(value) < 0){
			node.right = delete1(value, node.right);
			node.height = Math.max(height(node.left), height(node.right))+1;

		}
		else {
			if (isLeaf(node))
				return null;

			if (node.right == null)
				return node.left;

			if (node.left == null)
				return node.right;

			Node<T> pos = findMax(node.left);
			node.data = pos.data;
			
			node.left = delete1(node.data, node.left);

		}
		
		return balance(node);
	}


}
