Level order traversal with direction change after every two levels | JAVA 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 code ; Let us create binary tree
import java . util . * ; class GFG { static final int LEFT = 0 ; static final int RIGHT = 1 ; static int ChangeDirection ( int Dir ) { Dir = 1 - Dir ; return Dir ; } static class node { int data ; node left , right ; } ; static node newNode ( int data ) { node temp = new node ( ) ; temp . data = data ; temp . left = temp . right = null ; return temp ; } static void modifiedLevelOrder ( node root ) { if ( root == null ) return ; int dir = LEFT ; node temp ; Queue < node > Q = new LinkedList < > ( ) ; Stack < node > S = new Stack < > ( ) ; S . add ( root ) ; while ( ! Q . isEmpty ( ) || ! S . isEmpty ( ) ) { while ( ! S . isEmpty ( ) ) { temp = S . peek ( ) ; S . pop ( ) ; System . out . print ( temp . data + " ▁ " ) ; if ( dir == LEFT ) { if ( temp . left != null ) Q . add ( temp . left ) ; if ( temp . right != null ) Q . add ( temp . right ) ; } else { if ( temp . right != null ) Q . add ( temp . right ) ; if ( temp . left != null ) Q . add ( temp . left ) ; } } System . out . println ( ) ; while ( ! Q . isEmpty ( ) ) { temp = Q . peek ( ) ; Q . remove ( ) ; System . out . print ( temp . data + " ▁ " ) ; if ( dir == LEFT ) { if ( temp . left != null ) S . add ( temp . left ) ; if ( temp . right != null ) S . add ( temp . right ) ; } else { if ( temp . right != null ) S . add ( temp . right ) ; if ( temp . left != null ) S . add ( temp . left ) ; } } System . out . println ( ) ; dir = ChangeDirection ( dir ) ; } } public static void main ( String [ ] args ) { 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 ) ; } }