Reverse Level Order Traversal of Binary Tree using Stacks and Queues

ReverseLevelOrder.cpp

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

// Node Structure 
struct Node
{
    int data;
    struct Node* left;
    struct Node* right;
};

//Utility function
Node* newNode(int data)
{
    Node* temp = new Node;
    temp-> data = data;
    temp->left = NULL;
    temp-> right = NULL;
      return (temp);
}

// print nodes in reverse order
void ReverseLevelOrder( Node* root)
{
    stack <Node * > S; 
    queue <Node * > Q;
    Q.push(root);
     // 1) Instead of printing a node, we push the node to stack 
    // 2) Right subtree is visited before left subtree
    
    while(Q.empty() == false )
    {
        root = Q.front();
        Q.pop();
        S.push(root);
        
        //Enqueue right child
        if(root->right)
        Q.push(root->right);
        
        //Enqueue left child
        if(root->left)
        Q.push(root->left);
        }
        //pop stack one by one to print them
        while(S.empty() == false)
        {
            root = S.top();
            cout << root->data << " ";
            S.pop();            
        }
   
}
//Driver Function
int main() {
    struct Node *root = newNode(1); 
    root->left        = newNode(2); 
    root->right       = newNode(3); 
    root->left->left  = newNode(4); 
    root->left->right = newNode(5); 
    root->right->left  = newNode(6); 
    root->right->right = newNode(7); 
  
    cout << "Level Order traversal of binary tree is \n"; 
    ReverseLevelOrder(root); 
  return 0;
}