0
Reverse Level Order Traversal
Write a program to print Reverse Level Order Traversal of a binary tree.
Example:
Basic level order traversal:
2
7 5
2 6 9
5 11 4
Reverse Level order traversal:
5 11 4
2 6 9
7 5
2 
C++ programming
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