public class BinaryTree
{
	////////////////////////////////////////////////////////////
	private class Node
	{
		private Node	left;
		private int	obj;
		private Node	right;
		
		public Node(Node left, int obj, Node right)
		{
			this.setLeft(left);
			this.setObj(obj);
			this.setRight(right);
		}
		
		public Node(int obj)
		{
			this(null, obj, null);
		}

		public void setLeft(Node left) { this.left = left; }
		public Node getLeft() {	return this.left; }
		public void setObj(int obj) { this.obj = obj; }
		public int getObj() { return this.obj; }
		public void setRight(Node right) { this.right = right; }
		public Node getRight() { return this.right; }
		
		public String toString() { return this.obj+""; }
	}
	////////////////////////////////////////////////////////////
	
	private Node root;
	
	public BinaryTree()
	{
		this.root = null;
	}
	
	//////////////////////////////////////////////////////////////
	
	private void insert(int obj, Node n)
	{
		if (obj == n.getObj()) { return; }
		
		if (obj < n.getObj())
		{
			if (n.getLeft() == null)	{ n.setLeft(new Node(obj)); }
			else				{ this.insert(obj, n.getLeft()); }
		}
		else
		{
			if (n.getRight() == null)	{ n.setRight(new Node(obj)); }
			else				{ this.insert(obj, n.getRight()); }
		}
	}
	
	public void insert(int obj)
	{
		if (this.root == null)	{ this.root = new Node(obj); }
		else			{ this.insert(obj, this.root); }
	}
	
	//////////////////////////////////////////////////////////////
	
	private Node search(int obj, Node n)
	{
		if (n == null)		{ return null; }
		if (obj == n.getObj())	{ return n; }
		
		if (obj < n.getObj())
		{
			return this.search(obj, n.getLeft());
		}
		else
		{
			return this.search(obj, n.getRight());
		}
	}
	
	public Node search(int obj)
	{
		return this.search(obj, this.root);
	}
	//////////////////////////////////////////////////////////////
    
	private int minValue(Node n)
	{
		if (n.getLeft() == null)
		{
			return n.getObj();
		}
		else return this.minValue(n.getLeft());
	}
	
	private Node delete(int obj, Node n)
	{
		if (n != null)
		{
			if (obj < n.getObj())
			{
				n.setLeft(this.delete(obj, n.getLeft()));
			}
			else if (obj > n.getObj())
			{
				n.setRight(this.delete(obj, n.getRight()));
			}
			else if (n.getLeft() != null && n.getRight() != null)
			{
				n.setObj(this.minValue(n.getRight()));
				n.setRight(this.delete(n.getObj(), n.getRight()));
			}
			else
			{
				if (n.getLeft() != null)
				{
					n = n.getLeft();
				}
				else
				{
					n = n.getRight();
				}
			}
		}
		
		return n;
	}
	
	public void delete(int obj)
	{
		this.root = this.delete(obj, this.root);
	}
	
	//////////////////////////////////////////////////////////////
	
	private void inorder(Node n)
	{
		if (n.getLeft() != null) { this.inorder(n.getLeft()); }
		
		System.out.println(n.getObj());
		
		if (n.getRight() != null) { this.inorder(n.getRight()); }
	}
	
	public void inorder()
	{
		this.inorder(this.root);
	}
	
	//////////////////////////////////////////////////////////////
	
	private void preorder(Node n)
	{
		System.out.println(n.getObj());
		
		if (n.getLeft() != null) { this.preorder(n.getLeft()); }
		
		if (n.getRight() != null) { this.preorder(n.getRight()); }
	}
	
	public void preorder()
	{
		this.preorder(this.root);
	}
	
	//////////////////////////////////////////////////////////////
	
	private void postorder(Node n)
	{
		if (n.getLeft() != null) { this.postorder(n.getLeft()); }
		
		if (n.getRight() != null) { this.postorder(n.getRight()); }
		
		System.out.println(n.getObj());
	}
	
	public void postorder()
	{
		this.postorder(this.root);
	}
	
	//////////////////////////////////////////////////////////////
	
	public void levelorder()
	{
		java.util.Queue<Node> q = new java.util.LinkedList<Node>();
		q.offer(this.root);
		
		while (!q.isEmpty())
		{
			Node n = q.poll();
			System.out.println(n.getObj());
			
			if (n.getLeft() != null) { q.offer(n.getLeft()); }
			
			if (n.getRight() != null) { q.offer(n.getRight()); }
		}
	}
	
	//////////////////////////////////////////////////////////////
	
	public static void main(String[] args)
	{
		BinaryTree BT = new BinaryTree();
		
		BT.insert(5);
		BT.insert(3);
		BT.insert(2);
		BT.insert(4);
		BT.insert(8);
		BT.insert(6);
		BT.insert(9);
		BT.insert(1);
		
		/*
								5
						3				8
					2		4		6		9
				1
		*/
		
		System.out.println(BT.search(5)); // 5
		System.out.println(BT.search(3)); // 3
		System.out.println(BT.search(8)); // 8
		System.out.println(BT.search(7)); // null
		
		System.out.println("---------------------");
		System.out.println("INORDER:");
		System.out.println("---------------------");
		
		//BT.inorder();
		
		System.out.println("---------------------");
		System.out.println("PREORDER:");
		System.out.println("---------------------");
		
		//BT.preorder();
		
		System.out.println("---------------------");
		System.out.println("POSTORDER:");
		System.out.println("---------------------");
		
		//BT.postorder();
		
		System.out.println("---------------------");
		System.out.println("LEVELORDER:");
		System.out.println("---------------------");
		
		//BT.levelorder();
		
		System.out.println("---------------------");
		
		BT.delete(0);
		BT.delete(9);
		
		BT.levelorder();
		
		System.out.println("---------------------");
		
		BT.delete(5);
		
		BT.levelorder();
	}
}