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:
- Take a Stack of integer and Queue of TreeNode pointer and insert the root TreeNode in the Queue.
- Now get the front element of Queue and add it in Stack.
- 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.
- Do the second and third step iteratively until the Queue becomes empty.
- 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
Leave a Reply