Level Order Traversal in Spiral Form

Problem Statement

Given a root node of a binary tree, print its level order traversal in spiral order.

Example

Input
Let’s assume we have the following binary tree –

         1
       /  \
      /    \
     2      3
    / \    / \
   /   \  /   \
  4     5 6    7

Note that only the address of the root node is provided as the input.

Output

The level order traversal in spiral order of the tree is - 
1 3 2 4 5 6 7

Example Explanation

The simple level order traversal of the tree is – 1 2 3 4 5 6 7
We just need to reverse the order in alternate levels to make it level order traversal in spiral order. In the above case, it required to reverse the $2^{nd}$ level only.

Constraints

• $0 < n < 10^5$, where $n$ is the number of nodes present in the tree.
• $0 < \text{node.val} < 10^9$

Approach 1 – Recursive

As we have discussed in the example explanation, we need to print every alternate level in the reverse order $i.e.$ from right to left.
To implement this we can keep a boolean variable (say ltr) and based on its value we can decide whether it is required to print this level left to right or right to left.
Now it is understood that the number of levels in the tree is equal to its height. So we will use a loop to iterate over all the levels and print them as per the value of ltr.

The steps involved in the algorithm of level order traversal in spiral order are –

• Declare a void type function spiralOrderTraversal that accepts a single argument $i.e.$ root node of the tree.
• Declare the boolean variable ltr, and initialize its value to true.
• Find the height of the given tree and store it in a variable h.
• Iterate from i = 1 to i = h and do the following –
  • Call a function (say printLevel) which prints the node at the $i^{th}$ level as per the value of ltr.
  • Flip the value of ltr $i.e.$ ltr = !ltr

Now at this point, you might be thinking, how is this a recursive approach? So, here comes the recursive function printLevel which prints the node of the binary tree at a certain level.

The steps required to implement this function are as follows –

• Let root, level, and ltr be the three variables supplied as the argument to this function.
• For the base condition check if the root is null then return from the function.
• Another base condition is to check if the level is 1. If this condition holds, then print the node’s value and return.
• Now there are two possibilities – If ltr is true –
  • Recurse back to node’s left child and pass the level value as level - 1.
  • Recurse back to node’s right child and pass the level value as level - 1.
    Else if ltr is false –
  • Recurse back to node’s right child and pass the level value as level - 1.
  • Recurse back to node’s left child and pass the level value as level - 1.

Java Implementation

import java.util.*;

public class Main{
    // Node class
    static class Node{
        int val;
        Node left, right;

        // Constructor
        Node(int val){
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }
    // Function to find the height of the tree.
    static int height(Node root){
        // Base condition to check if
        // root is null.
        if (root == null)
            return 0;

        // Finding the height of the left subtree.
        int left = height(root.left);
        // Finding the height of the right subtree.
        int right = height(root.right);

        return 1 + Math.max(left, right);

    }

    // Recursion function to print the ith level.
    static void printLevel(Node root, int level, boolean ltr){
        // Base condition to check if root itself is null.
        if (root == null)
            return;

        // Base condition to check if the level is 1
        if (level == 1){
            System.out.print(root.val + " ");
            return;
        }

        // If it is required to print left to 
        // right fashion.
        if (ltr){
            // Recurring for the left subtree.
            printLevel (root.left, level - 1, ltr);

            // Recurring for the right subtree
            printLevel (root.right, level - 1, ltr);
        } else{
            // Recurring for the right subtree
            printLevel (root.right, level - 1, ltr);

            // Recurring for the left subtree.
            printLevel (root.left, level - 1, ltr);
        }
    }
    // Function to print nodes in spiral order.
    static void printSpiral(Node root){
        // Finding height of the tree.
        int h = height(root);

        // Declaring boolean variable ltr.
        boolean ltr = true;

        // Iterating from i = 1 to i = h;
        for (int i = 1; i <= h; i++){
            // Calling printLevel to print the
            // i^th level.
            printLevel(root, i, ltr);

            // Flipping the ltr
            ltr = !ltr;
        }

    }

