## Convert the given Binary Tree into a Doubly linked list in-place. The order of nodes should be same as in-order of the given binary tree. The left and right pointers of the tree node are to be used as previous and next.

### Example

**Time complexity : O(n)**

## Algorithm

Traverse the tree in reverse in-order traversal. We are doing reverse in-order because, we insert nodes at the beginning, we need to process leaves in reverse order.

**a.** If root is null, return(Null DLL)

**b.** Recursively covert right subtree and insert node into DLL

**c.** Change left pointer of previous head to root. Change head of Doubly linked list equal to root. (we are inserting nodes in the beginning).

**d.** Recursively covert right subtree.

## C++ Program

```
#include <bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node *right;
Node *left;
};
void insertAtBeginning(struct Node **head, int X)
{
struct Node * curr = new Node;
curr->data = X;
curr->left = NULL;
curr->right = *head;
if(*head != NULL)
(*head)->left = curr;
*head = curr;
}
void display(struct Node**head)
{
struct Node*temp=*head;
while(temp!=NULL)
{
if(temp->right!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;
temp=temp->right; //move to right node
}
//O(number of nodes)
cout<<endl;
}
void Convert(Node* root, Node** head_ref)
{
if (root == NULL)
{
return;
}
//Right subtree
Convert(root->right, head_ref);
//Insert node
root->right = *head_ref;
if (*head_ref != NULL)
{
(*head_ref)->left = root;
}
*head_ref = root;
//Left subtree
Convert(root->left, head_ref);
}
// Utility function for allocating node for Binary
// Tree.
Node* newNode(int data)
{
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
//Main function
int main()
{
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->right = newNode(6);
root->right->right->right = newNode(7);
root->left->left->left = newNode(8);
root->left->left->right = newNode(9);
Node* head = NULL;
Convert(root, &head);
display(&head);
return 0;
}
```

Try It

**Next >**
**< Prev**