Convert a given Binary Tree to Doubly Linked List | Set 1 | Binary tree Node class has data , left and right child ; This is a utility function to convert the binary tree to doubly linked list . Most of the core task is done by this function . ; Base case ; Convert left subtree and link to root ; Convert the left subtree ; Find inorder predecessor , After this loop , left will point to the inorder predecessor of root ; Make root as next of predecessor ; Make predecessor as previous of root ; Convert the right subtree and link to root ; Convert the right subtree ; Find inorder successor , After this loop , right will point to the inorder successor of root ; Make root as previous of successor ; Make successor as next of root ; The main function that first calls bintree2listUtil ( ) , then follows step 3 of the above algorithm ; Base case ; Convert to doubly linked list using BLLToDLLUtil ; We need pointer to left most node which is head of the constructed Doubly Linked list ; Function to print the given doubly linked list ; Driver Code ; Let us create the tree shown in above diagram ; Convert to DLL ; Print the converted list
class Node ( object ) : NEW_LINE INDENT def __init__ ( self , item ) : NEW_LINE INDENT self . data = item NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def BTToDLLUtil ( root ) : NEW_LINE INDENT if root is None : NEW_LINE INDENT return root NEW_LINE DEDENT if root . left : NEW_LINE INDENT left = BTToDLLUtil ( root . left ) NEW_LINE while left . right : NEW_LINE INDENT left = left . right NEW_LINE DEDENT left . right = root NEW_LINE root . left = left NEW_LINE DEDENT if root . right : NEW_LINE INDENT right = BTToDLLUtil ( root . right ) NEW_LINE while right . left : NEW_LINE INDENT right = right . left NEW_LINE DEDENT right . left = root NEW_LINE root . right = right NEW_LINE DEDENT return root NEW_LINE DEDENT def BTToDLL ( root ) : NEW_LINE INDENT if root is None : NEW_LINE INDENT return root NEW_LINE DEDENT root = BTToDLLUtil ( root ) NEW_LINE while root . left : NEW_LINE INDENT root = root . left NEW_LINE DEDENT return root NEW_LINE DEDENT def print_list ( head ) : NEW_LINE INDENT if head is None : NEW_LINE INDENT return NEW_LINE DEDENT while head : NEW_LINE INDENT print ( head . data , end = " ▁ " ) NEW_LINE head = head . right NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = Node ( 10 ) NEW_LINE root . left = Node ( 12 ) NEW_LINE root . right = Node ( 15 ) NEW_LINE root . left . left = Node ( 25 ) NEW_LINE root . left . right = Node ( 30 ) NEW_LINE root . right . left = Node ( 36 ) NEW_LINE head = BTToDLL ( root ) NEW_LINE print_list ( head ) NEW_LINE DEDENT