Level order traversal in spiral form

1. Use two stacks.

      One stack for print the elements from left to right,

      Other stack to print the elements from right to left.

2. In every iteration, we have nodes of one level,

   We will print the nodes and keep pushing the child nodes in another stack.

import java.util.Stack;

class Tree {

   int value;

   Tree left;

   Tree right;

   public Tree (int value) {

      this.value = value;

   }

}

public class PrintSpriralTree {

   public static void main(String[] args) {

      Tree root = new Tree(1);

      root.left = new Tree(2);

      root.right = new Tree(3);

      root.left.left = new Tree(7);

      root.left.right = new Tree(6);

      root.right.left = new Tree(5);

      root.right.right = new Tree(4);

      root.left.left.left = new Tree(8);

      root.left.left.right = new Tree(9);

      root.left.left.left.left = new Tree(11);

      root.left.left.left.right = new Tree(10);

      printSpiral(root);

   }

   private static void printSpiral(Tree root) {

      Stack<Tree> s1 = new Stack<Tree>();

      Stack<Tree> s2 = new Stack<Tree>();

      s1.add(root);

      while(!s1.isEmpty() || !s2.isEmpty()) {

        

         while(!s1.isEmpty()) {

            Tree top = s1.pop();

            System.out.print(top.value+" ");

           

            if(top.right!=null) {

               s2.add(top.right);

            }

           

            if(top.left!=null) {

               s2.add(top.left);

            }

         }

        

         while(!s2.isEmpty()) {

            Tree top = s2.pop();

            System.out.print(top.value + " ");

           

            if(top.left!=null) {

               s1.add(top.left);

            }

           

            if(top.right!=null) {

               s1.add(top.right);

            }           

         }

      }

   }

}

Spiral order traversal will take O(n) time and O(n) extra space.