Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Overview
2.
Problem Statement
3.
Example
4.
Method 1
4.1.
Algorithm
4.2.
Implementation in C++
4.3.
Implementation in Java
5.
Method 2
5.1.
Algorithm 
5.2.
Implementation in C++
5.3.
Implementation in Java
6.
Frequently Asked Questions
6.1.
What is a binary tree?
6.2.
What is level order traversal in spiral form?
6.3.
What is level order traversal?
6.4.
Which technique is used to implement level order traversal in spiral form?
6.5.
Is BFS (Breadth-First Search) the same as the Level order traversal?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Level Order Traversal in Spiral Form

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Overview

We will learn how to do level order traversal in the spiral form of a tree. We will also see the implementation in C++ and in Java with their time complexity and space complexity. Generally, we will see the two approaches of level order traversal in spiral form, i.e., first using one stack and the other using two stacks.

At last, we will see some frequently asked questions.

Problem Statement

We have a binary tree. We need to do level order traversal in spiral form. This means we have to print the nodes in level order in spiral form, i.e., nodes at level 1(root) should be published first from left to right, followed by nodes at level 2 from right to left, and so on or vice-versa.

In the Level Order Traversal, the binary tree is traversed, starting from the first to the last level sequentially.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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);
}

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;
        }
    }   
}

 

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);
}

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); 
            } 
        }
    }   
}

 

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 treeBinary Tree, and Traversals.

Recommended problems -

 

To learn more about DSA, Competitive ProgrammingSystem 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!

Previous article
Morris Traversal
Next article
Level order traversal line by line
Live masterclass