Spiral Order Traversal of Binary Tree

Problem: Given a binary tree, print its nodes level by level in spiral order.

For example:

The spiral order traversal of the tree above is (1, 3, 2, 4, 5, 6, 7) or (1, 2, 3, 7, 6, 5, 4)

Method 1: The idea is to use two stacks. We can use one stack for printing from left to right and other stack for printing from right to left. In every iteration, we have nodes of one level in one of the stacks. We print the nodes, and push nodes of next level in other stack.

import java.util.*;
 
/* creating Tree node */
class Node 
{
    int data;
    Node left, right;
 
    public Node(int val) 
    {
        data = val;
        left = right = null;
    }
}
 
class BinaryTree 
{
 
    static Node root;
 
    /* function to print spiral of binary tree */
    void printSpiral(Node node) 
    {
        /* checking base case */
        if (node == null) 
            return;
 
        /* two stacks to store alternate levels
           stack s1 used to print nodes from right to left 
           and s2 used to print nodes from left to right */
        Stack s1 = new Stack();
        Stack s2 = new Stack();
 
        /* Push first level to first stack 's1' */
        s1.push(node);
 
        /* Keep ptinting 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()) 
            {
                Node temp = s1.peek();
                s1.pop();
                System.out.print(temp.data + " ");
 
                /* Note that is right is pushed before left */
                if (temp.right != null) 
                    s2.push(temp.right);
                 
                if (temp.left != null) 
                    s2.push(temp.left);
                 
            }
 
            /* Print nodes of current level from s2 and push 
               nodes of next level to s1 */
            while (!s2.empty()) 
            {
                Node temp = s2.peek();
                s2.pop();
                System.out.print(temp.data + " ");
 
                /* Note that is left is pushed before right */
                if (temp.left != null)
                    s1.push(temp.left);
                if (temp.right != null)
                    s1.push(temp.right);
            }
        }
    }
 
    public static void main(String[] args) 
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.right.left = new Node(6);
        tree.root.right.right = new Node(7);
        tree.printSpiral(root);
    }
}

Output:

1 2 3 7 6 5 4

Method 2: We can also do this problem using Dequeue.

/* function to print spiral of binary tree */
public static void printSpiral(Node root) 
{
    Node temp = root;
    Deque deque = new java.util.LinkedList();
    deque.addLast(temp);
    
    /* boolean varible which store detail of style of printing
       i.e left to right or right to let */
    boolean isReverseLevel = true;

    while (!deque.isEmpty()) 
    {
        int size = deque.size();

        while (size > 0) 
        {
            if (isReverseLevel) 
            {
                Node pollLast = deque.pollLast();
                System.out.print(" " + pollLast.data);
                if (pollLast.right != null) 
                {
                    deque.addFirst(pollLast.right);
                }
                if (pollLast.left != null) 
                {
                    deque.addFirst(pollLast.left);
                }
            } 
            else 
            {
                Node pollFirst = deque.pollFirst();
                System.out.print(" " + pollFirst.data);
                if (pollFirst.left != null) 
                {
                    deque.addLast(pollFirst.left);
                }
                if (pollFirst.right != null) 
                {
                    deque.addLast(pollFirst.right);
                }
            }
            size--;
        }
        isReverseLevel = !isReverseLevel;
    }
}

Time Complexity: O(n) and Space Complexity: O(n)