ZigZag Level Order Traversal of an N | Java program for the above approach ; Class containing left and right child of current node and key value ; 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
import java . util . * ; public class Main { static class Node { public int val ; public Vector < Node > child ; public Node ( int key ) { val = key ; child = new Vector < Node > ( ) ; } } static Node newNode ( int key ) { Node temp = new Node ( key ) ; return temp ; } static void zigzagLevelOrder ( Node root ) { if ( root == null ) return ; Vector < Vector < Integer > > result = new Vector < Vector < Integer > > ( ) ; Vector < Node > q = new Vector < Node > ( ) ; q . add ( root ) ; while ( q . size ( ) > 0 ) { int size = q . size ( ) ; Vector < Integer > curLevel = new Vector < Integer > ( ) ; for ( int i = 0 ; i < size ; i ++ ) { Node node = q . get ( 0 ) ; q . remove ( 0 ) ; curLevel . add ( node . val ) ; for ( int j = 0 ; j < ( node . child ) . size ( ) ; j ++ ) q . add ( node . child . get ( j ) ) ; } result . add ( curLevel ) ; } for ( int i = 0 ; i < result . size ( ) ; i ++ ) { if ( ( i + 1 ) % 2 == 0 ) { Collections . reverse ( result . get ( i ) ) ; } for ( int j = 0 ; j < result . get ( i ) . size ( ) ; j ++ ) System . out . print ( result . get ( i ) . get ( j ) + " ▁ " ) ; System . out . println ( ) ; } } public static void main ( String [ ] args ) { Node root = newNode ( 1 ) ; ( root . child ) . add ( newNode ( 2 ) ) ; ( root . child ) . add ( newNode ( 3 ) ) ; ( root . child . get ( 0 ) . child ) . add ( newNode ( 4 ) ) ; ( root . child . get ( 0 ) . child ) . add ( newNode ( 5 ) ) ; ( root . child . get ( 1 ) . child ) . add ( newNode ( 6 ) ) ; ( root . child . get ( 1 ) ) . child . add ( newNode ( 7 ) ) ; ( root . child . get ( 1 ) . child ) . add ( newNode ( 8 ) ) ; zigzagLevelOrder ( root ) ; } }