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 code ; Let us create the tree shown in above diagram
#include <bits/stdc++.h> NEW_LINE using namespace std ; class node { public : int data ; node * left , * right ; } ; node * newNode ( int data ) { node * Node = new node ( ) ; Node -> data = data ; Node -> left = Node -> right = NULL ; return ( Node ) ; } void inorder ( node * root ) { if ( root != NULL ) { inorder ( root -> left ) ; cout << " TABSYMBOL " << root -> data ; inorder ( root -> right ) ; } } void fixPrevPtr ( node * root ) { static node * pre = NULL ; if ( root != NULL ) { fixPrevPtr ( root -> left ) ; root -> left = pre ; pre = root ; fixPrevPtr ( root -> right ) ; } } node * fixNextPtr ( node * root ) { 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 ) ; } node * BTToDLL ( node * root ) { fixPrevPtr ( root ) ; return fixNextPtr ( root ) ; } void printList ( node * root ) { while ( root != NULL ) { cout << " TABSYMBOL " << root -> data ; root = root -> right ; } } int main ( void ) { 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 ) ; cout << " Inorder Tree Traversal " ; inorder ( root ) ; node * head = BTToDLL ( root ) ; cout << " DLL Traversal " printList ( head ) ; return 0 ; }