fork download
copy 
  1. /* topcse - Diagonal Printing of Binary Tree ; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* binary search tree */
  8. class bstree
  9. {
  10. 	bstnode root;
  11. 	public class bstnode
  12. 		{
  13. 	      int data;
  14. 	      bstnode left;
  15. 	      bstnode right;
  16. 	      bstnode() {data = 0 ; left = null; right = null;}
  17. 	      bstnode(int data1) { data = data1; left = null; right = null;}
  18. 		}
  19.  
  20. 	bstree() { root = null;}
  21.  
  22. 	/* inroder traversal */
  23.     void inorder(bstnode t)
  24.     {
  25.     	if (t!= null)
  26.     	{
  27.     	   inorder(t.left);
  28.     	   System.out.print(t.data + " ");
  29.     	   inorder(t.right); 
  30.     	}
  31.     }
  32.  
  33.     /* create the binary tree */
  34.     void create ( int a[], int n)
  35.     {
  36.     	for (int i = 0; i< n; i++)
  37.     	{
  38.     		//System.out.print("i=" +i + "data= "+ a[i]);
  39.     	   this.root = createTreeRec(this.root, a[i]);    			
  40.     	}
  41.     }
  42.  
  43.     /* create tree recursive */
  44.     bstnode createTreeRec(bstnode t, int data)
  45.     { 
  46.     	if (t == null)
  47.     	{
  48.     		bstnode temp = new bstnode(data);
  49.     		temp.data=data;
  50.     		//System.out.print("debug= " + temp.data);
  51.     		return temp;
  52.     	}
  53.     	else 
  54.     	{
  55.     		if (data < t.data)
  56.     	      t.left=createTreeRec(t.left, data);
  57.     	 	else
  58.     	 	 t.right=createTreeRec(t.right, data);
  59.     	 	return t;
  60.     	}
  61.     }
  62.  
  63.  /** print tree diagonally */
  64.     void printTreeDiagonally(bstnode t)
  65.     {
  66.  
  67.         Queue  <bstnode> q = new java.util.LinkedList<>();
  68.  
  69.     	if (t == null)
  70.     	   return;
  71.  
  72.     	/* add null terminal before , this will help to determine when to insert new line */
  73.     	q.add(null);
  74.  
  75.     	/* starting from root as t, enqueue left elemnt, print data and move t to right ot it */
  76.     	do{ 
  77.     		/* move till extreme left of current node */
  78.     	    while(t != null )
  79.     	    {
  80.     	      /*enq left of node if it is not null */	
  81.     	      if (t.left != null)
  82.     	    	q.add(t.left);
  83.  
  84.     	      /* print data */
  85.     	      System.out.print(" "+ t.data);
  86.  
  87.     	      /* move to  right child of node */ 
  88.     	      t=t.right;	  
  89.     	    }
  90.  
  91.     	    /* if right child is null then we have two options - 
  92.     	     *  1. If next element in queue is null then it means we need to print new line character, 
  93.     	     *      deq null character, dequeue next element make it as current node.
  94.     	     *  2. If there are  non-null element in queue then dequeue it make it as current node.     
  95.     	     */
  96.  
  97.     	    if (!q.isEmpty())
  98.     	    {
  99.     	        t = q.remove();
  100.  
  101.     	    	if ( t==null)
  102.     	    	{
  103.     	    	  /* print new line and insert null character again after removing top elem, else break if queue is empty. */	
  104.     	    	  System.out.println("\n");
  105.  
  106.     	    	  if (!q.isEmpty())
  107.     	    	  {
  108.     	    		  t = q.remove();
  109.     	    	  }
  110.     	    	  else
  111.     	    		  break;
  112.  
  113.     	    	  /* add null again indicating begening of new line */
  114.     	    	  q.add(null);
  115.     	    	}
  116.     	    }
  117.  
  118.     	}while(!q.isEmpty());
  119.     }
  120. }
  121.  
  122.  
  123. /* Name of the class has to be "Main" only if the class is public. */
  124. class Ideone
  125. {
  126. 	public static void main (String[] args) throws java.lang.Exception
  127. 	{
  128. 	   int a[] = {15,9,20,7,12,17,25,3,8,10,14,16,19,23,28};
  129.  
  130.     	bstree bst = new bstree();
  131.     	bst.create(a, a.length);
  132.     	System.out.println("\nTree Inorder data : ");
  133.     	bst.inorder(bst.root);
  134.  
  135.     	 /* print tree diagonally */
  136.             System.out.println("\nDiagonal Printing of Tree: ");
  137.             bst.printTreeDiagonally(bst.root);
  138. 	}
  139. }
Success #stdin #stdout 0.1s 27872KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Tree Inorder data : 
3 7 8 9 10 12 14 15 16 17 19 20 23 25 28 
Diagonal Printing of Tree: 
 15 20 25 28

 9 12 14 17 19 23

 7 8 10 16

 3
https://ideone.com/q9ysDf
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!