# Binary Tree to Doubly Linked List

**Introduction**

Binary Trees are a type of data structure where each data is stored as a node, and each node has two child nodes. The three primary traversal techniques are pre-order, in-order, and post-order.

Linked Lists are another type of data structure where data is stored in nodes, and each node is connected via links. A linked list can be singly linked or doubly-linked depending upon the number of links. The two pointers in a doubly-linked list are: next and previous.

In this article, we will learn to convert a given binary tree into a doubly-linked list by performing in-order traversal. To know more about the various tree traversals, click here __Tree Traversals__.

**Problem Statement**

Given a binary tree with **n **nodes, convert it into a doubly-linked list.

Note: Store the inorder traversal of the given binary tree to the doubly linked list.

**Example**

Sample Input

Expected Output

**Approach and Explanation**

The implementation of the given problem is done in Java.

The step-by-step explanation is as follows -

- Binary Tree and Linked List are abstract data structures. This means that we need to create/define them so that we can use them.

- We create a constructor named
**TLL**. It has three members-**data**(int),**left**(TLL), and**right**(TLL). The variable**data**contains the node’s value and**left**and**right**are the links that will connect the nodes.

- Once this is done, create a class that will do all our work and convert the binary tree into a linked list. Inside this class, have two global variables named
**root**and**head**of the constructor type (**TLL**in our case) to perform the in-place conversion.

- Create a function that will recursively convert a Binary Tree node into a node of the Doubly Linked List. Name this function as
**createDLL().**

- The variable
**root**is for our binary tree, and the variable**head**is for our doubly linked list.

- The base case of the recursion is that if the
**root**is null, we simply return and end the recursion. Else we recur for the right sub-tree first and set its value to the**head**of our linked list.

- We then check if the
**head**is null or not. If it is not null, then the left side of the**head**contains the**root**. After assigning the value of**root**in the**head,**we traverse the left sub-tree.

- In the given implementation, there are two print functions. One of them is for the linked list, and the other is for the binary tree.

- In the function
**printLL(**TLL head**),**we pass the**head**node of our linked list and print by traversing the whole list.

- In the function
**printBT(**TLL root**),**we pass the**root**of our binary tree, perform level order traversal and print the tree level-wise.

- Inside our main() function, we create our binary tree object and pass some values for our nodes and then call the following three functions:
*printBT():*To print the binary tree given as the input.*createDLL():*To create a doubly-linked list from the binary tree.*printLL():*To print the doubly-linked list.

**Recommended:** Try to solve the problem first on our __CodeStudio__ by clicking here __Convert A Given Binary Tree To Doubly Linked List__.

**Java implementation**

```
import java.util.*;
class TLL{
int data;
TLL left,right;
public TLL(int value){
data = value;
left = right = null;
}
}
public class BTreeDLL {
TLL root;
TLL head;
void createDLL(TLL root)
{
if (root == null)
return;
createDLL(root.right);
root.right = head;
if (head != null)
head.left = root;
head = root;
createDLL(root.left);
}
void printLL(TLL head)
{
while (head != null) {
System.out.print(head.data + " ");
head = head.right;
}
}
void printBT(TLL root){
if(root == null)
return;
Queue<TLL> q =new LinkedList<TLL>();
q.add(root);
while(true)
{
int nC = q.size();
if(nC == 0)
break;
while(nC > 0)
{
TLL node = q.peek();
System.out.print(node.data + " ");
q.remove();
if(node.left != null)
q.add(node.left);
if(node.right != null)
q.add(node.right);
nC--;
}
System.out.println();
}
}
public static void main(String[] args){
BTreeDLL tree = new BTreeDLL();
tree.root = new TLL(5);
tree.root.left = new TLL(7);
tree.root.right = new TLL(9);
tree.root.left.left = new TLL(11);
tree.root.left.right = new TLL(13);
tree.root.right.left = new TLL(17);
System.out.println("The Binary Tree is:");
tree.printBT(tree.root);
tree.createDLL(tree.root);
System.out.print("The Linked List Formed: ");
tree.printLL(tree.head);
}
}
```

OUTPUT

```
The Binary Tree is:
5
7 9
11 13 17
The Linked List Formed: 11 7 13 5 17 9
```

**Complexities**

**Time Complexity**

We traverse our binary tree of n nodes once in the given implementation to create our doubly linked list. Thus time complexity is:

**T(n) = O(n)**

where n is the number of nodes.

**Space Complexity**

In the given implementation, we use recursion to make our doubly linked list. Thus,

**Space Complexity = O(h)**

**O(h) **is the extra space for the recursion stack, where **h **is the height of the binary tree.

**Frequently Asked Questions**

**Are there other ways to convert a binary tree into a doubly-linked list?**

Yes, there are a few more ways to convert a binary tree into a doubly-linked list. One of them is to perform in-order traversal, keep track of the visited nodes of our linked list and insert each visited node at the tail of our linked list.

**Are these problems asked in coding interviews?**

Yes, such questions are asked in the coding interviews of various companies like__Adobe__,__Facebook__, and__Google__. You can practice various coding interview problems and read about many interview experiences on our__CodeStudio__.

**Key Takeaways**

In a nutshell, this article discussed the conversion of a binary tree to a doubly-linked list thoroughly. We saw the problem statement, an example, an approach to the problem, its Java implementation, and the time and space complexities. We concluded the article with a few FAQs.

Want to ace the coding rounds of big tech companies? Try our __Attempt Unlimited Online Mock Test Series__ to start your preparation.

Learn various topics from Web Technologies, Programming Fundamentals, Data Structures, and Algorithms from our __Library__.

Happy Coding!

Comments

## No comments yet

## Be the first to share what you think