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 ; Utility function to create a new 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 ; Run this while loop till queue got empty ; 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 traversal . ; Driver program to test above functions ; Let us create binary tree
#include <iostream> NEW_LINE #include <stack> NEW_LINE #include <queue> NEW_LINE using namespace std ; #define LEFT  0 NEW_LINE #define RIGHT  1 NEW_LINE #define ChangeDirection ( Dir )  ((Dir) = 1 - (Dir)) NEW_LINE struct node { int data ; struct node * left , * right ; } ; node * newNode ( int data ) { node * temp = new node ; temp -> data = data ; temp -> left = temp -> right = NULL ; return temp ; } void modifiedLevelOrder ( struct node * root ) { if ( ! root ) return ; int dir = LEFT ; struct node * temp ; queue < struct node * > Q ; stack < struct node * > S ; S . push ( root ) ; while ( ! Q . empty ( ) || ! S . empty ( ) ) { while ( ! S . empty ( ) ) { temp = S . top ( ) ; S . pop ( ) ; cout << temp -> data << " ▁ " ; if ( dir == LEFT ) { if ( temp -> left ) Q . push ( temp -> left ) ; if ( temp -> right ) Q . push ( temp -> right ) ; } else { if ( temp -> right ) Q . push ( temp -> right ) ; if ( temp -> left ) Q . push ( temp -> left ) ; } } cout << endl ; while ( ! Q . empty ( ) ) { temp = Q . front ( ) ; Q . pop ( ) ; cout << temp -> data << " ▁ " ; if ( dir == LEFT ) { if ( temp -> left ) S . push ( temp -> left ) ; if ( temp -> right ) S . push ( temp -> right ) ; } else { if ( temp -> right ) S . push ( temp -> right ) ; if ( temp -> left ) S . push ( temp -> left ) ; } } cout << endl ; ChangeDirection ( dir ) ; } } 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 ; }