    // Main function
    public static void main(String args[]){
        // Constructing the following tree - 
        //           1
        //         /  \
        //        /    \
        //       2      3
        //      / \    / \
        //     /   \  /   \
        //    4    5 6    7
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        System.out.println("The Spiral order traversal of the tree is -");
        // Calling 'spiralOrder' function to 
        // print nodes in spiral order fashion.
        printSpiral(root);
    }
}

C++ Implementation

#include<bits/stdc++.h>
using namespace std;

// Node class
class Node{
public:
    int val;
    Node *left, *right;

    // Constructor
    Node(int Val){
        val = Val;
        left = nullptr;
        right = nullptr;
    }
};
// Function to find the height of the tree.
int height(Node *root){
    // Base condition to check if
    // root is nullptr.
    if (root == nullptr)
        return 0;

    // Finding the height of the left subtree.
    int left = height(root->left);
    // Finding the height of the right subtree.
    int right = height(root->right);

    return 1 + max(left, right);

}

// Recursion function to print the ith level.
void printLevel(Node *root, int level, bool ltr){
    // Base condition to check if root itself is nullptr.
    if (root == nullptr)
        return;

    // Base condition to checl if the level is 1
    if (level == 1){
        cout << root->val <<" ";
        return;
    }

    // If it is required to print left to 
    // right fashion.
    if (ltr){
        // Recurring for the left subtree.
        printLevel (root->left, level - 1, ltr);

        // Recurring for the right subtree
        printLevel (root->right, level - 1, ltr);
    } else{
        // Recurring for the right subtree
        printLevel (root->right, level - 1, ltr);

        // Recurring for the left subtree.
        printLevel (root->left, level - 1, ltr);
    }
}
// Function to print nodes in spiral order.
void printSpiral(Node *root){
    // Finding height of the tree.
    int h = height(root);

    // Declaring boolean variable ltr.
    bool ltr = true;

    // Iterating from i = 1 to i = h;
    for (int i = 1; i <= h; i++){
        // Calling printLevel to print the
        // i^th level.
        printLevel(root, i, ltr);

        // Flipping the ltr
        ltr = !ltr;
    }

}

// Main function
int main(){
    // Constructing the following tree - 
    //           1
    //         /  \
    //        /    \
    //       2      3
    //      / \    / \
    //     /   \  /   \
    //    4    5 6    7
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    cout << "The Spiral order traversal of the tree is -" << endl;
    // Calling 'spiralOrder' function to 
    // print nodes in spiral order fashion.
    printSpiral(root);
}

Python Implementation

class Node:    
    # Constructor
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# Function to find the height of the tree.
def height(root):
    # Base condition to check if
    # root is null.
    if (root == None):
        return 0

    # Finding the height of the left subtree.
    left = height(root.left)
    # Finding the height of the right subtree.
    right = height(root.right)

    return 1 + max(left, right)



# Recursion function to print the ith level.
def printLevel(root, level, ltr):
    # Base condition to check if root itself is null.
    if (root == None):
        return

    # Base condition to check if the level is 1
    if (level == 1):
        print(root.val, end = " ")
        return


    # If it is required to print left to 
    # right fashion.
    if (ltr):
        # Recurring for the left subtree.
        printLevel (root.left, level - 1, ltr)

        # Recurring for the right subtree
        printLevel (root.right, level - 1, ltr)
    else:
        # Recurring for the right subtree
        printLevel (root.right, level - 1, ltr)

        # Recurring for the left subtree.
        printLevel (root.left, level - 1, ltr)


# Function to print nodes in spiral order.
def printSpiral(root):
    # Finding height of the tree.
    h = height(root)

    # Declaring boolean variable ltr.
    ltr = True

    # Iterating from i = 1 to i = h
    for i in range(1, h + 1):
        # Calling printLevel to print the
        # i^th level.
        printLevel(root, i, ltr)

