Zig-Zag Traversal

Problem Statement:
                      Traverse the Binary Tree in Zig Zag manner (aka spiral traversal)

Given Binary Tree:
       

Fig1: Given Binary Tree

The resultant Spiral Traversal or Zig-Zag Traversal is:
              

Fig2 : Resultant Level order Traversal (Left to Right)

Solution:

This problem is similar to level order traversal which required a Queue,
In this problem we would require 2 stacks meant for storing odd level and even level nodes in the tree

This problem is also called spiral traversal of binary Tree

Full Source Code: LINK

 /**
 * Zig Zag Level Order Traversal ( 2 stacks used)
 * @author Prateek Rathore
 */

 public void zigzagTraverse(Node root){

  if(root == null)
   return;

  Stack oddstack = new Stack();  //holds root as first element
  Stack evenstack = new Stack();

  oddstack.add(root);

  while(!oddstack.isEmpty() || !evenstack.isEmpty())
  {
   while(!oddstack.isEmpty())
   {
    Node item=oddstack.pop();
    System.out.print(item.data+"\t");
    
    if(item.left!=null)
     evenstack.push(item.left);
    
    if(item.right!=null)
     evenstack.push(item.right);
   }

   System.out.println();
   while(!evenstack.isEmpty())
   {
    Node item=evenstack.pop();
    System.out.print(item.data+"\t");

    if(item.right!=null)
     oddstack.push(item.right);
    
    if(item.left!=null)
     oddstack.push(item.left);
   }
   System.out.println();
  }
 }

Similar to this problem is Level Order Traversal of binary Tree.

Please post your critiques , suggestions as comments , also if any flaw or improvisation possible please do let me know.

Happy Coding !! :)