Output of binary tree in zig-zag manner

The problem can be asked in different ways:

1. Given a binary tree and each node has an extra next pointer apart from left and right. Connect all the nodes using next pointer in Zig-Zag Manner.

2. Given a binary tree and each node has an extra next pointer apart from left and right. Print out all node in Zig-Zag Manner.

They are all coming down to how to traverse the binary tree in zig-zag manner. The key is to use two stacks, main stack and temporary stack. The main stack is used to traverse each layer, while put the children under the layer into temporary stack, also be careful with if we need to go left to right or right to left. 

public static void zigZag(Node root){

Stack<Node> s = new Stack<Node>();

s.add(root);

int level = 0;

Node pre = null;

while(!s.isEmpty()){

Stack<Node> t = new Stack<Node>();

while(!s.isEmpty()){

Node curr = s.pop();

if(pre==null)

pre = curr;

else{

pre.next = curr;

pre = curr;

}

if(level%2==0){

if(curr.left!=null)

t.add(curr.left);

if(curr.right!=null)

t.add(curr.right);

}else{

if(curr.right!=null)

t.add(curr.right);

if(curr.left!=null)

t.add(curr.left);

}

}

s = t;

level++;

}

}