# Convert a given Binary Tree to Doubly Linked List

__Introduction__

__Introduction__

A __linked list__ is a linear data structure where elements are not stored contiguously but randomly. They are instrumental in implementing stacks and queues, graphs, performing arithmetic operations on large integers, and representing sparse matrices. On the other hand, a binary tree is a tree in which each node has at the most * 2* children.

These two are significant topics and are often a part of various technical interviews.

This blog will discuss one such problem involving a linked list and binary tree, Convert a given binary tree to a doubly-linked list.

__Example__

Consider the following binary tree:

The doubly-linked list for this binary tree is given by:

Let us see the different techniques that can be used to solve this problem:

**Using Inorder Traversal**

__Algorithm__

__Algorithm__

- Perform inorder traversal on the given binary tree.
- For every node that is encountered, insert it at the beginning of the doubly linked list.
- The linked list is then reversed to maintain the same order of the nodes as in the inorder traversal.

__Implementation__

__Implementation__

__Program__

__Program__```
// C++ program to convert a given binary tree to a doubly-linked list using inorder traversal.
#include <iostream>
using namespace std;
// Creating a node to store the binary tree.
struct Node
{
int data;
Node *left, *right;
Node(int data)
{
this->data = data;
this->left = this->right = NULL;
}
};
// Function to print the doubly linked list.
void printDLL(Node *head)
{
Node *curr = head;
while (curr != NULL)
{
cout << curr->data << " ";
curr = curr->right;
}
}
// Helper function to convert a given binary tree to a doubly linked list using normal inorder traversal.
void convert(Node *root, Node *&head)
{
// If the tree is empty.
if (root == NULL)
{
return;
}
// Converting the left tree recursively.
convert(root->left, head);
root->left = NULL;
// Storing the right child.
Node *right = root->right;
// Inserting the current node at the beginning of a doubly linked list.
root->right = head;
if (head != NULL)
{
head->left = root;
}
head = root;
// Converting the right subtree recursively.
convert(right, head);
}
// To reverse the doubly linked list.
void reverse(Node *&head)
{
Node *prev = NULL;
Node *current = head;
while (current)
{
swap(current->left, current->right);
prev = current;
current = current->left;
}
if (prev != NULL)
{
head = prev;
}
}
// Function to convert a given binary tree to a doubly linked list.
void convert(Node *root)
{
// Assigning 'NULL' value to the 'HEAD' node.
Node *head = NULL;
// Convert this binary tree into a doubly linked list.
convert(root, head);
// Reversing the linked list.
reverse(head);
// Print the list.
printDLL(head);
}
int main()
{
// Inserting values in the binary tree.
Node *root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
// Calling the function and printing the doubly linked list.
cout << "The doubly linked list is given by: ";
convert(root);
return 0;
}
```

__Output__

__Output__```
The doubly linked list is given by:
4 2 5 1 6 3 7
```

**Time Complexity**

**Time Complexity**

The time complexity is * O(N)*, where

*is the total number of nodes in the binary tree.*

**N**Since we are traversing the entire binary tree having * N* nodes, only once, the time complexity is given by

**O(N).****Space Complexity**

**Space Complexity**

The space complexity is * O(N), *where

*is the height of the binary tree.*

**N**Since the recursive function is called, again and again, it will occupy a stack of size equal to the height of the tree, in the memory. For a skew tree, the height will be * N*, leading space complexity to

*.*

**O(N)****Using Reverse Inorder Traversal**

This problem can also be solved using a single step as well. The algorithm has been explained below:

__Algorithm__

__Algorithm__

- We will use reverse inorder traversal instead of using normal inorder traversal.
- We will process the right subtree first and then the left subtree.
- For every node that is encountered, insert it at the beginning of the doubly linked list.
- The nodes will follow the same order as in the inorder traversal.

__Implementation__

__Implementation__

__Program__

__Program__```
// C++ program to convert a given binary tree to a doubly linked list using reverse inorder traversal.
#include <iostream>
using namespace std;
// Creating a node to store the binary tree.
struct Node
{
int data;
Node *left, *right;
Node(int data)
{
this->data = data;
this->left = this->right = NULL;
}
};
// Function to print the doubly linked list.
void printDLL(Node *&head)
{
Node *curr = head;
while (curr != NULL)
{
cout << curr->data << " ";
curr = curr->right;
}
}
// Helper function to convert a given binary tree to a doubly linked list using reverse inorder traversal.
void convert(Node *root, Node *&head)
{
// If the tree is empty.
if (root == NULL)
{
return;
}
// Converting the right tree recursively.
convert(root->right, head);
// Inserting the current node at the beginning of a doubly linked list.
root->right = head;
if (head != NULL)
{
head->left = root;
}
head = root;
// Converting the left subtree recursively.
convert(root->left, head);
}
// Function to convert a given binary tree to a doubly linked list.
void convert(Node *root)
{
// Assigning ‘NULL’ value to the ‘HEAD’ node.
Node *head = NULL;
// Convert this binary tree into a doubly linked list.
convert(root, head);
// Print the list.
printDLL(head);
}
int main()
{
// Inserting values in the binary tree.
Node *root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
// Calling the function and printing the doubly linked list.
cout << "The doubly linked list is given by: ";
convert(root);
return 0;
}
```

