Level order traversal with direction change after every two levels | A Binary Tree Node ; Function to prthe level order of given binary tree . Direction of printing level order traversal of binary tree changes after every two levels ; For null root ; Maintain a queue for normal level order traversal ; Maintain a stack for printing nodes in reverse order after they are popped out from queue . ; sz is used for storing the count of nodes in a level ; Used for changing the direction of level order traversal ; Used for changing the direction of level order traversal ; Push root node to the queue ; Run this while loop till queue got empty ; Do a normal level order traversal ; For printing nodes from left to right , simply prthe nodes in the order in which they are being popped out from the queue . ; 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 printing nodes after every two levels . ; Driver program to test above functions ; Let us create binary tree
from collections import deque NEW_LINE class Node : NEW_LINE INDENT def __init__ ( self , x ) : NEW_LINE INDENT self . data = x NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def modifiedLevelOrder ( node ) : NEW_LINE INDENT if ( node == None ) : NEW_LINE INDENT return NEW_LINE DEDENT if ( node . left == None and node . right == None ) : NEW_LINE INDENT print ( node . data , end = " ▁ " ) NEW_LINE return NEW_LINE DEDENT myQueue = deque ( ) NEW_LINE myStack = [ ] NEW_LINE temp = None NEW_LINE sz = 0 NEW_LINE ct = 0 NEW_LINE rightToLeft = False NEW_LINE myQueue . append ( node ) NEW_LINE while ( len ( myQueue ) > 0 ) : NEW_LINE INDENT ct += 1 NEW_LINE sz = len ( myQueue ) NEW_LINE for i in range ( sz ) : NEW_LINE INDENT temp = myQueue . popleft ( ) NEW_LINE if ( rightToLeft == False ) : NEW_LINE INDENT print ( temp . data , end = " ▁ " ) NEW_LINE DEDENT else : NEW_LINE INDENT myStack . append ( temp ) NEW_LINE DEDENT if ( temp . left ) : NEW_LINE INDENT myQueue . append ( temp . left ) NEW_LINE DEDENT if ( temp . right ) : NEW_LINE INDENT myQueue . append ( temp . right ) NEW_LINE DEDENT DEDENT if ( rightToLeft == True ) : NEW_LINE INDENT while ( len ( myStack ) > 0 ) : NEW_LINE INDENT temp = myStack [ - 1 ] NEW_LINE del myStack [ - 1 ] NEW_LINE print ( temp . data , end = " ▁ " ) NEW_LINE DEDENT DEDENT if ( ct == 2 ) : NEW_LINE INDENT rightToLeft = not rightToLeft NEW_LINE ct = 0 NEW_LINE DEDENT print ( ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = Node ( 1 ) NEW_LINE root . left = Node ( 2 ) NEW_LINE root . right = Node ( 3 ) NEW_LINE root . left . left = Node ( 4 ) NEW_LINE root . left . right = Node ( 5 ) NEW_LINE root . right . left = Node ( 6 ) NEW_LINE root . right . right = Node ( 7 ) NEW_LINE root . left . left . left = Node ( 8 ) NEW_LINE root . left . left . right = Node ( 9 ) NEW_LINE root . left . right . left = Node ( 3 ) NEW_LINE root . left . right . right = Node ( 1 ) NEW_LINE root . right . left . left = Node ( 4 ) NEW_LINE root . right . left . right = Node ( 2 ) NEW_LINE root . right . right . left = Node ( 7 ) NEW_LINE root . right . right . right = Node ( 2 ) NEW_LINE root . left . right . left . left = Node ( 16 ) NEW_LINE root . left . right . left . right = Node ( 17 ) NEW_LINE root . right . left . right . left = Node ( 18 ) NEW_LINE root . right . right . left . right = Node ( 19 ) NEW_LINE modifiedLevelOrder ( root ) NEW_LINE DEDENT