Level order traversal with direction change after every two levels | CPP program to print Zig - Zag traversal in groups of size 2. ; A Binary Tree Node ; Function to print the level order of given binary tree . Direction of printing level order traversal of binary tree changes after every two levels ; For null root ; Maintain a queue for normal level order traversal ; Maintain a stack for printing nodes in reverse order after they are popped out from queue . ; sz is used for storing the count of nodes in a level ; Used for changing the direction of level order traversal ; Used for changing the direction of level order traversal ; Push root node to the queue ; Run this while loop till queue got empty ; Do a normal level order traversal ; For printing nodes from left to right , simply print the nodes in the order in which they are being popped out from the queue . ; For printing nodes from right to left , push the nodes to stack instead of printing them . ; for printing the nodes in order from right to left ; Change the direction of printing nodes after every two levels . ; Utility function to create a new tree node ; Driver program to test above functions ; Let us create binary tree
#include <iostream> NEW_LINE #include <queue> NEW_LINE #include <stack> NEW_LINE using namespace std ; struct Node { struct Node * left ; int data ; struct Node * right ; } ; void modifiedLevelOrder ( struct Node * node ) { if ( node == NULL ) return ; if ( node -> left == NULL && node -> right == NULL ) { cout << node -> data ; return ; } queue < Node * > myQueue ; stack < Node * > myStack ; struct Node * temp = NULL ; int sz ; int ct = 0 ; bool rightToLeft = false ; myQueue . push ( node ) ; while ( ! myQueue . empty ( ) ) { ct ++ ; sz = myQueue . size ( ) ; for ( int i = 0 ; i < sz ; i ++ ) { temp = myQueue . front ( ) ; myQueue . pop ( ) ; if ( rightToLeft == false ) cout << temp -> data << " ▁ " ; else myStack . push ( temp ) ; if ( temp -> left ) myQueue . push ( temp -> left ) ; if ( temp -> right ) myQueue . push ( temp -> right ) ; } if ( rightToLeft == true ) { while ( ! myStack . empty ( ) ) { temp = myStack . top ( ) ; myStack . pop ( ) ; cout << temp -> data << " ▁ " ; } } if ( ct == 2 ) { rightToLeft = ! rightToLeft ; ct = 0 ; } cout << " STRNEWLINE " ; } } Node * newNode ( int data ) { Node * temp = new Node ; temp -> data = data ; temp -> left = temp -> right = NULL ; return temp ; } int main ( ) { 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 ) ; root -> left -> left -> left = newNode ( 8 ) ; root -> left -> left -> right = newNode ( 9 ) ; root -> left -> right -> left = newNode ( 3 ) ; root -> left -> right -> right = newNode ( 1 ) ; root -> right -> left -> left = newNode ( 4 ) ; root -> right -> left -> right = newNode ( 2 ) ; root -> right -> right -> left = newNode ( 7 ) ; root -> right -> right -> right = newNode ( 2 ) ; root -> left -> right -> left -> left = newNode ( 16 ) ; root -> left -> right -> left -> right = newNode ( 17 ) ; root -> right -> left -> right -> left = newNode ( 18 ) ; root -> right -> right -> left -> right = newNode ( 19 ) ; modifiedLevelOrder ( root ) ; return 0 ; }