public class AVLTree
{
	private Node root;

	private class Node{
		private int val;
		private Node left, right;

		public Node(int val)
		{
			this.val = val;
		}

		public Node getLeft()
		{
			return left;
		}

		public Node getRight()
		{
			return right;
		}

		public int getVal()
		{
			return val;
		}

		public void setLeft(Node node)
		{
			left = node;
		}

		public void setRight(Node node)
		{
			right = node;
		}

		public void setVal(int x)
		{
			val = x;
		}

	}

	public void add(int n)
	{
		if (root == null) { root = new Node(n); }
		else { add(root, n); }
	}

	public void add(Node node, int n)
	{
		if (n == node.getVal()) {
			System.out.println("Already exists");
			return; }
		else if (n < node.getVal()) {
			if (node.getLeft() == null) { node.setLeft(new Node(n)); }
			else { add(node.getLeft(), n); }
		}

		else if (n > node.getVal()) {
			if (node.getRight() == null) { node.setRight(new Node(n)); }
			else { add(node.getRight(), n); }
		}
	}

	public boolean search(int n)
	{
		if (root.getVal() == n) { return true; }
		else { search(root, n); }

		return false;
	}

	public boolean search(Node node, int n)
	{
		if (n == node.getVal()) { return true; }
		else if (n < node.getVal()) {
			if (node.getLeft() == null) { return false; }
			else { search(node.getLeft(), n); }
		}
		else if (n > node.getVal()) {
			if (node.getRight() == null) { return false; }
			else { search(node.getRight(), n); }
		}

		return false;
	}

	public int remove(int n)
	{
		if (root == null) {
			System.out.println("empty tree");
			return -1;
		}
		else { remove(root, n); }

		return 0;
	}

	public void remove(Node node,int n)
	{
		if (node.getVal() == n)
		{
			if (isLeaf(node)) // if node is leaf
			{
				node = null;
			}

			else if (hasTwoChildren(node)) // if node has 2 children
			{
				if (isLeaf(node.getRight()))
				{
					swapNode(node, node.getRight());
					remove(node.getRight(), node.getRight().getVal());
				}
				else if (node.getRight().getLeft() != null)
				{
					swapNode(node, node.getRight().getLeft());
					remove(node.getRight().getLeft(), node.getRight().getLeft().getVal());
				}
				else if (node.getRight().getRight() != null)
				{
					swapNode(node, node.getRight());
					remove(node.getRight(), node.getRight().getVal());
				}
			}


		}
		else if (n < node.getVal())
		{
			if (isLeaf(node.getLeft()))
			{
				node.setLeft(null);
			}
			else
			{
				remove(node.getLeft(), n);
			}
		}
		else if (n > node.getVal())
		{
			if (isLeaf(node.getRight()))
			{
				node.setRight(null);
			}
			else
			{
				remove(node.getRight(), n);
			}
		}
	}

	public boolean isLeaf(Node node)
	{
		if (node.getRight() == null && node.getLeft() == null) { return true; }
		return false;
	}

	public boolean hasTwoChildren(Node node)
	{
		if (node.getRight() != null && node.getLeft() != null) { return true;	}
		return false;
	}

	public void swapNode(Node n1, Node n2)
	{
		int x1 = n1.getVal();
		int x2 = n2.getVal();

		n1.setVal(x2);
		n2.setVal(x1);
	}

	public void printTree()
	{
		if (root == null) { return; }
		else {
			printTree(root, 0);
		}
	}

	public void printTree(Node node, int n)
	{
		String s = "";
		for (int i = 0; i < n; i++)
		{
			s += "     ";
		}

		if (node.getRight() != null)
		{
			printTree(node.getRight(), n + 1);
		}

		s += node.val;
		System.out.println(s);

		if (node.getLeft() != null)
		{
			printTree(node.getLeft(), n + 1);
		}
	}

}