Program to convert Binary tree to Doubly linked list

The order of Doubly linked list will be same as the inorder of the Binary tree.So the first node of DLL will be the leftmost node of Binary tree.Let us assume that the given Binary tree is

Now the order of the Doubly linked list will be 31 23 36 15 42 34.

Algorithm :

The algorithm of this program is pretty simple.We will first find the inorder of the left subtree and convert into DLL.Then we again find the inorder of right subtree and convert into DLL.Then finally we join both DLL to the root node of the tree.

1) Recursively convert left subtree to DLL
2) Now find the inorder predecessor of root node. Inorder predecessor is the right most node of left subtree.Let take it as IP node.
3) Now nake root node as next of IP node and IP node as previous of root node.
4) Recursively convert Right subtree to DLL
5) Now find the inorder successor of root node.The inorder successor of root node is the left node of right subtree.Let take it as IS node.
6) Now make IS node next of root node and root node as previous of IS node.
7) Find the left most node and return it ie the head of DLL.

Program :

#include<stdio.h>
#include<conio.h>
struct node
{
int data;
node *left;
node *right;
}

node* newNode(int data)
{
    node* newnode = new node;
    newnode->data = data;
    newnode->left = newnode->right = NULL;
    return (newnode);
}

node* bintree2DLL(node* root)
{
   
    if (root == NULL)
        return root;

    if (root->left != NULL)
    {
       
        node* left = bintree2DLL(root->left);           // Convert the left subtree

       
        while(left->right!=NULL)
           left=left->right                                         // Find inorder predecessor
                                                       

        left->right = root;                                      // Make root as next of the predecessor

       
        root->left = left;                                       // Make predecessor as previous of root
    }

   
    if (root->right!=NULL)
    {
       
        node* right = bintree2DLL(root->right);     // Convert the right subtree

       
        while(right->left!=NULL)                           // Find inorder successor
              right = right->left
       
        right->left = root;                                       // Make root as previous of successor

       
        root->right = right;                                    // Make successor as next of root
    }

    return root;
}


int main()
{

 node *root        = newNode(15);
    root->left        = newNode(23);
    root->right       = newNode(34);
    root->left->left  = newNode(31);
    root->left->right = newNode(36);
    root->right->left = newNode(42);
  node  *r= bintree2DLL(root);
 while(r->left!=NULL)
{
r=r->left;
}
while(r!=NULL)
{
printf("%d",r->data)
r=r->right;
}
    getch();

}