Convert a given Binary Tree to Doubly Linked List | Set 2 | A 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 next 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 ; Traverses the DLL from left tor right ; Let us create the tree shown in above diagram
class node { constructor ( val ) { this . data = val ; this . left = null ; this . right = null ; } } var prev ; function inorder ( root ) { if ( root == null ) return ; inorder ( root . left ) ; document . write ( root . data + " " ) ; inorder ( root . right ) ; } function fixPrevptr ( root ) { if ( root == null ) return ; fixPrevptr ( root . left ) ; root . left = prev ; prev = root ; fixPrevptr ( root . right ) ; } function fixNextptr ( root ) { while ( root . right != null ) root = root . right ; while ( root != null && root . left != null ) { var left = root . left ; left . right = root ; root = root . left ; } return root ; } function BTTtoDLL ( root ) { prev = null ; fixPrevptr ( root ) ; return fixNextptr ( root ) ; } function printlist ( root ) { while ( root != null ) { document . write ( root . data + " " ) ; root = root . right ; } } var root = new node ( 10 ) ; root . left = new node ( 12 ) ; root . right = new node ( 15 ) ; root . left . left = new node ( 25 ) ; root . left . right = new node ( 30 ) ; root . right . left = new node ( 36 ) ; document . write ( " " ) ; inorder ( root ) ; var head = BTTtoDLL ( root ) ; document . write ( " " ) ; printlist ( head ) ;