Of course the solution is quite like the level order traversal just a little bit of modification.
Algorithm:
FUNCTION reverseLevelOrder (root): prints reverse Level order traversal of the tree
Prerequisite: Queue q, Stack s
FUNCTION reverseLevelOrder(root)// root of the tree
1. Declare a TreeNode type variable temp;
2. Declare qto store nodes //creating a queue
3. Declare sfor reversal
4. IF (!root) //root is null
return;
5. EnQueue(q,root); // EnQueue the root in the queue
6. while(q is not empty){
temp=DeQueue(q); //Dequeue
s.push(temp->data); //push temp->data to stack
IF(temp->right)//this is different from ordinary level-order
EnQueue(q,temp->right); // if right child exists EnQueue
END IF
IF(temp->left)
EnQueue(q,temp->left); // if left child exists EnQueue
END IF
END While
7. While(s is not empty)
Pop and print
END While
8. DeleteQueue(q);
9. DeleteStack(s);
Example with explanation:
N.B: The nodes are represented by their respective values.
For the above example:
In the main we call reverseLevelOrder (2)
------------------------------------------------------------
reverseLevelOrder (2)
q.push(2)//EnQueue the root
------------------------------------------------------------
1st iteration:
q is not empty
temp= q.front()=2
q.pop()
Queue status:
Empty Queue
s.push(temp->data) //2
2->right not NULL
q.push(2->right) //q.push(5)
2->left not NULL
q.push(2->left)//q.push(7)
Queue status:
5 7
------------------------------------------------------------
2nd iteration:
q is not empty
temp= q.front()=5
q.pop()
Queue status:
7
s.push(temp->data) //5
5->right not NULL
q.push(5->right) //q.push(9)
5->leftNULL
Queue status:
7 9
------------------------------------------------------------
3rd iteration:
q is not empty
temp= q.front()=7
q.pop()
Queue status:
9
s.push(temp->data) //7
7->right not NULL
q.push(7->right) //q.push(6)
7->left not NULL
q.push(7->left) //q.push(2)
Queue status:
9 6 2
------------------------------------------------------------
4th iteration:
q is not empty
temp= q.front()=9
q.pop()
Queue status:
6 2
s.push(temp->data) //9
9->rightNULL
9->left not NULL
q.push(9->left) //q.push(4)
Queue status:
6 2 4
------------------------------------------------------------
5th iteration:
q is not empty
temp= q.front()=6
q.pop()
Queue status:
2 4
s.push(temp->data) //6
6->right not NULL
q.push(6->right) //q.push(11)
9->left not NULL
q.push(6->left) //q.push(5)
Queue status:
2 4 11 5
------------------------------------------------------------
6th iteration:
q is not empty
temp= q.front()=2
q.pop()
Queue status:
4 11 5
s.push(temp->data) //2
2->rightNULL
2->left NULL
Queue status:
4 11 5
------------------------------------------------------------
7th iteration:
q is not empty
temp= q.front()=4
q.pop()
Queue status:
11 5
s.push(temp->data) //4
4->right NULL
4->left NULL
Queue status:
11 5
------------------------------------------------------------
8th iteration:
q is not empty
temp= q.front()=11
q.pop()
Queue status:
5
s.push(temp->data) //11
11->right NULL
11->left NULL
Queue status:
5
------------------------------------------------------------
9th iteration:
q is not empty
temp= q.front()=5
q.pop()
Queue status:
Empty queue
s.push(temp->data) //5
5->right NULL
5->left NULL
Queue status:
Empty Queue
------------------------------------------------------------
10th iteration:
Empty Queue
Final stack status:
5
11
4
2
6
9
7
5
2
Pop and print:
Output:
5 11 4 2 6 9 7 5 2
C++ implementation:
#include <bits/stdc++.h>
using namespace std;
class Node{ // tree node is defined
public:
int data;
Node *left;
Node *right;
};
void reverseLevelOrder(Node *root)
{
Node* temp;
stack<int> s;
queue<Node*> q;
q.push(root);
while(!q.empty()){
temp=q.front();
q.pop();
s.push(temp->data);
if(temp->right)
q.push(temp->right);
if(temp->left)
q.push(temp->left);
}
while(!s.empty()){
cout<<s.top()<<" ";
s.pop();
}
}
Node* newnode(int data) // creating new node
{
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main() {
//**same tree is builted as shown in example**
Node *root=newnode(2);
root->left= newnode(7);
root->right= newnode(5);
root->right->right=newnode(9);
root->right->right->left=newnode(4);
root->left->left=newnode(2);
root->left->right=newnode(6);
root->left->right->left=newnode(5);
root->left->right->right=newnode(11);
cout<<"Reverse Level Order traversal of binary tree is :"<<endl;
reverseLevelOrder(root);
return 0;
}
Output
Reverse Level Order traversal of binary tree is :
5 11 4 2 6 9 7 5 2
Of course the solution is quite like the level order traversal just a little bit of modification.
Algorithm:
FUNCTION reverseLevelOrder (root): prints reverse Level order traversal of the tree
Prerequisite: Queue q, Stack s
FUNCTION reverseLevelOrder(root)// root of the tree 1. Declare a TreeNode type variable temp; 2. Declare qto store nodes //creating a queue 3. Declare sfor reversal 4. IF (!root) //root is null return; 5. EnQueue(q,root); // EnQueue the root in the queue 6. while(q is not empty){ temp=DeQueue(q); //Dequeue s.push(temp->data); //push temp->data to stack IF(temp->right)//this is different from ordinary level-order EnQueue(q,temp->right); // if right child exists EnQueue END IF IF(temp->left) EnQueue(q,temp->left); // if left child exists EnQueue END IF END While 7. While(s is not empty) Pop and print END While 8. DeleteQueue(q); 9. DeleteStack(s);Example with explanation:
N.B: The nodes are represented by their respective values.
For the above example:
In the main we call reverseLevelOrder (2) ------------------------------------------------------------ reverseLevelOrder (2) q.push(2)//EnQueue the root ------------------------------------------------------------ 1st iteration: q is not empty temp= q.front()=2 q.pop() Queue status: Empty Queue s.push(temp->data) //2 2->right not NULL q.push(2->right) //q.push(5) 2->left not NULL q.push(2->left)//q.push(7) Queue status: 5 7 ------------------------------------------------------------ 2nd iteration: q is not empty temp= q.front()=5 q.pop() Queue status: 7 s.push(temp->data) //5 5->right not NULL q.push(5->right) //q.push(9) 5->leftNULL Queue status: 7 9 ------------------------------------------------------------ 3rd iteration: q is not empty temp= q.front()=7 q.pop() Queue status: 9 s.push(temp->data) //7 7->right not NULL q.push(7->right) //q.push(6) 7->left not NULL q.push(7->left) //q.push(2) Queue status: 9 6 2 ------------------------------------------------------------ 4th iteration: q is not empty temp= q.front()=9 q.pop() Queue status: 6 2 s.push(temp->data) //9 9->rightNULL 9->left not NULL q.push(9->left) //q.push(4) Queue status: 6 2 4 ------------------------------------------------------------ 5th iteration: q is not empty temp= q.front()=6 q.pop() Queue status: 2 4 s.push(temp->data) //6 6->right not NULL q.push(6->right) //q.push(11) 9->left not NULL q.push(6->left) //q.push(5) Queue status: 2 4 11 5 ------------------------------------------------------------ 6th iteration: q is not empty temp= q.front()=2 q.pop() Queue status: 4 11 5 s.push(temp->data) //2 2->rightNULL 2->left NULL Queue status: 4 11 5 ------------------------------------------------------------ 7th iteration: q is not empty temp= q.front()=4 q.pop() Queue status: 11 5 s.push(temp->data) //4 4->right NULL 4->left NULL Queue status: 11 5 ------------------------------------------------------------ 8th iteration: q is not empty temp= q.front()=11 q.pop() Queue status: 5 s.push(temp->data) //11 11->right NULL 11->left NULL Queue status: 5 ------------------------------------------------------------ 9th iteration: q is not empty temp= q.front()=5 q.pop() Queue status: Empty queue s.push(temp->data) //5 5->right NULL 5->left NULL Queue status: Empty Queue ------------------------------------------------------------ 10th iteration: Empty Queue Final stack status: 5 11 4 2 6 9 7 5 2 Pop and print: Output: 5 11 4 2 6 9 7 5 2C++ implementation:
Output
need an explanation for this answer? contact us directly to get an explanation for this answer