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 point 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 point 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 ; Driver program to test above functions ; Let us create the tree shown in above diagram ; Convert to DLL ; Print the converted list
class Node { int data ; Node left , right ; Node ( int item ) { data = item ; left = right = null ; } } class BinaryTree { Node root ; Node bintree2listUtil ( Node node ) { if ( node == null ) return node ; if ( node . left != null ) { Node left = bintree2listUtil ( node . left ) ; for ( ; left . right != null ; left = left . right ) ; left . right = node ; node . left = left ; } if ( node . right != null ) { Node right = bintree2listUtil ( node . right ) ; for ( ; right . left != null ; right = right . left ) ; right . left = node ; node . right = right ; } return node ; } Node bintree2list ( Node node ) { if ( node == null ) return node ; node = bintree2listUtil ( node ) ; while ( node . left != null ) node = node . left ; return node ; } void printList ( Node node ) { while ( node != null ) { System . out . print ( node . data + " ▁ " ) ; node = node . right ; } } public static void main ( String [ ] args ) { BinaryTree tree = new BinaryTree ( ) ; tree . root = new Node ( 10 ) ; tree . root . left = new Node ( 12 ) ; tree . root . right = new Node ( 15 ) ; tree . root . left . left = new Node ( 25 ) ; tree . root . left . right = new Node ( 30 ) ; tree . root . right . left = new Node ( 36 ) ; Node head = tree . bintree2list ( tree . root ) ; tree . printList ( head ) ; } }