Reverse level order traversal

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

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

Run Code

Now let us see its output.

Output

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