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.

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.

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.

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 mocktest 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!