Convert Binary Tree to Double Linked List in Zig-Zag Order

Question: given a binary tree, write an algorithm to convert the tree into a double-linked list. The list must be as if the tree is traversed in zig-zag and level order.
Solution: let's first understand what the objective is. By zig-zag level order, the question means that we need to traverse the tree in level order, a.k.a breadth first, such that the next level is traversed in the oposite direction to the current level. For example, take a look at this tree:

A zig-zag level-order traversal creates the list 1, 2, 3, 5, 4. It doesn't matter which direction the root is printed because there is only one node. However, since the second level is printed left to right, 2 then 3, the third level is printed from right to left, 5 then 4.

Now we understand the question, let's figure out how to solve this problem. Well, the only tricky part is to traverse the tree in zig-zag order. The other part, adding nodes to a linked list, is easy.
We have already seen how to do zig zag order traversal here.

To solve this problem, we need two stacks. One stack stores nodes of levels that traversed from left to right. The other stores nodes of levels that traversed from right to left. The idea is to add the children of each node of the same level into a different stack than their parent. Thus, all children of the same level are in the same stack, separating one level from another. These children nodes are also pushed in the stack in the same direction with each other but opposite direction with their parents, so they can be traversed in the opposite direction to their parents. Moreover, as we traverse the tree, we add each node into a double linked list.

public static <T> DoubleLinkedList<T> 

bt2ZigZagDoubleLinkedList(BSTNode<T> root)
{
 if (root == null)
  return null;

 DoubleLinkedList<T> head = new DoubleLinkedList<T>();
 head.addHead(root.data);

 BSTNode<T> listIT = null;
 BSTNode<T> prevNode = null;

 Stack<BSTNode<T>> left2RightStack = 

new Stack<BSTNode<T>>();
 Stack<BSTNode<T>> right2LeftStack = 

new Stack<BSTNode<T>>();

 left2RightStack.push(root);

 while (!left2RightStack.empty())
 {
  //add nodes from left to right to the list
  while (!left2RightStack.empty())
  {
   //set previous node
   prevNode = listIT;

   //pop a node in left2RightStack and add it to list
   listIT = left2RightStack.peek(); 
   left2RightStack.pop();

 //add child nodes of the newly node in right to left direction
   if (listIT.left != null)
    right2LeftStack.push(listIT.left);

   if (listIT.right != null)
    right2LeftStack.push(listIT.right);

  //set left pointer of current node to the node in front of it
   listIT.left = prevNode; 

  //the previous node points to the current node in list
   if (prevNode != null)
    prevNode.right = listIT;
  }

 //add nodes from right to left to the list
  while (!right2LeftStack.empty())
  {
   prevNode = listIT;

   listIT = right2LeftStack.peek();

   right2LeftStack.pop();

   if(listIT.right != null)
    left2RightStack.push(listIT.right);

   if(listIT.left != null)
    left2RightStack.push(listIT.left);

   listIT.left = prevNode;

   if (prevNode != null)
    prevNode.right = listIT;
  }
 }

//connect linked the end node of list to null and the node in front of it
 listIT.right = null;
 listIT.left = prevNode;

 return head;
}