Convert a given Binary Tree to Doubly Linked List | Set 2 | A Binary Tree node ; Standard Inorder traversal of tree ; Changes left pointers to work as previous pointers in converted DLL The function simply does inorder traversal of Binary Tree and updates left pointer using previously visited node ; Changes right pointers to work as nexr pointers in converted DLL ; Find the right most node in BT or last node in DLL ; Start from the rightmost node , traverse back using left pointers While traversing , change right pointer of nodes ; The leftmost node is head of linked list , return it ; The main function that converts BST to DLL and returns head of DLL ; Set the previous pointer ; Set the next pointer and return head of DLL ; Traversses the DLL from left to right ; Let us create the tree shown in above diagram
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def inorder ( root ) : NEW_LINE INDENT if root is not None : NEW_LINE INDENT inorder ( root . left ) NEW_LINE print " TABSYMBOL % d " % ( root . data ) , NEW_LINE inorder ( root . right ) NEW_LINE DEDENT DEDENT def fixPrevPtr ( root ) : NEW_LINE INDENT if root is not None : NEW_LINE INDENT fixPrevPtr ( root . left ) NEW_LINE root . left = fixPrevPtr . pre NEW_LINE fixPrevPtr . pre = root NEW_LINE fixPrevPtr ( root . right ) NEW_LINE DEDENT DEDENT def fixNextPtr ( root ) : NEW_LINE INDENT prev = None NEW_LINE while ( root and root . right != None ) : NEW_LINE INDENT root = root . right NEW_LINE DEDENT while ( root and root . left != None ) : NEW_LINE INDENT prev = root NEW_LINE root = root . left NEW_LINE root . right = prev NEW_LINE DEDENT return root NEW_LINE DEDENT def BTToDLL ( root ) : NEW_LINE INDENT fixPrevPtr ( root ) NEW_LINE return fixNextPtr ( root ) NEW_LINE DEDENT def printList ( root ) : NEW_LINE INDENT while ( root != None ) : NEW_LINE INDENT print " TABSYMBOL % d " % ( root . data ) , NEW_LINE root = root . right NEW_LINE DEDENT DEDENT 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 print   " NEW_LINE INDENT Inorder Tree Traversal NEW_LINE DEDENT " NEW_LINE inorder ( root ) NEW_LINE fixPrevPtr . pre = None NEW_LINE head = BTToDLL ( root ) NEW_LINE print   " NEW_LINE INDENT DLL Traversal NEW_LINE DEDENT " NEW_LINE printList ( head ) NEW_LINE