__Output__

__Output__```
The doubly linked list is given by:
4 2 5 1 6 3 7
```

**Time Complexity**

**Time Complexity**

The time complexity is * O(N)*, where

*is the total number of nodes in the binary tree.*

**N**Since we are traversing the entire binary tree having * N* nodes, only once, the time complexity is given by

**O(N).****Space Complexity**

**Space Complexity**

The space complexity is * O(N), *where

*is the height of the binary tree.*

**N**Since the recursive function is called, again and again, it will occupy a stack of size equal to the height of the tree, in the memory. For a skew tree, the height will be * N*, leading space complexity to

*.*

**O(N)****Keeping track of the previous node- Inorder Traversal**

This approach is the simplest of all the techniques that we have discussed above.

The algorithm has been explained below:

__Algorithm__

__Algorithm__

- Perform inorder traversal on the given binary tree.
- For every node that is encountered, insert it at the beginning of the doubly linked list.
- Keep track of the previously processed node, say
**PREV.** - For every node visited, set its left child to
and the previous node’s right child to the current node.**PREV**

__Implementation__

__Implementation__

__Program__

__Program__```
// C++ program to convert a given binary tree to a doubly linked list keeping track of the previous node in inorder traversal.
#include <iostream>
using namespace std;
// Creating a node to store the binary tree.
struct Node
{
int data;
Node *left, *right;
Node(int data)
{
this->data = data;
this->left = this->right = NULL;
}
};
// Function to print the doubly linked list.
void printDLL(Node *&head)
{
Node *curr = head;
while (curr != NULL)
{
cout << curr->data << " ";
curr = curr->right;
}
}
// Helper function to convert a given binary tree to a doubly linked list.
// root --> current node.
// head --> head of the doubly linked list .
// prev --> previously processed node.
void convert(Node *curr, Node *&head, Node *&prev)
{
// If the tree is empty.
if (curr == NULL)
{
return;
}
// Converting the left tree recursively.
convert(curr->left, head, prev);
// Changing the pointers accordingly.
if (prev != NULL)
{
// The current node's left child is equated with prev.
curr->left = prev;
// The right child of previous node is equated with 'curr'.
prev->right = curr;
}
// If prev is null, update the head of the doubly linked list.
else
{
head = curr;
}
// The previous pointer is updated to the current node after the current node is visited.
prev = curr;
// Converting the right subtree recursively.
convert(curr->right, head, prev);
}
// Function to convert a given binary tree to a doubly linked list.
void convert(Node *root)
{
// To keep track of the previously processed node.
Node *prev = NULL;
// Convert the above binary tree into a doubly linked list.
convert(root, root, prev);
// Root becomes the head of the doubly linked list.
// Print the list.
printDLL(root);
}
int main()
{
// Inserting values in the binary tree.
Node *root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
// Calling the function and printing the doubly linked list.
cout << "The doubly linked list is given by: ";
convert(root);
return 0;
}
```

__Output__

__Output__```
The doubly linked list is given by:
4 2 5 1 6 3 7
```

**Time Complexity**

**Time Complexity**

The time complexity is * O(N)*, where

*is the total number of nodes in the binary tree.*

**N**Since we are traversing the entire binary tree having * N* nodes, only once, the time complexity is given by

**O(N).****Space Complexity**

**Space Complexity**

The space complexity is * O(N), *where

*is the height of the binary tree.*

**N**Since the recursive function is called, again and again, it will occupy a stack of size equal to the height of the tree, in the memory. For a skew tree, the height will be * N*, leading space complexity to

*.*

**O(N)**__Key Takeaways__

__Key Takeaways__

So, this blog discussed how to convert a given binary tree to a doubly-linked list using * 3* different approaches. To learn more on topics like

__Linked List__*,*

__Graphs__*,*

*, head over right now to*

__Trees__

*to practice problems on topics like and crack your interviews like a Ninja!*

__CodeStudio__Practicing a bunch of questions is not enough in this competitive world. So go check out where you stand among your peers by taking our __mock tests__* *and see which areas need improvement.

In case of any comments or suggestions, feel free to post them in the comments section.