Display Reverse Level Order Traversal by using queue

Question:

Given a binary tree root node, display all the nodes in reverse level order traversal.

Example:

Consider the image given below:

Form the image above, reverse level order traversal is: 7, 15, 18, 30, 10, 25, 16

Solution:

Solution is similar to level order traversal, with one difference.

Here we should use Stack and Queue.

Idea here is to do level order traversal, while dequeuing the elements, push those elements into the stack.

While pushing the elements into stack, push the right child first and then the left child.

Example:

1. If we have only one node, as shown below:

Root node doesn’t have left or right node. So remove from queue and put into stack. As the tree is empty, remove from stack and display.

2. If we have 2 nodes, as shown below:

First insert root node into queue.
Pop from queue and insert into stack.

Queue: Empty
Stack: 16

Next go to right child, and insert into queue

Queue: 25
Stack: 16

Next go to left child, and insert into queue

Queue: 25, 10
Stack: 16

Now, pop both of the elements and insert into stack

Queue: NULL
Stack: 16, 10, 25

As the tree is NULL, display stack contents.

 

Solution in C++

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};


void display_reverse_level_order(Node *root) 
{ 
    stack <Node *> my_stack; 
    queue <Node *> my_queue; 
    my_queue.push(root); 
  

    while (my_queue.empty() == false) 
    { 
        // Dequeue node and make it root
        root = my_queue.front(); 
        my_queue.pop(); 
        my_stack.push(root); 
  
        // Enqueue right child 
        if (root->right) 
            my_queue.push(root->right);
  
        // Enqueue left child 
        if (root->left) 
            my_queue.push(root->left); 
    } 
  
    // display all the elements in stack 
    while (my_stack.empty() == false) 
    { 
        root = my_stack.top(); 
        cout << root->data << " "; 
        my_stack.pop(); 
    } 
} 

int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    int level = 2;

    cout<<"Solution = " <<endl;
    display_reverse_level_order(root); 

    return 0;  
}  

Output:

Solution =
7 15 18 30 10 25 16