Convert a Binary Tree to Threaded binary tree | Set 2 ( Efficient ) | Converts tree with given root to threaded binary tree . This function returns rightmost child of root . ; Base cases : Tree is empty or has single node ; Find predecessor if it exists ; Find predecessor of root ( Rightmost child in left subtree ) ; Link a thread from predecessor to root . ; If current node is rightmost child ; Recur for right subtree . ; A utility function to find leftmost node in a binary tree rooted with ' root ' . This function is used in inOrder ( ) ; Function to do inorder traversal of a threaded binary tree ; Find the leftmost node in Binary Tree ; If this Node is a thread Node , then go to inorder successor ; Else go to the leftmost child in right subtree ; A utility function to create a new node ; Driver Code ; 1 / \ 2 3 / \ / \ 4 5 6 7
def createThreaded ( root ) : NEW_LINE INDENT if root == None : NEW_LINE INDENT return None NEW_LINE DEDENT if root . left == None and root . right == None : NEW_LINE INDENT return root NEW_LINE DEDENT if root . left != None : NEW_LINE INDENT l = createThreaded ( root . left ) NEW_LINE l . right = root NEW_LINE l . isThreaded = True NEW_LINE DEDENT if root . right == None : NEW_LINE INDENT return root NEW_LINE DEDENT return createThreaded ( root . right ) NEW_LINE DEDENT def leftMost ( root ) : NEW_LINE INDENT while root != None and root . left != None : NEW_LINE INDENT root = root . left NEW_LINE DEDENT return root NEW_LINE DEDENT def inOrder ( root ) : NEW_LINE INDENT if root == None : NEW_LINE INDENT return NEW_LINE DEDENT cur = leftMost ( root ) NEW_LINE while cur != None : NEW_LINE INDENT print ( cur . key , end = " ▁ " ) NEW_LINE if cur . isThreaded : NEW_LINE INDENT cur = cur . right NEW_LINE DEDENT else : NEW_LINE INDENT cur = leftMost ( cur . right ) NEW_LINE DEDENT DEDENT DEDENT class newNode : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . left = self . right = None NEW_LINE self . key = key NEW_LINE self . isThreaded = None 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 . left . left = newNode ( 4 ) NEW_LINE root . left . right = newNode ( 5 ) NEW_LINE root . right . left = newNode ( 6 ) NEW_LINE root . right . right = newNode ( 7 ) NEW_LINE createThreaded ( root ) NEW_LINE print ( " Inorder ▁ traversal ▁ of ▁ created " , " threaded ▁ tree ▁ is " ) NEW_LINE inOrder ( root ) NEW_LINE DEDENT