class Node {
	public Node left;
	public int data;
	public Node right;
//Test
	public Node(int val) 	{
		this.data=val;
	}
}


/**
 * BFS of Tree 
 * @author Prateek
 */
 class PrintTreeBFS {

	/**
	 * for printing BFS (recursive) 
	 * @param root
	 */
	public void printTreeBFS(Node root) {
		if(root==null)
			System.out.println("Empty Tree");
		
		int height=height(root);
		
		for(int i=1 ; i<=height ; i++){
			printLevel(root, i);
			System.out.println();
		}
	}
	
	/**
	 * Prints nodes at a given level
	 * @param root
	 * @param level
	 */
	public void printLevel(Node root, int level) {
			if(root==null)
				return ;
			
			if(level==1)
				System.out.print(root.data + "\t");
	
			printLevel(root.left, level-1) ;
			printLevel(root.right, level-1) ;
	}
	
	/**
	 * @param root of the tree
	 * @return height of the tree
	 */
	public int height(Node root) {
		if(root == null)
			return 0;
		
		int lHeight=height(root.left);
		int rHeight=height(root.right);
		
		return max(lHeight,rHeight) + 1;
	}

	/**
	 * @param val1
	 * @param val2
	 * @return maximum val
	 */
	private int max(int val1, int val2) {
		return val1 > val2 ? val1 : val2;
	}
	
	
	public static void main(String[] args) {
		Node root=new Node(12);

		Node n1=new Node(14);
		Node n2=new Node(18);
		Node n3=new Node(10);
		root.left=new Node(8);
		root.right=new Node(16);
		root.left.left=new Node(6);
		root.left.right=n3;
		root.right.left=n1;
		root.right.right=n2;


		PrintTreeBFS obj=new PrintTreeBFS();
		obj.printTreeBFS(root);
		
	}
}