Print a Binary Tree in Zig Zag Level Order or spiral order

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/binary-tree-traversal-zigzag-level-order-traversal/.

Question: Print a binary tree in zig-zag level order. Zig-zag means print 1st level from left to right, then 2nd level right to left and alternate thereafter.
Example: zig-zag level order traversal of below tree will be
0 2 1 3 4 5 6 14 13 12 11 10 9 8 7


Solution1 - Iterative solution

Answer: We usually use a queue for level order traversal of a queue. If we want to use the same here, how will we change direction of traversal on every alternate level?
If we think logically then we will see that we need stack in place of queue. Now again a single stack won’t serve our purpose here, we need 2 stacks: stack1 for right to left and stack2 for left to right. For identifying, whether we need to put data in stack1 or stack2, we need a flag (left2right) to indicate direction (after a level finishes).
Initially, left2right is true and we push root node in stack1 and that’s our beginning point. Now since after root node, first level fished, we toggle left2right. Until stack1 is empty, we pop values from stack1 and push values based on left2right flag. Once stack1 finishes, we toggle left2right again and switch stack’s role.
For clarification, when left2right is true, push left node first in stack and then right node. Similarly left2right is false, push right node first in stack and then left node.

public static <T extends Comparable>
    void  ZigZagLevelOrder(BSTNode<T> root) {
        Stack<BSTNode<T>> stack1 = new Stack<BSTNode<T>>();
        Stack<BSTNode<T>> stack2 = new Stack<BSTNode<T>>();
        Stack<BSTNode<T>> cur_level, next_level, temp;

        boolean left2right = true;

        cur_level = stack1;
        next_level = stack2;

        // push root in stack
        cur_level.push(root); 

        while (!cur_level.empty()) {
            BSTNode<T> node = cur_level.firstElement(); //top();
            cur_level.pop();
            if (node!=null) {
                out.println(node.data+" ");
                //cout << node.data << " ";
                if (left2right) {
                    //if left to right, start pushing from left
                    next_level.push(node.left);
                    next_level.push(node.right);
                } else {
                    next_level.push(node.right);
                    next_level.push(node.left);
                }
            }
            if (cur_level.empty()) {
                left2right = !left2right;
                // swap stacks
                temp = cur_level;
                cur_level = next_level;
                next_level = temp;     
            }
        }
    }

What if you have to remove the left2right flag?,how will you go about it?

Then we can use 2 while loops instead of if then else:

public static void ZigZagLevelOrder(BSTNode root){
    Queue<BSTNode> curr = new Queue();
    Stack<BSTNode> next= new Stack();
    curr.add(root);
 while(!curr.isEmpty() || !next.isEmpty()){
  while(!curr.isEmpty()){
   BSTNode p = curr.deque();
   print(p.data);
   next.add(p.children from left to right);
  }
  while(!next.isEmpty()){
   BSTNode p = next.pop();
   print(p.data);
   curr.add(p.children from n-1 to 0);
  }

   }
}

Here we are using 1 stack and 1 queue, but we can also use 2 stacks:

public static void print(BSTNode root)
    Stack<BSTNode> s1 = new Stack<BSTNode>();  // For levels to be printed from right to left
    Stack<BSTNode> s2 = new Stack<BSTNode>();  // For levels to be printed from left to right
 
    // Push first level to first stack 's1'
    s1.push(root);
 
    // Keep printing while any of the stacks has some nodes
    while (!s1.empty() || !s2.empty())
    {
        // Print nodes of current level from s1 and push nodes of
        // next level to s2
        while (!s1.empty())
        {
            BSTNode temp = s1.top();
            s1.pop();
            print(temp.data);
 
            // Note that is right is pushed before left
            if (temp.right)
                s2.push(temp.right);
            if (temp.left)
                s2.push(temp.left);
        }
 
        // Print nodes of current level from s2 and push nodes of
        // next level to s1
        while (!s2.empty())
        {
            BSTNode temp = s2.top();
            s2.pop();
            print(temp.data );
 
            // Note that is left is pushed before right
            if (temp.left)
                s1.push(temp.left);
            if (temp.right)
                s1.push(temp.right);
        }
    }
}

So, we got rid of left2right flag.
Solution 2 - Recursive solution

Approach: To print the nodes in spiral order, nodes at different levels should be printed in alternating order. To change the order of printing alt variable is used. If alt is 1 then printSpiralLevel() prints nodes from left to right else from right to left.

void printSpiralLevel(struct node* root, int level, int alt);
int height(struct node* node);
  
// Function to print spiral traversal of a tree
void printSpiral(struct node* root)
{
    int h = height(root);
    int i;
    bool alt = false;
    for(i=1; i<=h; i++)
    {
        printSpiralLevel(root, i, alt);
  
        //Revert alt to traverse next level in oppposite order
        alt = !alt;
    }
}
  
// Print nodes at a given level 
void printSpiralLevel(struct node* root, int level, int alt)
{
    if(root == NULL)
        return;
    if(level == 1)
        printf("%d ", root->data);
    else if (level > 1)
    {
        if(alt)
        {
            printSpiralLevel(root->left, level-1, alt);
            printSpiralLevel(root->right, level-1, alt);
        }
        else
        {
            printSpiralLevel(root->right, level-1, alt);
            printSpiralLevel(root->left, level-1, alt);
        }
    }
}

Thanks