        # Flipping the ltr
        ltr = not ltr

# Driver code 
# Constructing the following tree - 
#           1
#         /  \
#        /    \
#       2      3
#      / \    / \
#     /   \  /   \
#    4    5 6    7
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

print("The Spiral order traversal of the tree is -")
# Calling 'spiralOrder' function to 
# print nodes in spiral order fashion.
printSpiral(root)

Output –

The Spiral order traversal of the tree is -
1 3 2 4 5 6 7 

Complexity Analysis

• Time Complexity – Since in each iteration we are traversing from the root node to the nodes at the current level. It may take O(n^2) time in the worst case (skewed tree).
• Space Complexity – However we are not using any auxiliary data structure but it would required O(n) space in the worst case because of recursive nature of the function.

Approach 2 – Iterative

In the previous section, we have seen how we can use recursion to print the level order traversal in spiral order. Here we will be seeing how we can implement the same functionality using the iterative method.
The idea involves the usage of two stacks simultaneously. We will use one of them say st1 to print the nodes from left to right and the other one (say st2) to print nodes from right to left.

The steps required to implement this approach are as follows –

• Let root be the address of the root node of the provided binary tree.
• Now declare two stacks (st1 and st2) of Node type, and insert root in st2.
• Now use a while loop to iterate till at least one of the two stacks is not empty, and do the following –
  • Again use a while loop to iterate till st1 is not empty, and do the following –
    • Pop out the node from st1 and store it in a local variable (say node).
    • Print node.val on the console.
    • If node’e right child is not null, push it in s2.
    • If node’s left child is not null push it in s2.
  • Similarly, use a while loop to iterate while st2 is not empty, and do the following –
    • Pop out the node from st1 and store it in a local variable (say node).
    • Print node.val on the console.
    • If node’s left child is not null push it in s1.
    • If node’e right child is not null, push it in s1.

Java Implementation

import java.util.*;
public class Main{
    // Node class
    static class Node{
        int val;
        Node left, right;

        // Constructor
        Node(int val){
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }
    // Function to print nodes in spiral order.
    static void printSpiral(Node root){
        // Base condition to check if 
        // root itself is null.
        if ( root == null)
            return;

        // Creating stacks (st1 and st2)
        // to store the nodes.
        Stack<Node> st1 = new Stack<>();
        Stack<Node> st2 = new Stack<>();

        // Push root node in st2. 
        st2.push(root);

        while (!st1.isEmpty() || !st2.isEmpty()){
            // Print the nodes on the current level
            // from st1 and push their children in st2.
            while (!st1.isEmpty()){
                // Pop node from st1, let it be node.
                Node node = st1.pop();
                // Print its value.
                System.out.print(node.val + " ");

                // Push right child in the st2.
                if (node.right != null)
                    st2.push(node.right);

                // Push left child in the st2.
                if (node.left != null)
                    st2.push(node.left);
            }
            // Print the nodes on the current level
            // from st2 and push their children in st1.
            while (!st2.isEmpty()){
                // Pop node from st1, let it be node.
                Node node = st2.pop();
                // Print its value.
                System.out.print(node.val + " ");

                // Push left child in the st1.
                if (node.left != null)
                    st1.push(node.left);

                // Push right child in the st1.
                if (node.right != null)
                    st1.push(node.right);

            }
        }
    }

    // Main function
    public static void main(String args[]){
        // Constructing the following tree - 
        //           1
        //         /  \
        //        /    \
        //       2      3
        //      / \    / \
        //     /   \  /   \
        //    4    5 6    7
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        System.out.println("The Spiral order traversal of the tree is -");
        // Calling 'spiralOrder' function to 
        // print nodes in spiral order fashion.
        printSpiral(root);
    }
}

C++ Implementation

#include<bits/stdc++.h>
using namespace std;

// Node class
class Node{
public:
    int val;
    Node *left, *right;

