Convert a given Binary Tree to Doubly Linked List | Set 1 | A C ++ program for in - place conversion of Binary Tree to DLL ; 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 ; Helper function that allocates a new node with the given data and NULL left and right pointers . ; Function to print nodes in a given doubly linked list ; Driver code ; Let us create the tree shown in above diagram ; Convert to DLL ; Print the converted list
#include <bits/stdc++.h> NEW_LINE using namespace std ; class node { public : int data ; node * left ; node * right ; } ; node * bintree2listUtil ( node * root ) { if ( root == NULL ) return root ; if ( root -> left != NULL ) { node * left = bintree2listUtil ( root -> left ) ; for ( ; left -> right != NULL ; left = left -> right ) ; left -> right = root ; root -> left = left ; } if ( root -> right != NULL ) { node * right = bintree2listUtil ( root -> right ) ; for ( ; right -> left != NULL ; right = right -> left ) ; right -> left = root ; root -> right = right ; } return root ; } node * bintree2list ( node * root ) { if ( root == NULL ) return root ; root = bintree2listUtil ( root ) ; while ( root -> left != NULL ) root = root -> left ; return ( root ) ; } node * newNode ( int data ) { node * new_node = new node ( ) ; new_node -> data = data ; new_node -> left = new_node -> right = NULL ; return ( new_node ) ; } void printList ( node * node ) { while ( node != NULL ) { cout << node -> data << " ▁ " ; node = node -> right ; } } int main ( ) { 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 ) ; node * head = bintree2list ( root ) ; printList ( head ) ; return 0 ; }