Write a function which will accept a Binary Search Tree and convert it to a sorted Doubly linked Lis

struct Node{
int data;
struct Node *left;
struct Node *right;

}
I have named the two pointers as left and right, but they can be named pre/next or anything.

If we are codding in C++, then we can take the advantage of Object Oriented Programming and define the Node as a Class, The benefit we will get is that we can also define the constructor and/or other operations, like below, I have also defined a constructor which initializes the pointers to NULL in the member initialization list of constructor


#include
#include
using namespace std;


struct node
{
int data;
struct node* left;
struct node* right;

};

//typedef struct node Node;

/** Helper function to create a sample tree. Used to debug the program.
* It create the below tree and returns a pointer to the root.
*
* 4
* / \
* 2 5
* / \
* 1 3
*/
/** Prints the in Inorder Tracersal of the tree pointed to by r.
*/
void printInorder(struct node* r)
{
if(!r){ return; }

printInorder(r->left);
cout<<" "<data;
printInorder(r->right);
}

/** Prints the Doubly link list whose head is at h linearly.
*/
void printDoublyList(struct node* h)
{

while(h)
{
cout<<" "<data;
h = h->right;
}
cout<data;

}

struct node* append(struct node *a,struct node *b)
{
if(a==NULL)return b;
if(b==NULL)return a;

//struct node* result=a;

a->right=b;
b->left=a;

return a;

}

/** Recursively convert a Binary Tree to a Doubly Linked List
*/
struct node* treeToList(struct node* r)
{

// Terminating Condition of Recursion
if (r == NULL){ return NULL; }

// Convert to list the left and right subtrees recursively
struct node *prev = treeToList(r->left);
struct node *next = treeToList(r->right);

// Making the root Node a separate list
r->left = NULL;
r->right = NULL;

/* Append everything together in sorted order */
prev = append(prev, r);
prev = append(prev, next);

return(prev);
}

struct node* Node(int data)
{
struct node *temp=(struct node *)(malloc(sizeof(struct node)));
temp->data=data;
temp->left=NULL;
temp->right=NULL;

return temp;
}

int main()
{
struct node *r = NULL;
r = Node(4);
r->left =Node(2);
r->left->left = Node(1);
r->left->right = Node(3);
r->right = Node(5);
r->right->left = Node(6);
r->right->right = Node(7);



cout<<"In order Tracersal :";
printInorder(r);

r = treeToList(r);
cout<<"\nList :";
printDoublyList(r);

getchar();
return 0;
}
Run Here https://ideone.com/SVhKd
Run here https://ideone.com/clone/vMBw1