    // Constructor
    Node(int Val){
        val = Val;
        left = nullptr;
        right = nullptr;
    }
};

// Function to print nodes in spiral order.
void printSpiral(Node *root){
    // Base condition to check if 
    // root itself is null.
    if (root == nullptr)
        return;

    // Creating stacks (st1 and st2)
    // to store the nodes.
    stack<Node*> st1;
    stack<Node*> st2;

    // Push root node in st2. 
    st2.push(root);

    while (!st1.empty() || !st2.empty()){
        // Print the nodes on the current level
        // from st1 and push their children in st2.
        while (!st1.empty()){
            // Pop node from st1, let it be node.
            Node *node = st1.top();
            st1.pop();
            // Print its value.
            cout << node->val << " ";

            // Push right child in the st2.
            if (node->right != nullptr)
                st2.push(node->right);

            // Push left child in the st2.
            if (node->left != nullptr)
                st2.push(node->left);
        }
        // Print the nodes on the current level
        // from st2 and push their children in st1.
        while (!st2.empty()){
            // Pop node from st1, let it be node.
            Node *node = st2.top();
            st2.pop();
            // Print its value.
            cout << node->val << " ";

            // Push left child in the st1.
            if (node->left != nullptr)
                st1.push(node->left);

            // Push right child in the st1.
            if (node->right != nullptr)
                st1.push(node->right);
        }
    }

}

// Main function
int main(){
    // Constructing the following tree - 
    //           1
    //         /  \
    //        /    \
    //       2      3
    //      / \    / \
    //     /   \  /   \
    //    4    5 6    7
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    cout << "The Spiral order traversal of the tree is -" << endl;
    // Calling 'spiralOrder' function to 
    // print nodes in spiral order fashion.
    printSpiral(root);
}

Python Implementation

class Node:    
    # Constructor
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# Function to print nodes in spiral order.
def printSpiral(root):
    # Base condition to check if 
    # root itself is null.
    if (root == None):
        return

    # Creating stacks (st1 and st2)
    # to store the nodes.
    st1 = []
    st2 = []

    # Push root node in st2. 
    st2.append(root)

    while not len(st1) == 0 or not len(st2) == 0:
        # Print the nodes on the current level
        # from st1 and push their children in st2.
        while not len(st1) == 0:
            # Pop node from st1, let it be node.
            node = st1[-1]
            st1.pop()
            # Print its value.
            print(node.val, end = " ")

            # Push right child in the st2.
            if (node.right != None):
                st2.append(node.right)

            # Push left child in the st2.
            if (node.left != None):
                st2.append(node.left)

        # Print the nodes on the current level
        # from st2 and push their children in st1.
        while not len(st2) == 0:
            # Pop node from st1, let it be node.
            node = st2.pop()
            # Print its value.
            print(node.val, end = " ")

            # Push left child in the st1.
            if (node.left != None):
                st1.append(node.left)

