Level Order Traversal in Spiral Form

Example

Let us consider this binary tree.

The level order traversal in spiral form of the above tree will be 10 30 20 40 50 60 80 70 or 10 20 30 60 50 40 70 80.

Method 1

This idea is based on line-by-line level order traversal. In this method, we process the items four times. We generally do the below operations.

• Enqueue into the queue.
• Dequeue from the queue.
• Push into the stack.
• Pop from the stack.

Algorithm

• Create an empty queue q, generally used for normal-level order traversal.
• Push the root node of a tree to q. That is, q.push(root).
• Running a loop while the queue is not empty, we get queue.size() and run one more loop inside it till queue.size().
• We also use a stack, and its purpose is to reverse the alternate level. Whenever we are at a level to be changed, we add to the stack.

Implementation in C++

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


struct Node  
{ 
  int key; 
  struct Node *left; 
  struct Node *right; 
  Node(int k){
      key=k;
      left=right=NULL;
  }
};


void printSpiral(Node *root){
    if(root==NULL)return;
    queue<Node *>q;
    stack<int> s;
    bool reverse=false;
    q.push(root);
    while(q.empty()==false){
        int count=q.size();
        for(int i=0;i<count;i++){
        Node *curr=q.front();
        q.pop();
        if(reverse)
            s.push(curr->key);
        else
            cout<<curr->key<<" ";
        if(curr->left!=NULL)
            q.push(curr->left);
        if(curr->right!=NULL)
            q.push(curr->right);
        }
        if(reverse){
            while(s.empty()==false){
                cout<<s.top()<<" ";
                s.pop();
            }
        }
    reverse=!reverse;
    }
}  


int main() {
    
    Node *root=new Node(10);
    root->left=new Node(20);
    root->right=new Node(30);
    root->left->left=new Node(40);
    root->left->right=new Node(50);
    root->left->right->left=new Node(70);
    root->left->right->right=new Node(80);
    root->right->right=new Node(60);
    
    printSpiral(root);
}

You can also try this code with Online C++ Compiler

Run Code

Implementation in Java

import java.util.*;
import java.io.*;
import java.lang.*;


class Node  
{ 
  int key; 
  Node left; 
  Node right; 
  Node(int k){
      key=k;
      left=right=null;
  }
}



class CN { 
    
    public static void main(String args[]) 
    { 
        Node root=new Node(10);
        root.left=new Node(20);
        root.right=new Node(30);
        root.left.left=new Node(40);
        root.left.right=new Node(50);
        root.left.right.left=new Node(70);
        root.left.right.right=new Node(80);
        root.right.right=new Node(60);
        
        printSpiral(root);
    } 
    
    public static void printSpiral(Node root){
        if(root==null)return;
        Queue<Node> q=new LinkedList<>();
        Stack<Integer> s=new Stack<>();
        boolean reverse=false;
        q.add(root);
        while(q.isEmpty()==false){
            int count=q.size();
            for(int i=0;i<count;i++){
            Node curr=q.poll();
            if(reverse)
                s.add(curr.key);
            else
                System.out.print(curr.key+" ");
            if(curr.left!=null)
                q.add(curr.left);
            if(curr.right!=null)
                q.add(curr.right);
            }
            if(reverse){
                while(s.isEmpty()==false){
                    System.out.print(s.pop()+" ");
                }
            }
        reverse=!reverse;
        }
    }   
}

You can also try this code with Online Java Compiler

Run Code

Input: 

10 20 30 40 50 70 80 60

Output: 

10 30 20 40 50 60 80 70

Time Complexity: O(N), N is the number of nodes in a tree. Every node is enqueued into the queue exactly once and dequeued from the queue exactly once. Also, a node might be pushed into the stacked or popped from the stack. So, a node must be traversed almost four times. So the time complexity will be upper bound by 4N. Therefore, its time complexity is O(N).

Space Complexity: O(N).

Method 2

In method 1, we do some extra work for the items to be printed in reverse order. These items go into the queue first, come out from the queue, and then come into the stack and come out from the stack.

In this method, we optimized the solution by reducing the amount the work by maintaining two stacks. So we generally do push and pop operations from the stack.

Algorithm 

• It uses two stacks.
• Push root to the stack s1.
• While any of the two stacks is not empty.
• While s1 is not empty.

Take out a node, print it and, Push children of the taken out node into s2.

• While s2 is not empty.

Take out a node, print it and, Push children of the taken out node into s1 in reverse order.

Implementation in C++

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


struct Node  
{ 
  int key; 
  struct Node *left; 
  struct Node *right; 
  Node(int k){
      key=k;
      left=right=NULL;
  }
};


