Convert left | Python3 program to convert left - right to down - right representation of binary tree Helper function that allocates a new node with the given data and None left and right poers . ; Construct to create a new node ; An Iterative level order traversal based function to convert left - right to down - right representation . ; Base Case ; Recursively convert left an right subtrees ; If left child is None , make right child as left as it is the first child . ; If left child is NOT None , then make right child as right of left child ; Set root 's right as None ; A utility function to traverse a tree stored in down - right form . ; Driver Code ; 1 / \ 2 3 / \ 4 5 / / \ 6 7 8
class newNode : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . key = key NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def convert ( root ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return NEW_LINE DEDENT convert ( root . left ) NEW_LINE convert ( root . right ) NEW_LINE if ( root . left == None ) : NEW_LINE INDENT root . left = root . right NEW_LINE DEDENT else : NEW_LINE INDENT root . left . right = root . right NEW_LINE DEDENT root . right = None NEW_LINE DEDENT def downRightTraversal ( root ) : NEW_LINE INDENT if ( root != None ) : NEW_LINE INDENT print ( root . key , end = " ▁ " ) NEW_LINE downRightTraversal ( root . right ) NEW_LINE downRightTraversal ( root . left ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 1 ) NEW_LINE root . left = newNode ( 2 ) NEW_LINE root . right = newNode ( 3 ) NEW_LINE root . right . left = newNode ( 4 ) NEW_LINE root . right . right = newNode ( 5 ) NEW_LINE root . right . left . left = newNode ( 6 ) NEW_LINE root . right . right . left = newNode ( 7 ) NEW_LINE root . right . right . right = newNode ( 8 ) NEW_LINE convert ( root ) NEW_LINE print ( " Traversal ▁ of ▁ the ▁ tree ▁ converted " , " to ▁ down - right ▁ form " ) NEW_LINE downRightTraversal ( root ) NEW_LINE DEDENT