Sink Odd nodes in Binary Tree | Helper function to allocates a new node ; Helper function to check if node is leaf node ; A recursive method to sink a tree with odd root This method assumes that the subtrees are already sinked . This method is similar to Heapify of Heap - Sort ; If None or is a leaf , do nothing ; if left subtree exists and left child is even ; swap root 's data with left child   and fix left subtree  ; if right subtree exists and right child is even ; swap root 's data with right child   and fix right subtree  ; Function to sink all odd nodes to the bottom of binary tree . It does a postorder traversal and calls sink ( ) if any odd node is found ; If None or is a leaf , do nothing ; Process left and right subtrees before this node ; If root is odd , sink it ; Helper function to do Level Order Traversal of Binary Tree level by level . This function is used here only for showing modified tree . ; Do Level order traversal ; Print one level at a time ; Line separator for levels ; Constructed binary tree is 1 / \ 5 8 / \ / \ 2 4 9 10
class newnode : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . data = key NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def isLeaf ( root ) : NEW_LINE INDENT return ( root . left == None and root . right == None ) NEW_LINE DEDENT def sink ( root ) : NEW_LINE INDENT if ( root == None or isLeaf ( root ) ) : NEW_LINE INDENT return NEW_LINE DEDENT if ( root . left and not ( root . left . data & 1 ) ) : NEW_LINE INDENT root . data , root . left . data = root . left . data , root . data NEW_LINE sink ( root . left ) NEW_LINE DEDENT elif ( root . right and not ( root . right . data & 1 ) ) : NEW_LINE INDENT root . data , root . right . data = root . right . data , root . data NEW_LINE sink ( root . right ) NEW_LINE DEDENT DEDENT def sinkOddNodes ( root ) : NEW_LINE INDENT if ( root == None or isLeaf ( root ) ) : NEW_LINE INDENT return NEW_LINE DEDENT sinkOddNodes ( root . left ) NEW_LINE sinkOddNodes ( root . right ) NEW_LINE if ( root . data & 1 ) : NEW_LINE INDENT sink ( root ) NEW_LINE DEDENT DEDENT def printLevelOrder ( root ) : NEW_LINE INDENT q = [ ] NEW_LINE q . append ( root ) NEW_LINE while ( len ( q ) ) : NEW_LINE INDENT nodeCount = len ( q ) NEW_LINE while ( nodeCount ) : NEW_LINE INDENT node = q [ 0 ] NEW_LINE print ( node . data , end = " ▁ " ) NEW_LINE q . pop ( 0 ) NEW_LINE if ( node . left != None ) : NEW_LINE INDENT q . append ( node . left ) NEW_LINE DEDENT if ( node . right != None ) : NEW_LINE INDENT q . append ( node . right ) NEW_LINE DEDENT nodeCount -= 1 NEW_LINE DEDENT print ( ) NEW_LINE DEDENT DEDENT root = newnode ( 1 ) NEW_LINE root . left = newnode ( 5 ) NEW_LINE root . right = newnode ( 8 ) NEW_LINE root . left . left = newnode ( 2 ) NEW_LINE root . left . right = newnode ( 4 ) NEW_LINE root . right . left = newnode ( 9 ) NEW_LINE root . right . right = newnode ( 10 ) NEW_LINE sinkOddNodes ( root ) NEW_LINE print ( " Level ▁ order ▁ traversal ▁ of ▁ modified ▁ tree " ) NEW_LINE printLevelOrder ( root ) NEW_LINE