ZigZag Level Order Traversal of an N | C ++ program for the above approach ; Structure of a tree node ; Function to create a new node ; Function to perform zig zag traversal of the given tree ; Stores the vectors containing nodes in each level of tree respectively ; Create a queue for BFS ; Enqueue Root of the tree ; Standard Level Order Traversal code using queue ; Stores the element in the current level ; Iterate over all nodes of the current level ; Insert all children of the current node into the queue ; Insert curLevel into result ; Loop to Print the ZigZag Level order Traversal of the given tree ; If i + 1 is even reverse the order of nodes in the current level ; Print the node of ith level ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int val ; vector < Node * > child ; } ; Node * newNode ( int key ) { Node * temp = new Node ; temp -> val = key ; return temp ; } void zigzagLevelOrder ( Node * root ) { if ( root == NULL ) return ; vector < vector < int > > result ; queue < Node * > q ; q . push ( root ) ; while ( ! q . empty ( ) ) { int size = q . size ( ) ; vector < int > curLevel ; for ( int i = 0 ; i < size ; i ++ ) { Node * node = q . front ( ) ; q . pop ( ) ; curLevel . push_back ( node -> val ) ; for ( int j = 0 ; j < node -> child . size ( ) ; j ++ ) { q . push ( node -> child [ j ] ) ; } } result . push_back ( curLevel ) ; } for ( int i = 0 ; i < result . size ( ) ; i ++ ) { if ( ( i + 1 ) % 2 == 0 ) { reverse ( result [ i ] . begin ( ) , result [ i ] . end ( ) ) ; } for ( int j = 0 ; j < result [ i ] . size ( ) ; j ++ ) { cout << result [ i ] [ j ] << " ▁ " ; } cout << endl ; } } zigzagLevelOrder ( root ) ; return 0 ; }