ZigZag Level Order Traversal of an N | 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
class Node { constructor ( key ) { this . child = [ ] ; this . val = key ; } } function newNode ( key ) { let temp = new Node ( key ) ; return temp ; } function zigzagLevelOrder ( root ) { if ( root == null ) return ; let result = [ ] ; let q = [ ] ; q . push ( root ) ; while ( q . length > 0 ) { let size = q . length ; let curLevel = [ ] ; for ( let i = 0 ; i < size ; i ++ ) { let node = q [ 0 ] ; q . shift ( ) ; curLevel . push ( node . val ) ; for ( let j = 0 ; j < ( node . child ) . length ; j ++ ) q . push ( node . child [ j ] ) ; } result . push ( curLevel ) ; } for ( let i = 0 ; i < result . length ; i ++ ) { if ( ( i + 1 ) % 2 == 0 ) { result [ i ] . reverse ( ) ; } for ( let j = 0 ; j < result [ i ] . length ; j ++ ) document . write ( result [ i ] [ j ] + " " ) ; document . write ( " " ) ; } } let root = newNode ( 1 ) ; ( root . child ) . push ( newNode ( 2 ) ) ; ( root . child ) . push ( newNode ( 3 ) ) ; ( root . child [ 0 ] . child ) . push ( newNode ( 4 ) ) ; ( root . child [ 0 ] . child ) . push ( newNode ( 5 ) ) ; ( root . child [ 1 ] . child ) . push ( newNode ( 6 ) ) ; ( root . child [ 1 ] ) . child . push ( newNode ( 7 ) ) ; ( root . child [ 1 ] . child ) . push ( newNode ( 8 ) ) ; zigzagLevelOrder ( root ) ;