Convert Binary Tree to Double Linked List

Question: write an algorithm to convert a binary tree into a double linked list. For example, if the input is the binary tree below:

The output will be a double linked list like this:

Solution: there are two tasks in converting a binary tree to a linked list. First of all, we must traverse the tree and visit all the nodes. Second of all, we must break each node from the tree and add it into the linked list.

For traversing the tree, we'll use level / order traversal a.k.a breadth first search. If you are not familiar with that concept, here is the post for you :) Take your time to read it, I'll be right here when you come back!

To construct the linked list, each node will have its left pointer point to the node in front of it and its right pointer point to the node behind it in the linked list. For instance, if node 1 is in front of node 2 and node 3 is behind node 2 in the linked list, we'll set left pointer of node 2 to node 1 and right pointer of node 2 to node 3 (see picture above)

#include<iostream>
#include<queue>
using namespace std;

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

struct Node* bt2DoubleLinkedList(struct Node* root)
{
  if (root == NULL)
    return NULL;

  queue nodeQueue;

  struct Node* head = root; //reference to head of the linked list
  struct Node* listIT = NULL; //current node being processed
  struct Node* prevNode = NULL; //previous node processed

  //initialize the stack
  nodeQueue.push(root);

  //convert to double linked list
  while (!nodeQueue.empty())
  {
    //process next node in stack
    prevNode = listIT; 
    listIT = nodeQueue.front();
    
    nodeQueue.pop();

    //add left child to stack
    if (listIT->left != NULL)
      nodeQueue.push(listIT->left);

    //add right child to stack
    if (listIT->right != NULL)
      nodeQueue.push(listIT->right);

    //add current node to linked list
    if (prevNode != NULL)
      prevNode->right = listIT;
    listIT->left = prevNode;
  }
  
  //connect end node of list to null
  listIT->right = NULL;

  return head;
}

Explanation: the method accepts a pointer to the tree's root as argument and returns the pointer to the head node of the linked list:

1. If the root node is null, we return null because the tree is empty.
2. If the root is not null, we proceed by first creating a queue to store the the nodes. Why do we use queue? That is how we traverse the tree by level. Every time we reach a node, we store its children in the queue for later processing. Thus, the queue will always have something in it as long as there are still unvisited node in the tree.
3. Next, we create three pointers. head points to the head node of the linked list. listIT is our list iterator which used to build the list one node at a time. prevNode is the last node added into the list. We need to keep track of such node because we have to change the right pointer of that node to the node immediate after it, which is the node that listIT will point to.
4. We initialize the queue by adding the root into it. The reason is that we will use the condition of empty queue to end the while loop.
5. The while loop will run until no node left in queue to process. For each node in the queue, we do the following:
   
   prevNode = listIT gets reference to the last processed node because we are about to process a new node
   
   listIT = nodeQueue.front() gets reference to the top in the queue because we're going to add it into the list.
   
   nodeQueue.pop() removes the top node out of the queue.
   
   We then add the left and right child of the top node into the queue, so we can process them later. Notice that we only add the children if they are not null.
   
   Finally, we connect the top node to the linked list. First, we set the right pointer of the previous node (prevNode) to the top node. Then, we set the left pointer of the top node to the previous node. As the result, the top node becomes the end node of the linked list and the previous node completely breaks off the tree.
   
   
6. When the last node is added into the linked list and the while loop exits, we have a double linked list. The only thing left is to set the end node's right pointer (pointed to by listIT) to null because there is no more node to add into the list.

Whew! That was a long explanation. If you are still confused, you may want to read about breadth first traversal and do an example with pencil and paper. Also, please don't hesitate to ask questions in the comment section below!