Convert a given Binary Tree to Doubly Linked List | Set 3 | A C ++ program for in - place conversion of Binary Tree to DLL ; A binary tree node has data , and left and right pointers ; A simple recursive function to convert a given Binary tree to Doubly Linked List root -- > Root of Binary Tree head -- > Pointer to head node of created doubly linked list ; 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 ; 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 program to test above functions ; Let us create the tree shown in above diagram ; Convert to DLL ; Print the converted list
#include <iostream> NEW_LINE using namespace std ; struct node { int data ; node * left ; node * right ; } ; void BinaryTree2DoubleLinkedList ( node * root , node * * head ) { if ( root == NULL ) return ; static node * prev = NULL ; BinaryTree2DoubleLinkedList ( root -> left , head ) ; if ( prev == NULL ) * head = root ; else { root -> left = prev ; prev -> right = root ; } prev = root ; BinaryTree2DoubleLinkedList ( root -> right , head ) ; } 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 = NULL ; BinaryTree2DoubleLinkedList ( root , & head ) ; printList ( head ) ; return 0 ; }