**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.

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:

- If the root node is null, we return null because the tree is empty.
- 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.
- 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.
- 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.
- 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.

- 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.