Binary tree zigzag print

Problem

Given a binary tree print it in level order zigzag form.

Solution

A level order traversal of a tree is done using queue. Root is inserted into the queue. Then the iteration is done till the queue is empty. While a node is dequeued, its left and right children are added to the queue. In this way a normal level order print is possible. For zigzag, we keep a marker node. After root, the marker is inserted into the queue. So whenever marker is dequeued, that means a level has ended, so its children are already in the queue. So at this point the next level is also inserted. So we put the marker back into the queue if the queue is not already empty. For a reverse print of the level we use a stack to store the nodes, till the level is done.

Code

import java.util.LinkedList;
import java.util.LinkedList;
import java.util.Stack;

public class BinaryTreeZigzag {
 public static void main(String[] args) {
  Node a = new Node(1);
  Node b = new Node(2);
  Node c = new Node(3);
  Node d = new Node(4);
  Node e = new Node(5);
  Node f = new Node(6);
  Node g = new Node(7);
  Node h = new Node(8);
  Node i = new Node(9);

  a.left = b;
  a.right = c;
  b.right = d;
  c.left = e;
  c.right = f;
  d.left = g;
  d.right = h;
  g.right = i;

  printZigzag(a);

 }

 public static void printZigzag(Node root) {
  LinkedList queue = new LinkedList();
  Stack stack = new Stack();
  if (root == null)
   return;
  Node marker = new Node(-1);
  boolean printOrder = true;
  queue.add(root);
  queue.add(marker);
  while (!queue.isEmpty()) {
   Node node = queue.poll();
   if (node == marker) {
    if (!printOrder) {
     while (stack.size() > 0) {
      Node printNode = stack.pop();
      System.out.println(printNode.value);

     }

    }
    printOrder = !printOrder;
    if (!queue.isEmpty())
     queue.add(marker);
    continue;
   }
   if (printOrder) {
    System.out.println(node.value);
   } else {
    stack.push(node);
   }
   if (node.left != null)
    queue.add(node.left);
   if (node.right != null)
    queue.add(node.right);

  }

 }

 static class Node {
  public Node left;
  public Node right;
  public int value;

  public Node(int value) {
   this.value = value;
  }
 }

}