Diagonal Traversal of Binary Tree – Print Data Diagonally ( Algorithm with Java Code )

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

 

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 : 

  1. Create a queue ( used inbuilt Queue for Java here )
  2. Root is assumed as Current Node ( currNode) , Enqueue a Null indicating new line.
  3. Enqueue left of currNode if it is not null, print currNode Data and Move to Right Child of Node.
  4. Repeat 3 untill t is not null.
  5. 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.
  6. Repeat 3 to 5 untill queue is empty.

 

Complete Java Code:

Output :

 

%d bloggers like this: