# Binary Tree To Double Linked List

## Introduction

In this article we will discuss about a popular interview question, which is how would you convert a binary tree to a double linked list. Now, a binary tree is a hierachical graph data structure and that does makes binary search tree a part of the question, it just needs to be a binary tree. And a double linked list is a data structure where nodes that hold information are sequentially chained, each node holds a pointer to the next node in the chain.

## Algorithm

We will choose the most naive approach for solving the problem. We'll do an in order traversal of the binary tree which ends up visiting the nodes in the order: 25 12 30 100, which is the order we want our double linked list to have. We'll keep track of the current node that we're looking at, and the previous node that we've visited. At each step, we'll make the current root node's left pointer point to the previous node, and we'll make the previous node's right pointer point to the current root node. We'll also cover one specific case where our first node becomes the previous node, and we have a head pointer for our linked list point to that node. Here is the C++ algorithm,
1. #include <iostream>
2. using namespace std;
3.
4. struct Node {
5.     int Data;
6.     struct Node* Left;
7.     struct Node* Right;
8.
9.     Node(int data) {
10.         this->Data = data;
11.         this->Left = NULL;
12.         this->Right = NULL;
13.     }
14. };
16.     // for last nodes
18.         cout << endl;
19.         return;
20.     }
21.
22.     // print node
23.     cout << head->Data << " ";
24.
25.     // recursively print
27. }
28. void ParseBinaryTree(Node* root, Node*& previous, Node*& header) {
29.     if(root == NULL) {
30.         return;
31.     }
32.
33.     // for left nodes
35.
36.     if(previous == NULL) {
37.         // Set the header & previous node for the first node
39.         previous = root;
40.     }
41.     else{
42.         // root node's left pointer point to the previous node
43.         root->Left = previous;
44.
45.         // previous node's right pointer point to the root
46.         previous->Right = root;
47.
48.         // update the previous node
49.         previous = root;
50.     }
51.
52.     // for right nodes
54. }
55. int main() {
56.     // initailize a binary tree
57.     Node* root = new Node(100);
58.     root->Left = new Node(12);
59.     root->Left->Left = new Node(25);
60.     root->Left->Right = new Node(30);
61.
62.     // intialize null header & prvious node nodes