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
using System ; using System . Collections . Generic ; class GFG { class Node { public int val ; public List < Node > child ; public Node ( int key ) { val = key ; child = new List < Node > ( ) ; } } static Node newNode ( int key ) { Node temp = new Node ( key ) ; return temp ; } static void zigzagLevelOrder ( Node root ) { if ( root == null ) return ; List < List < int > > result = new List < List < int > > ( ) ; List < Node > q = new List < Node > ( ) ; q . Add ( root ) ; while ( q . Count > 0 ) { int size = q . Count ; List < int > curLevel = new List < int > ( ) ; for ( int i = 0 ; i < size ; i ++ ) { Node node = q [ 0 ] ; q . RemoveAt ( 0 ) ; curLevel . Add ( node . val ) ; for ( int j = 0 ; j < ( node . child ) . Count ; j ++ ) q . Add ( node . child [ j ] ) ; } result . Add ( curLevel ) ; } for ( int i = 0 ; i < result . Count ; i ++ ) { if ( ( i + 1 ) % 2 == 0 ) { result [ i ] . Reverse ( ) ; } for ( int j = 0 ; j < result [ i ] . Count ; j ++ ) Console . Write ( result [ i ] [ j ] + " ▁ " ) ; Console . WriteLine ( ) ; } } static void Main ( ) { Node root = newNode ( 1 ) ; ( root . child ) . Add ( newNode ( 2 ) ) ; ( root . child ) . Add ( newNode ( 3 ) ) ; ( root . child [ 0 ] . child ) . Add ( newNode ( 4 ) ) ; ( root . child [ 0 ] . child ) . Add ( newNode ( 5 ) ) ; ( root . child [ 1 ] . child ) . Add ( newNode ( 6 ) ) ; ( root . child [ 1 ] ) . child . Add ( newNode ( 7 ) ) ; ( root . child [ 1 ] . child ) . Add ( newNode ( 8 ) ) ; zigzagLevelOrder ( root ) ; } }