Convert a given Binary Tree to Doubly Linked List | Set 3 | A binary tree node has data , left pointers and right pointers ; head -- > Pointer to head node of created doubly linked list ; A simple recursive function to convert a given Binary tree to Doubly Linked List root -- > Root of Binary Tree ; Base case ; Initialize previously visited node as NULL . This is static so that the same value is accessible in all recursive calls ; Recursively convert left subtree ; Now convert this node ; Finally convert right subtree ; Function to print nodes in a given doubly linked list ; Driver program to test above functions ; Let us create the tree as shown in above diagram ; convert to DLL ; Print the converted List
class Node { int data ; Node left , right ; public Node ( int data ) { this . data = data ; left = right = null ; } } class BinaryTree { Node root ; Node head ; void BinaryTree2DoubleLinkedList ( Node root ) { if ( root == null ) return ; static Node prev = null ; BinaryTree2DoubleLinkedList ( root . left ) ; if ( prev == null ) head = root ; else { root . left = prev ; prev . right = root ; } prev = root ; BinaryTree2DoubleLinkedList ( root . right ) ; } 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 ) ; tree . BinaryTree2DoubleLinkedList ( tree . root ) ; tree . printList ( tree . head ) ; } }