Reverse Level Order Traversal of Binary Tree in C++

In this article, we will learn how to reverse the level order traversal of binary tree in C++. The level order traversal is quite easy and the trick is to maintain a queue and print the elements in it. But for this topic, we have to maintain a stack additionally. If you don’t know about level order traversal of the binary tree then go through this link-Breadth first search (BFS) and Depth first search (DFS) for a Graph in C++ . Here see the BFS part.

C++ program for reverse level order traversal of binary tree

Let’s quickly understand with a simple example:

For the above tree the output should be:
4 5 6 7 2 3 1

Algorithm:

1. Take a Stack of integer and Queue of TreeNode pointer and insert the root TreeNode in the Queue.
2. Now get the front element of Queue and add it in Stack.
3. Push the right and then the left child of the front element in the Queue(If the child is not NULL) and remove the element from Queue.
4. Do the second and third step iteratively until the Queue becomes empty.
5. Now retrieve the elements from Stack and print it.

Implementation of the above algorithm:

At first, build the structure of the TreeNode:

#include<bits/stdc++.h>
using namespace std;
struct  TreeNode
{
    int value;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int data){
        value=data;
        left=right=NULL;
    }
};

Then build a function which gets root TreeNode as an argument:

void reverseLevelOrder(TreeNode* root){
    if(root==NULL)//if root is NULL then return immediately
         return;
    queue<TreeNode*>q;//declare queue of TreeNode pointer
    stack<int>s; //declare stack of integer
    q.push(root);//push the root to the queue
    TreeNode* temp=NULL;
 //Now iterate the queue until it becomes empty and get the elements in stack
    while(!q.empty()){
        temp=q.front();
        s.push(temp->value);
        if(temp->right!=NULL)
            q.push(temp->right);
        if(temp->left!=NULL)
            q.push(temp->left);
        q.pop();
    }
    //retrieve the elements from the stack
    while(!s.empty()){
        cout<<s.top()<<" ";
        s.pop();
    }
}

Now add the main function and let’s build the tree shown in the example and call the reverseLevelOrder function:

int main(){
    TreeNode* root=new TreeNode(1);
    root->left=new TreeNode(2);
    root->right=new TreeNode(3);
    root->left->left=new TreeNode(4);
    root->left->right=new TreeNode(5);
    root->right->left=new TreeNode(6);
    root->right->right=new TreeNode(7);
    reverseLevelOrder(root);
    return 0;
}

the output is:

4 5 6 7 2 3 1