1.
Introduction
1.1.
Need for Reverse Level Order Traversal
2.
Reverse level order traversal
2.1.
Example
2.2.
Code
2.3.
Output
3.
3.1.
What is tree data structure?
3.2.
How many types of traversal are there in the tree data structure?
3.3.
Which kind of traversal is most used in tree data structure?
3.4.
What is the time complexity and space complexity of reverse level order traversal?
3.5.
What is the difference between level order traversal and reverse level order traversal?
4.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Reverse level order traversal

Ankit Kumar
1 upvote

## Introduction

In computer science, we use multiple data structures to store the data, and we decide the data structures according to the need of the problem. In this article, we will be focusing on a special type of data structure named 'Tree'. Unlike array data structure, generally in trees, there are four kinds of traversals, namely Inorder, Postorder, Preorder, and Levelorder traversal. But this is gonna be a special type of article that will discuss a modified version of level order traversal, that is, Reverse level order traversal. We will discuss how it's done and will also look over its code and will analyze it on time and space complexities. In the end, we will discuss some of the frequently asked questions related to this topic.

So without wasting much of your time. Let's get started with understanding the need for Reverse level order traversal.

### Need for Reverse Level Order Traversal

In programming, we have many data structures such as arrays, linked lists, stacks, and queues which are linear in nature, which means we can access the stored information in an only method that is linearly accessing each and every data stored in the data structure. But there were many problems in which we needed to access the stored elements non-linearly. Here comes the role of the data structure 'Trees'. It gave us four methods of traversals and thus successfully quenched our thirst for accessing the stored data in multiple ways. The reverse level order is again problem specific way of traversal in which we can print the stored elements in a  reverse level order, which was not possible in other data structures.

Now we understand the requirements of reverse level order traversal. It's high time to move to the next section and learn more about Reverse level order traversal.

## Reverse level order traversal

I hope you know all about level order traversal as learning about reverse level order requires the learning of level order traversal as the maser ingredient.

The reverse level order traversal is similar to level order traversal with only some difference. The fundamental idea behind the reverse level order traversal is that it traverses from the left side of the last level of a tree to the root node and thus displays the result in that order.

Let us now see how it's implemented in programs.

It involves two data structures, queue, and stack, to store the data and eventually implement reverse level order traversal, and it follows the following steps.

Step 1 - Create an empty stack and queue.

Step 2 - Enqueue the root node into the queue

Step 3 - Loop until the queue is empty (loop will include the following three statements.

1. Dequeue the element present in the queue and make it root.

2. Push the root element into the stack

3. Enqueue root node's children from right to left into the queue.

Step 4 - Pop all elements from the stack and print them.

This was how to reverse level order traversal in the tree works. Let us see it with the help of an example.

### Example

Let us consider the following tree shown in the figure below.

The reverse level order for the above example will be 8,9,6,7,5. Let us see how.

First of all, we will create an empty stack and queue and will insert five into the queue. This step will be followed by dequeuing five and assigning them to the root variable. Subsequently, we will be pushing it into the stack. Now the children of root elements 5, which are 7 and 6, will be inserted into the queue. Since the queue follows the First in First out algorithm, element seven will be dequeued, and it will be our new root element. So again, we will insert children of 7 that are 9 and 8 into the queue, and subsequently, we will push seven into the stack. Now in the queue, we have 6,9, and 8. These will be dequeued in this order and will be pushed into the stack.

After completing all these operations, our stack will look like this.

You can try out some of these examples on your own with the help of the above-mentioned steps.

Now, We will see its implementation in the section.

### Code

Although we can implement it in any programming language of our choice, in this article, we will be using C++.

``````// Reverse level order traversal using C++
#include <bits/stdc++.h>
using namespace std;

/* node with data and pointer for its children */

struct node {
int data;
struct node* left;
struct node* right;
};

/*Function to print reverse level order traversal */

void reverseLevelOrder(node* root) {

// stack and queue for storing elements

stack <node *> S;
queue <node *> Q;
// pushing root node
Q.push(root);
// Following the above mentioned steps
while (Q.empty() == false) {

/* Dequeuing node and assigning it to the root variable */

root = Q.front();
Q.pop();
S.push(root);
/* Right child first */
if (root->right)
Q.push(root->right);
/* Enqueuing left child */
if (root->left)
Q.push(root->left);
}

// popping elements and printing it on the screen.

while (S.empty() == false) {
root = S.top();
cout << root->data << " ";
S.pop();
}
}

/* function to create new node assigning null pointer to left and right child */

node* newNode(int data) {
node* temp = new node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return (temp);
}

// main function

int main() {
// tree
struct node *root = newNode(5);
root->left = newNode(6);
root->right = newNode(7);
root->right->left = newNode(8);
root->right->right = newNode(9);
// calling our function
cout << " Reverse Level Order traversal of binary tree is \n";
reverseLevelOrder(root);
return 0;
}``````

Now let us see its output.

### Output

Now let us see some of the frequently asked questions related to this topic.

### What is tree data structure?

Unlike array and linked list trees, the data structure stores the data in a non-linear manner, and they are used in the indexing of databases.

### How many types of traversal are there in the tree data structure?

Generally, there are four types of traversal methods in the tree data structure that are preorder, postorder, in order, and level order traversal. However, we can derive some more kinds of traversals like reverse level order traversal, as discussed in this article.

### Which kind of traversal is most used in tree data structure?

Inorder traversal is one of the most used traversal methods in the tree data structure.

### What is the time complexity and space complexity of reverse level order traversal?

The time complexity for reverse level order traversal is O(N), and space complexity is O(N) as we are using stack and queue for storing the nodes while traversing.

### What is the difference between level order traversal and reverse level order traversal?

Though they are very similar to each other, the only difference between them is that the reverse level order traversal prints the reverse of level order traversal.

## Conclusion

In this article, we have extensively discussed reverse level order traversal and its implementation in C++. We also used some examples to make it easier to understand.

After reading about Reverse level order traversal, are you not feeling excited to read/explore more articles on related topics? Don't worry. Coding ninjas has you covered. To learn more, see  Level order traversal with direction change after every two levelsConstructing a binary tree from two traversal SequencesPerfect Binary Tree Specific Level Order Traversal, Reverse a Stack using Recursion or you can also try out some Gate Questions on Tree Traversal.

Recommended problems -

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc., you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!