            # Push right child in the st1.
            if (node.right != None):
                st1.append(node.right)

# Driver code 
# Constructing the following tree - 
#           1
#         /  \
#        /    \
#       2      3
#      / \    / \
#     /   \  /   \
#    4    5 6    7
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

print("The Spiral order traversal of the tree is -")
# Calling 'spiralOrder' function to 
# print nodes in spiral order fashion.
printSpiral(root)

Output –

The Spiral order traversal of the tree is -
1 3 2 4 5 6 7 

Complexity Analysis

• Time Complexity – Here we are exploring every node present in the tree without going back to any node again. Therefore the time complexity, in this case is O(n).
• Space Complexity – Since we are using two stacks here, whose combined maximum size can reach up to O(n) therefore the space complexity is O(n).

Approach 3 – using Doubly Ended Queue

In the simple level order traversal, we have seen how we can use a queue to print nodes in the simple level order fashion.
Here as it is required to perform level order traversal in spiral order, we will be using the doubly ended queue so that we can also dequeue the elements from the rear end and thus print the nodes from right to left.

The idea is to use a doubly ended queue (say dq) and to print the nodes we will have two choices –

1. If it is required to print nodes of $i^{th}$ level in left to right order then we will pop the front elements to print them, and add their children to the rear end of the dq.
2. Otherwise if it is required to print the nodes of the $i^{th}$ level in right to left order, then we will pop the nodes from the rear end to print them, and add their children to the front end of the dq.

Here are the steps required to implement the algorithm –

• Declare a doubly ended queue dq and insert root in it.
• Also define the boolean variable ltr to find the order in which it is required to print the nodes.
• Now iterate while dq is not empty and do the following –
  • Find the size of the dq and store it in a variable n.
  • If ltr is true, it means we need to print nodes in left to right order. So, use a for loop to iterate from $i = 1$ to $i = n$ and do the following –
    • Pop the front node of dq and store it in a variable node.
    • Print the value of the node, and insert their children at the rear end of the dq (the right child is followed by the left child).
  • Otherwise, if ltr is false, it means we need to print nodes in right to left order. So, use a for loop to iterate from $i = 1$ to $i = n$ and do the following –
    • Pop the rear node of dq and store it in a variable node.
    • Print the value of the node, and insert their children at the rear end of the dq (the right child is followed by the left child).

Java Implementation

import java.util.*;
public class Main{
    // Node class
    static class Node{
        int val;
        Node left, right;

        // Constructor
        Node(int val){
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }
    // Function to print nodes in spiral order.
    static void printSpiral(Node root){
        // Base condition to check if 
        // root itself is null.
        if ( root == null)
            return;

        // Declare the doubly ended queue. 
        Deque<Node> dq = new ArrayDeque<>();
        // Adding root in the queue. 
        dq.offer(root);

        // Declaring the boolean variable to 
        // detect in which order it is required
        // to print the node. 
        boolean ltr = true;

        // Iterate while dq is not empty
        while (!dq.isEmpty()){
            // Find the size of the dq.
            int n = dq.size();

            // If it is required to print in
            // left to right order.
            if (ltr){
                // Iterate from i = 1 to i = n
                for (int i = 1; i <= n; i++){
                    // Poll the node from the front end
                    Node node = dq.pollFirst();

                    // Print the node's value.
                    System.out.print(node.val + " ");
                    // Insert its children at the rear
                    // end of the queue.
                    if (node.left != null)
                        dq.offerLast(node.left);
                    if (node.right != null)
                        dq.offerLast(node.right);

                }
            } else{
                // Iterate from i = 1 to i = n
                for (int i = 1; i <= n; i++){
                    // Poll the node from the rear end
                    Node node = dq.pollLast();

                    // Print the node's value.
                    System.out.print(node.val + " ");
                    // Insert its children at the front
                    // end of the queue.
                    if (node.right != null)
                        dq.offerFirst(node.right);
                    if (node.left != null)
                        dq.offerFirst(node.left);

                }
            }

            // Flip the value of ltr.
            ltr = !ltr;
        }

    }

    // Main function
    public static void main(String args[]){
        // Constructing the following tree - 
        //           1
        //         /  \
        //        /    \
        //       2      3
        //      / \    / \
        //     /   \  /   \
        //    4    5 6    7
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        System.out.println("The Spiral order traversal of the tree is -");
        // Calling 'spiralOrder' function to 
        // print nodes in spiral order fashion.
        printSpiral(root);
    }
}

C++ Implementation

#include<bits/stdc++.h>
using namespace std;

// Node class
class Node{
public:
    int val;
    Node *left, *right;

