Objective : We are given a binary tree we need to print the data of tree diagonally , it is also know as Diagonal Tree Traversal.
Sample Input : Let us consider the below tree
1
3 2
6. 8 5. 4
9 7
Out Put : We should be able to get the out put as
1, 3, 6
2, 5, 8, 9
4, 7
Approach :
To print tree data diagonally we have used Queues with null character for new line. We will print the Node Data and save the left child of the node for second Level, move to right child, once we reach right most node then add null character indicating line change and pop new element fromt he queue. This is more or less similar to Level Order traversal however here we need save left child here in order to print the tree correctly.
Algorithm :
- Create a queue ( used inbuilt Queue for Java here )
- Root is assumed as Current Node ( currNode) , Enqueue a Null indicating new line.
- Enqueue left of currNode if it is not null, print currNode Data and Move to Right Child of Node.
- Repeat 3 untill t is not null.
- Once Current Node is null, check if queue is empty , get top elem
- If topmost element is null then remove top elem, print new line repeat 3.
- Repeat 3 to 5 untill queue is empty.
Complete Java Code:
/* topcse - Diagonal Printing of Binary Tree ; */
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;
/* default constructor */
bstnode() {data = 0 ; left = null; right = null;}
/* make node */
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 Main
{
public static void main (String[] args) throws java.lang.Exception
{
/* input data */
int a[] = {15,9,20,7,12,17,25,3,8,10,14,16,19,23,28};
/* Tree level Order */
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);
}
}
Output :
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
