text: Convert a given Binary Tree to Doubly Linked List | Set 2 | A simple inorder traversal based program to convert a Binary Tree to DLL ; A tree node ; A utility function to create a new 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 program to test above functions ; Let us create the tree shown in above diagram
code: #include <stdio.h> NEW_LINE #include <stdlib.h> NEW_LINE struct node { int data ; struct node * left , * right ; } ; struct node * newNode ( int data ) { struct node * node = ( struct node * ) malloc ( sizeof ( struct node ) ) ; node -> data = data ; node -> left = node -> right = NULL ; return ( node ) ; } void inorder ( struct node * root ) { if ( root != NULL ) { inorder ( root -> left ) ; printf ( " TABSYMBOL % d " , root -> data ) ; inorder ( root -> right ) ; } } void fixPrevPtr ( struct node * root ) { static struct node * pre = NULL ; if ( root != NULL ) { fixPrevPtr ( root -> left ) ; root -> left = pre ; pre = root ; fixPrevPtr ( root -> right ) ; } } struct node * fixNextPtr ( struct node * root ) { struct node * prev = NULL ; while ( root && root -> right != NULL ) root = root -> right ; while ( root && root -> left != NULL ) { prev = root ; root = root -> left ; root -> right = prev ; } return ( root ) ; } struct node * BTToDLL ( struct node * root ) { fixPrevPtr ( root ) ; return fixNextPtr ( root ) ; } void printList ( struct node * root ) { while ( root != NULL ) { printf ( " TABSYMBOL % d " , root -> data ) ; root = root -> right ; } } int main ( void ) { struct node * root = newNode ( 10 ) ; root -> left = newNode ( 12 ) ; root -> right = newNode ( 15 ) ; root -> left -> left = newNode ( 25 ) ; root -> left -> right = newNode ( 30 ) ; root -> right -> left = newNode ( 36 ) ; printf ( " Inorder Tree Traversal " inorder ( root ) ; struct node * head = BTToDLL ( root ) ; printf ( " DLL Traversal " printList ( head ) ; return 0 ; }