Convert a Binary Tree to a Doubly Linked List

The structure of Node of a Binary Tree and Doubly linked list are same.

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

struct Node
{
   int data;
   Node* previous;
   Node* next;
}

If we treat left pointer as previous and right pointer as next, we can use the Node of a Binary Tree to represent node of a Doubly linked list or vice-versa.

Given a binary tree, modify the pointers in each node of the tree so that they represent a Doubly linked. Order of the nodes in DLL should be same as that in the in-order traversal.

If the Input Binary tree is as below

then the function should modify pointers in the nodes, as shown below and return the head pointer.

The solution to this problem, like many others in Binary Trees uses recursion. Let us say, the signature of the function is:

Node* convertToDLL(Node *r, Node** tail)

This function receives pointer to root of the tree. Convert it into a DLL and return the head of the list. It also set the address of last node in tail pointer.
We call this function recursively for left and right subree of the Binary Tree and get the following 4 pointers.

1. Head of DLL of left subtree
2. Tail of DLL of left subtree
3. Head of DLL of right subtree
4. Tail of DLL of right subtree

Once we have this, we just need to combine the left and right DLL by inserting root node between them:

The recursion terminates when we are at leaf node of root is NULL. Below is the complete code for this solution:

Code

struct Node
{
   int data;
   Node* left;
   Node* right;
   // CONSTRUCTOR
   Node():data(0), left(NULL), right(NULL){}
   Node(int v): data(v), left(NULL), right(NULL){}
};
// Covert the Tree with root at r to DLL.
// Return the head of DLL and set tail of DLL to dllTail
Node* convertToDLL(Node *r, Node** tail)
{
   // 0 or 1 nodes.
   if(r == NULL || (r->left == NULL && r->right == NULL))
   {
      *tail = r;
      return r;
   }
   Node* leftHead; // Head of DLL - Left subtree.
   Node* leftTail; // Tail of DLL - Left subtree.
   Node* rightHead; // Head of DLL - Right subtree.
   Node* rigthTail; // Tail of DLL - Right subtree.
   leftHead = convertToDLL(r->left, &leftTail);
   rightHead = convertToDLL(r->right, &rigthTail);
   Node* head = r; // Head of this tree.
   r->left = NULL;
   if(leftHead != NULL)
   {
      head = leftHead;
      leftTail->right = r;
      r->left = leftTail;
   }
   if(rightHead != NULL)
   {
      r->right = rightHead;
      rightHead->left = r;
      *tail = rigthTail;
   }
   else
   {
      *tail = r;
      r->right = NULL;
   }
   return head;
}
//Print the entire DLL
void printList(Node *head)
{
   while (head!=NULL)
   {
      cout << head->data << " ";
      head = head->right;
   }
}
void inOrder(Node* r)
{
   if(r)
   {
      inOrder(r->left);
      cout<<r->data<<" ";
      inOrder(r->right);
   }
}
int main()
{
   // CONSTRUCTING THE BINARY TREE
   Node *root      = new Node(10);
   root->left      = new Node(5);
   root->right      = new Node(15);
   root->left->left  = new Node(2);
   root->left->right = new Node(8);
   root->right->right = new Node(19);
   root->left->right->left = new Node(6);
   Node *head = convertToDLL(root, &head);
   // Print the converted list
   printList(head);
   return 0;
}