void printSpiral(Node *root){
    if (root == NULL) 
        return;  
    stack<Node*> s1;  
    stack<Node*> s2;  
  
    s1.push(root); 
    while (!s1.empty() || !s2.empty()) { 
        while (!s1.empty()) { 
            Node* temp = s1.top(); 
            s1.pop(); 
            cout << temp->key << " "; 
  
            if (temp->right) 
                s2.push(temp->right); 
            if (temp->left) 
                s2.push(temp->left); 
        } 
        
        while (!s2.empty()) { 
            Node* temp = s2.top(); 
            s2.pop(); 
            cout << temp->key << " "; 
  
            if (temp->left) 
                s1.push(temp->left); 
            if (temp->right) 
                s1.push(temp->right); 
        } 
    } 
}  

int main() {
    
    Node *root=new Node(10);
    root->left=new Node(20);
    root->right=new Node(30);
    root->left->left=new Node(40);
    root->left->right=new Node(50);
    root->left->right->left=new Node(70);
    root->left->right->right=new Node(80);
    root->right->right=new Node(60);
    
    printSpiral(root);
}

You can also try this code with Online C++ Compiler

Run Code

Implementation in Java

import java.util.*;
import java.io.*;
import java.lang.*;

class Node  
{ 
  int key; 
  Node left; 
  Node right; 
  Node(int k){
      key=k;
      left=right=null;
  }
}

class CN { 
    
    public static void main(String args[]) 
    { 
        Node root=new Node(10);
        root.left=new Node(20);
        root.right=new Node(30);
        root.left.left=new Node(40);
        root.left.right=new Node(50);
        root.left.right.left=new Node(70);
        root.left.right.right=new Node(70);
        root.right.right=new Node(60);
        printSpiral(root);
    } 
    
    public static void printSpiral(Node root){
        if (root == null) 
            return; 
        Stack<Node> s1 = new Stack<Node>();  
        Stack<Node> s2 = new Stack<Node>();  
   
        s1.add(root); 
  
        while (!s1.isEmpty() || !s2.isEmpty()) { 
            while (!s1.empty()) { 
                Node temp = s1.peek(); 
                s1.pop(); 
                System.out.print(temp.key + " "); 
  
                if (temp.right != null) 
                    s2.add(temp.right); 
  
                if (temp.left != null) 
                    s2.add(temp.left); 
            } 
  
            while (!s2.empty()) { 
                Node temp = s2.peek(); 
                s2.pop(); 
                System.out.print(temp.key + " "); 
  
                if (temp.left != null) 
                    s1.add(temp.left); 
                if (temp.right != null) 
                    s1.add(temp.right); 
            } 
        }
    }   
}

You can also try this code with Online Java Compiler

Run Code

Input: 

10 20 30 40 50 70 80 60

Output: 

10 30 20 40 50 60 80 70

Time Complexity: O(N), N is the number of nodes. We pushed the items into the stack and popped the items from the stack. So generally, we do two operations. So its time complexity will be upper bounded by 2N.

Space Complexity: O(N).
 

In the above, we learned the approaches to the famous problem, level order traversal in spiral form. Now, Let us see some frequently asked questions.

Also See, Binary Tree Postorder Traversal.

Frequently Asked Questions

What is a binary tree?

A Binary tree is a tree data structure in which every tree node has at most two children. I.e., left and right children.

What is level order traversal in spiral form?

Level order traversal in spiral form means printing the root node first, then visiting right to left or left to right, then seeing from left to right, and so on. (Alternate left to right or right to left).

What is level order traversal?

Level order traversal is the algorithm used in the tree data structure for printing nodes by traversing through depth. i.e., the root node should be printed first. Then we visit left to the right in the tree, then again we visit left to right, and so on.

Which technique is used to implement level order traversal in spiral form?

We use a stack data structure in addition to the level order traversal concept to implement level order traversal in spiral form.

Is BFS (Breadth-First Search) the same as the Level order traversal?

Yes, because Level order traversal is also known as Breadth-First search since it traverses all the nodes at a particular level before going to the next level.

Conclusion

This article discussed the level order tree traversal in spiral form. We have also addressed the algorithm used in both methods.

After reading about level order traversal in spiral form, are you not feeling excited to read/explore more articles on DSA? Don't worry; Coding Ninjas has you covered. To learn, see Level order traversal of a tree, Binary Tree, and Traversals.

Recommended problems -

• Preorder Traversal
• Zig Zag Tree Traversal 

To learn more about DSA, Competitive Programming, System Design, JavaScript, etc., refer to our Guided Path on Coding Ninjas Studio. If you wish to put your coding skills to the test, check out the mock test series and enter the contests hosted by Coding Ninjas Studio! However, suppose you have just begun your learning process and are looking for questions asked by tech giants such as Amazon, Facebook, and Microsoft, among others, In that case you should look at the interview experiences and interview bundle for placement preparations.

Nonetheless, you may want to consider our paid courses to give your career a competitive advantage!

Please vote for the blogs if you find them valuable and exciting!

Happy Learning!