# Binary Tree to Doubly linked list  ## 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;

}

{
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;
}

{
if (root == NULL)
{
return;
}
//Right subtree
//Insert node
{
}
//Left subtree
}

// 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);