Convert a given Binary Tree to Doubly Linked List | Set 2 | Java program to convert BTT to DLL using simple inorder traversal ; 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 ; Driver code ; Let us create the tree shown in above diagram
public class BinaryTreeToDLL { static class node { int data ; node left , right ; public node ( int data ) { this . data = data ; } } static node prev ; static void inorder ( node root ) { if ( root == null ) return ; inorder ( root . left ) ; System . out . print ( root . data + " ▁ " ) ; inorder ( root . right ) ; } static void fixPrevptr ( node root ) { if ( root == null ) return ; fixPrevptr ( root . left ) ; root . left = prev ; prev = root ; fixPrevptr ( root . right ) ; } static node fixNextptr ( node root ) { while ( root . right != null ) root = root . right ; while ( root != null && root . left != null ) { node left = root . left ; left . right = root ; root = root . left ; } return root ; } static node BTTtoDLL ( node root ) { prev = null ; fixPrevptr ( root ) ; return fixNextptr ( root ) ; } static void printlist ( node root ) { while ( root != null ) { System . out . print ( root . data + " ▁ " ) ; root = root . right ; } } public static void main ( String [ ] args ) { node 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 ) ; System . out . println ( " Inorder ▁ Tree ▁ Traversal " ) ; inorder ( root ) ; node head = BTTtoDLL ( root ) ; System . out . println ( " DLL Traversal "); printlist ( head ) ; } }