    // Constructor
    Node(int Val){
        val = Val;
        left = nullptr;
        right = nullptr;
    }
};

// Function to print nodes in spiral order.
void printSpiral(Node *root){
    // Base condition to check if 
    // root itself is null.
    if (root == nullptr)
        return;

    // Declare the doubly ended queue. 
    deque<Node*> dq;
    // Adding root in the queue. 
    dq.push_back(root);

    // Declaring the boolean variable to 
    // detect in which order it is required
    // to print the node. 
    bool ltr = true;

    // Iterate while dq is not empty
    while (!dq.empty()){
        // Find the size of the dq.
        int n = dq.size();

        // If it is required to print in
        // left to right order.
        if (ltr){
            // Iterate from i = 1 to i = n
            for (int i = 1; i <= n; i++){
                // Poll the node from the front end
                Node *node = dq.front();
                dq.pop_front();

                // Print the node's value.
                cout << node->val << " ";
                // Insert its children at the rear
                // end of the queue.
                if (node->left != nullptr)
                    dq.push_back(node->left);
                if (node->right != nullptr)
                    dq.push_back(node->right);

            }
        } else{
            // Iterate from i = 1 to i = n
            for (int i = 1; i <= n; i++){
                // Poll the node from the rear end
                Node *node = dq.back();
                dq.pop_back();

                // Print the node's value.
                cout << node->val << " ";

                // Insert its children at the front
                // end of the queue.
                if (node->right != nullptr)
                    dq.push_front(node->right);
                if (node->left != nullptr)
                    dq.push_front(node->left);

            }
        }

        // Flip the value of ltr.
        ltr = !ltr;
    }

}

// Main function
int main(){
    // Constructing the following tree - 
    //           1
    //         /  \
    //        /    \
    //       2      3
    //      / \    / \
    //     /   \  /   \
    //    4    5 6    7
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    cout << "The Spiral order traversal of the tree is -" << endl;
    // Calling 'spiralOrder' function to 
    // print nodes in spiral order fashion.
    printSpiral(root);
}

Python Implementation

from collections import deque

class Node:    
    # Constructor
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# Function to print nodes in spiral order.
def printSpiral(root):
    # Base condition to check if 
    # root itself is null.
    if (root == None):
        return

    # Declare the doubly ended queue. 
    dq = deque()
    # Adding root in the queue. 
    dq.append(root)

    # Declaring the boolean variable to 
    # detect in which order it is required
    # to print the node. 
    ltr = True

    # Iterate while dq is not empty
    while (len(dq) != 0):
        # Find the size of the dq.
        n = len(dq)

        # If it is required to print in
        # left to right order.
        if (ltr):
            # Iterate from i = 1 to i = n
            for i in range(1, n + 1):
                # Poll the node from the front end
                node = dq.popleft()

                # Print the node's value.
                print(node.val, end = " ")
                # Insert its children at the rear
                # end of the queue.
                if (node.left != None):
                    dq.append(node.left)
                if (node.right != None):
                    dq.append(node.right)


        else:
            # Iterate from i = 1 to i = n
            for i in range(1, n + 1):
                # Poll the node from the rear end
                node = dq.pop()

                # Print the node's value.
                print(node.val, end = " ")
                # Insert its children at the front
                # end of the queue.
                if (node.right != None):
                    dq.appendleft(node.right)
                if (node.left != None):
                    dq.appendleft(node.left)

        # Flip the value of ltr.
        ltr = not ltr

# Driver code 
# Constructing the following tree - 
#           1
#         /  \
#        /    \
#       2      3
#      / \    / \
#     /   \  /   \
#    4    5 6    7
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

print("The Spiral order traversal of the tree is -")
# Calling 'spiralOrder' function to 
# print nodes in spiral order fashion.
printSpiral(root)

Output –

The Spiral order traversal of the tree is -
1 3 2 4 5 6 7 

Complexity Analysis

• Time Complexity – Again we are exploring and printing all the nodes of the binary tree without revisiting the explored nodes. Hence the time complexity is O(n).
• Space Complexity – Since, we are using a doubly ended queue, whose size can reach up to O(n). Hence the space complexity is O(n).

Conclusion

• Printing nodes of binary tree in spiral order is nothing but the level order traversal with every alternate level in reversed fashion.
• Recursion can be used to print nodes in spiral order but it requires O(n^2) time to do so.
• Using the iterative method (either by using stacks or doubly ended queue), nodes can be printed in spiral order in O(n) time.