Convert a given Binary Tree to Doubly Linked List | Set 1 | A binary tree node has data , and left and right pointers ; * This is the core function to convert Tree to list . This function follows * steps 1 and 2 of the above algorithm ; Base case ; Convert the left subtree and link to root ; Convert the left subtree ; Find inorder predecessor . After this loop , left will povar to the inorder predecessor ; Make root as next of the predecessor ; Make predecssor as previous of root ; Convert the right subtree and link to root ; Convert the right subtree ; Find inorder successor . After this loop , right will povar to the inorder successor ; 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 DLL using bintree2listUtil ( ) ; bintree2listUtil ( ) returns root node of the converted DLL . We need pointer to the leftmost node which is head of the constructed DLL , so move to the leftmost node ; Function to print nodes in a given doubly linked list ; Let us create the tree shown in above diagram ; Convert to DLL ; Prvar the converted list
class Node { constructor ( val ) { this . data = val ; this . left = null ; this . right = null ; } } var root ; function bintree2listUtil ( node ) { if ( node == null ) return node ; if ( node . left != null ) { var left = bintree2listUtil ( node . left ) ; for ( ; left . right != null ; left = left . right ) left . right = node ; node . left = left ; } if ( node . right != null ) { var right = bintree2listUtil ( node . right ) ; for ( ; right . left != null ; right = right . left ) right . left = node ; node . right = right ; } return node ; } function bintree2list ( node ) { if ( node == null ) return node ; node = bintree2listUtil ( node ) ; while ( node . left != null ) node = node . left ; return node ; } function printList ( node ) { while ( node != null ) { document . write ( node . data + " " ) ; node = node . right ; } } 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 ) ; var head = bintree2list ( root ) ; printList ( head ) ;