Printing Spiral order Traversal of Binary tree

June 23, 2019

Given a Tree and we need to print the spiral order traversal of the given tree.

By spiral Order Traversal We mean that alternate levels should be printed in alternate order .

for eg:- Level 0 to  be printed left to right
Level 1 from right to left. and so on

import java.util.*;
class Node
{
    int data;
    Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
    public Node()
    {
        data =0;
        left  = right = null;
    }
}

// Binary tree Class
class BTree
{
 
    static Node root;

void printSpiral(Node node)
      {
           // We will use a Queue and a Stack Here .
           Queue queue = new LinkedList();
           if(node == null) // Edge Case , when root is null
           return;
           
           boolean flag = false;
           Stack straightPrint = new Stack();
           Stack revPrint = new Stack ();
           straightPrint.add(node);
            
           while(!(straightPrint.isEmpty()) || !(revPrint.isEmpty())){
               while(revPrint.size()>0){
                   Node temp = revPrint.pop();
                   System.out.print(temp.data +" ");
                   //Left to Right for next Level (Straight Level)
                   if(temp.left != null)
                   straightPrint.push(temp.left);
                   if(temp.right != null)
                   straightPrint.push(temp.right);
               }
               while(straightPrint.size() >0){
                   Node temp = straightPrint.pop();
                    System.out.print(temp.data +" ");
                   // Right To Left for next Level (Reverse Print )
                   if(temp.right != null)
                   revPrint.push(temp.right);
                   if(temp.left != null)
                   revPrint.push(temp.left);
               }
           }    
           
      }


 public static void main(String[] args)
    {
        BTree tree = new BTree();
        tree.root = new Node(1);
        tree.root.left = new Node(5);
        tree.root.right = new Node(4);
        tree.root.left.left = new Node(9);
        tree.root.left.right = new Node(7);
        tree.root.right.left = new Node(10);
        tree.root.right.right = new Node(13);
        System.out.println("Spiral Order traversal of Binary Tree is ");
        tree.printSpiral(root);
    }
}