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 : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . val = key NEW_LINE self . child = [ ] NEW_LINE DEDENT DEDENT def newNode ( key ) : NEW_LINE INDENT temp = Node ( key ) NEW_LINE return temp NEW_LINE DEDENT def zigzagLevelOrder ( root ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return NEW_LINE DEDENT result = [ ] NEW_LINE q = [ ] NEW_LINE q . append ( root ) NEW_LINE while len ( q ) > 0 : NEW_LINE INDENT size = len ( q ) NEW_LINE curLevel = [ ] NEW_LINE for i in range ( size ) : NEW_LINE INDENT node = q [ 0 ] NEW_LINE q . pop ( 0 ) NEW_LINE curLevel . append ( node . val ) NEW_LINE for j in range ( len ( node . child ) ) : NEW_LINE INDENT q . append ( node . child [ j ] ) NEW_LINE DEDENT DEDENT result . append ( curLevel ) NEW_LINE DEDENT for i in range ( len ( result ) ) : NEW_LINE INDENT if ( ( i + 1 ) % 2 == 0 ) : NEW_LINE INDENT result [ i ] . reverse ( ) NEW_LINE DEDENT for j in range ( len ( result [ i ] ) ) : NEW_LINE INDENT print ( result [ i ] [ j ] , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT DEDENT root = newNode ( 1 ) NEW_LINE ( root . child ) . append ( newNode ( 2 ) ) NEW_LINE ( root . child ) . append ( newNode ( 3 ) ) NEW_LINE ( root . child [ 0 ] . child ) . append ( newNode ( 4 ) ) NEW_LINE ( root . child [ 0 ] . child ) . append ( newNode ( 5 ) ) NEW_LINE ( root . child [ 1 ] . child ) . append ( newNode ( 6 ) ) NEW_LINE ( root . child [ 1 ] ) . child . append ( newNode ( 7 ) ) NEW_LINE ( root . child [ 1 ] . child ) . append ( newNode ( 8 ) ) NEW_LINE zigzagLevelOrder ( root ) NEW_LINE