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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

/**  * Zig Zag Level Order Traversal ( 2 stacks used)  * @author Prateek Rathore  */    public void zigzagTraverse(Node root){     if(root == null)    return;     Stack<node> oddstack = new Stack<node>();  //holds root as first element   Stack<node> evenstack = new Stack<node>();     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();   }  }   </node></node></node></node>

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 !! :)