/* topcse - Diagonal Printing of Binary Tree ; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* binary search tree */
class bstree
{
	bstnode root;
	public class bstnode
		{
	      int data;
	      bstnode left;
	      bstnode right;
	      bstnode() {data = 0 ; left = null; right = null;}
	      bstnode(int data1) { data = data1; left = null; right = null;}
		}

	bstree() { root = null;}
	
	/* inroder traversal */
    void inorder(bstnode t)
    {
    	if (t!= null)
    	{
    	   inorder(t.left);
    	   System.out.print(t.data + " ");
    	   inorder(t.right); 
    	}
    }
    
    /* create the binary tree */
    void create ( int a[], int n)
    {
    	for (int i = 0; i< n; i++)
    	{
    		//System.out.print("i=" +i + "data= "+ a[i]);
    	   this.root = createTreeRec(this.root, a[i]);    			
    	}
    }
    
    /* create tree recursive */
    bstnode createTreeRec(bstnode t, int data)
    { 
    	if (t == null)
    	{
    		bstnode temp = new bstnode(data);
    		temp.data=data;
    		//System.out.print("debug= " + temp.data);
    		return temp;
    	}
    	else 
    	{
    		if (data < t.data)
    	      t.left=createTreeRec(t.left, data);
    	 	else
    	 	 t.right=createTreeRec(t.right, data);
    	 	return t;
    	}
    }
    
 /** print tree diagonally */
    void printTreeDiagonally(bstnode t)
    {
    	
        Queue  <bstnode> q = new java.util.LinkedList<>();
    	
    	if (t == null)
    	   return;

    	/* add null terminal before , this will help to determine when to insert new line */
    	q.add(null);

    	/* starting from root as t, enqueue left elemnt, print data and move t to right ot it */
    	do{ 
    		/* move till extreme left of current node */
    	    while(t != null )
    	    {
    	      /*enq left of node if it is not null */	
    	      if (t.left != null)
    	    	q.add(t.left);
    	    	
    	      /* print data */
    	      System.out.print(" "+ t.data);
    	      
    	      /* move to  right child of node */ 
    	      t=t.right;	  
    	    }
    	    
    	    /* if right child is null then we have two options - 
    	     *  1. If next element in queue is null then it means we need to print new line character, 
    	     *      deq null character, dequeue next element make it as current node.
    	     *  2. If there are  non-null element in queue then dequeue it make it as current node.     
    	     */
    	    
    	    if (!q.isEmpty())
    	    {
    	        t = q.remove();
    	    	
    	    	if ( t==null)
    	    	{
    	    	  /* print new line and insert null character again after removing top elem, else break if queue is empty. */	
    	    	  System.out.println("\n");
    	    	  
    	    	  if (!q.isEmpty())
    	    	  {
    	    		  t = q.remove();
    	    	  }
    	    	  else
    	    		  break;
    	    	  
    	    	  /* add null again indicating begening of new line */
    	    	  q.add(null);
    	    	}
    	    }
    	       	    
    	}while(!q.isEmpty());
    }
}


/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
	   int a[] = {15,9,20,7,12,17,25,3,8,10,14,16,19,23,28};

    	bstree bst = new bstree();
    	bst.create(a, a.length);
    	System.out.println("\nTree Inorder data : ");
    	bst.inorder(bst.root);
    	 
    	 /* print tree diagonally */
            System.out.println("\nDiagonal Printing of Tree: ");
            bst.printTreeDiagonally(bst.root);
	}
}