Reverse alternate levels of a perfect binary tree | Python3 program to reverse alternate levels of a binary tree ; A Binary Tree node ; A utility function to create a new Binary Tree Node ; Function to store nodes of alternate levels in an array ; Base case ; Store elements of left subtree ; Store this node only if this is a odd level node ; Function to modify Binary Tree ( All odd level nodes areupdated by taking elements from array in inorder fashion ) ; Base case ; Update nodes in left subtree ; Update this node only if this is an odd level node ; Update nodes in right subtree ; A utility function to reverse an array from index 0 to n - 1 ; The main function to reverse alternate nodes of a binary tree ; Create an auxiliary array to store nodes of alternate levels ; First store nodes of alternate levels ; Reverse the array ; Update tree by taking elements from array ; A utility function to print indorder traversal of a binary tree ; Driver code
MAX = 100 NEW_LINE class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . left = None NEW_LINE self . right = None NEW_LINE self . data = data NEW_LINE DEDENT DEDENT def newNode ( item ) : NEW_LINE INDENT temp = Node ( item ) NEW_LINE return temp NEW_LINE DEDENT def storeAlternate ( root , arr , index , l ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return index ; NEW_LINE DEDENT index = storeAlternate ( root . left , arr , index , l + 1 ) ; NEW_LINE if ( l % 2 != 0 ) : NEW_LINE INDENT arr [ index ] = root . data ; NEW_LINE index += 1 ; NEW_LINE DEDENT index = storeAlternate ( root . right , arr , index , l + 1 ) ; NEW_LINE return index NEW_LINE DEDENT def modifyTree ( root , arr , index , l ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return index ; NEW_LINE DEDENT index = modifyTree ( root . left , arr , index , l + 1 ) ; NEW_LINE if ( l % 2 != 0 ) : NEW_LINE INDENT root . data = arr [ index ] ; NEW_LINE index += 1 ; NEW_LINE DEDENT index = modifyTree ( root . right , arr , index , l + 1 ) ; NEW_LINE return index NEW_LINE DEDENT def reverse ( arr , n ) : NEW_LINE INDENT l = 0 NEW_LINE r = n - 1 ; NEW_LINE while ( l < r ) : NEW_LINE INDENT arr [ l ] , arr [ r ] = ( arr [ r ] , arr [ l ] ) ; NEW_LINE l += 1 NEW_LINE r -= 1 NEW_LINE DEDENT DEDENT def reverseAlternate ( root ) : NEW_LINE INDENT arr = [ 0 for i in range ( MAX ) ] NEW_LINE index = 0 ; NEW_LINE index = storeAlternate ( root , arr , index , 0 ) ; NEW_LINE reverse ( arr , index ) ; NEW_LINE index = 0 ; NEW_LINE index = modifyTree ( root , arr , index , 0 ) ; NEW_LINE DEDENT def printInorder ( root ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return ; NEW_LINE DEDENT printInorder ( root . left ) ; NEW_LINE print ( root . data , end = ' ▁ ' ) NEW_LINE printInorder ( root . right ) ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT root = newNode ( ' a ' ) ; NEW_LINE root . left = newNode ( ' b ' ) ; NEW_LINE root . right = newNode ( ' c ' ) ; NEW_LINE root . left . left = newNode ( ' d ' ) ; NEW_LINE root . left . right = newNode ( ' e ' ) ; NEW_LINE root . right . left = newNode ( ' f ' ) ; NEW_LINE root . right . right = newNode ( ' g ' ) ; NEW_LINE root . left . left . left = newNode ( ' h ' ) ; NEW_LINE root . left . left . right = newNode ( ' i ' ) ; NEW_LINE root . left . right . left = newNode ( ' j ' ) ; NEW_LINE root . left . right . right = newNode ( ' k ' ) ; NEW_LINE root . right . left . left = newNode ( ' l ' ) ; NEW_LINE root . right . left . right = newNode ( ' m ' ) ; NEW_LINE root . right . right . left = newNode ( ' n ' ) ; NEW_LINE root . right . right . right = newNode ( ' o ' ) ; NEW_LINE print ( " Inorder ▁ Traversal ▁ of ▁ given ▁ tree " ) NEW_LINE printInorder ( root ) ; NEW_LINE reverseAlternate ( root ) ; NEW_LINE print ( " Inorder Traversal of modified tree " ) NEW_LINE printInorder ( root ) ; NEW_LINE DEDENT