Traversing binary tree in zig zag order

The question is we need to traverse binary tree level by level in such a way that traversal direction within level changes from level to level thus forming a spiral.

We’ll start with a well know problem of traversing binary tree level by level It can be done using queue. But this problem seems to be tricky. Its not the obvious approach. Instead of going with queue approach we can solve this problem using two stacks. Let us say the two stacks are curr Level and nextLevel. Next level is a set of child nodes from current level. We also need a variable to keep track of the current level’s order. If next level must be traversed from left to right we must first push right child node and then left and in opposite order if next level will be traversed from right to left we will push the left child first and then right child.

Working Java Code:

public void spiralOrderTraversal(BinaryTreeNode root)
    {
        Stack<BinaryTreeNode> currentLevel,nextLevel;
        BinaryTreeNode temp;
        int leftToRight = 1;
       
        if(root == null)
            return;
       
        currentLevel = new Stack<BinaryTreeNode>();
        nextLevel = new Stack<BinaryTreeNode>();
       
        currentLevel.push(root);
       
        while(!(currentLevel.isEmpty())
        {
            temp = currentLevel.pop();
            if(temp)
            {
                System.out.println(temp.data);
                if(leftToRight)
                {
                    if(temp.left)
                        nextLevel.push(temp.left);
                    if(temp.right)
                        nextLevel.push(temp.right);
                }
                else
                {
                    if(temp.right)
                        nextLevel.push(temp.right);
                    if(temp.left)
                        nextLevel.push(temp.left);
                }
               
                if(currentLevel.isEmpty())
                {
                    leftToRight = 1-leftToRight;
                    swap(currentLevel,nextLevel)
                }
            }
        }
    }