# Convert a given binary tree to doubly linked list in Python

In this tutorial, we will get to know the method to convert a given binary tree to a doubly-linked list in Python. Here, we will learn about binary trees, doubly-linked lists, and a method to convert a given binary tree to a doubly-linked list. Also, we will see a Python program for the same. So, if you are looking for a Python program for converting a binary tree to a doubly-linked list, you are in the right place.

The figure given below shows a binary tree with root node 6. Every node of a binary tree can have at most 2 children.

To represent a binary tree in Python, we can use the following data structures-

• Arrays

But, here we will use a linked list to represent a binary tree. So, we define the structure of a node using a Python class as follows-

```class Node:
def __init__(self,key):
self.leftchild = None
self.rightchild = None
self.value = key```

Here, the variables ‘leftchild’ and ‘rightchild’ point to the left-child and right-child nodes respectively. And the variable ‘value’ stores the data of a node. The node representation of a binary tree is shown below-

A doubly-linked list is a data structure that contains sequentially linked records i.e. nodes. It stores data or information sequentially and each individual data is stored in a node. The definition of a node using a Python class is as follows-

```class DLL_Node:
def __init__(self, next=None, prev=None, data=None):
self.next = next
self.prev = prev
self.data = data```

Here, the variables ‘next’ and ‘prev’ points to the next and previous nodes respectively. The variable ‘data’ stores the information of a node. The node representation of a doubly-linked list is shown below-

## Traversal of a binary tree

So, here we will learn about traversal techniques. There are three traversal techniques of a binary tree-

• Pre-order –> (Root, Left, Right)
• In-order –> (Left, Root, Right)
• Post-order –> (Left, Right, Root)

But in this tutorial, we will use the in-order traversal of the binary tree for conversion to a doubly-linked list. So, let’s find out the in-order traversal of the binary tree given below-

The figures below show the stepwise in-order traversal of the given binary tree-

So, the in-order traversal of this binary tree is shown in the figure below.

## Conversion of a binary tree to a doubly-linked list

Firstly, let us understand what we have to do. So, we need to create a doubly-linked list that represents the given binary tree. For example – The doubly-linked list of the above binary tree will be as follows-

Remember, the addresses are just for the sake of a better understanding of the concept. Although, the actual addresses are the hexadecimal memory addresses. In the above representation, we have used the in-order traversal of the given binary tree to obtain the doubly-linked list. But, we can perform the conversion by storing any one traversal of the binary tree. So, there are following ways for conversion-

• Using pre-order traversal for the conversion of a binary tree.
• By using in-order traversal for the conversion.
• Also, we can take the post-order traversal of a given binary tree.

But here, we will convert the given binary tree to a doubly-linked list by storing the in-order traversal of the given binary tree. So, to convert a binary tree to a doubly-linked list we will follow these steps.

• Firstly, create a binary tree with ‘n’ nodes.
• Declare a doubly-linked list node.
• Perform the in-order traversal of the binary tree.
• While performing the above operation, display the nodes of the binary tree.
• And append these nodes in the doubly-linked list simultaneously.
• Finally, the doubly-linked list will contain the in-order traversal of the binary tree.

## Converting a binary tree to a doubly-linked list using Python program

So now we will see a Python program that converts a given binary tree into a doubly-linked list.

```class Node:
def __init__(self,key):
self.leftchild = None
self.rightchild = None
self.value = key
class DLL_Node:
def __init__(self, next=None, prev=None, data=None):
self.next = next
self.prev = prev
self.data = data
class insert:
def __init__(self):
self.tail = None;
def append(self, new_data):
new_node = DLL_Node(data = new_data)
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail=new_node
def display(self):
print("\n\nTHE RESULTANT DLL IS -")
print("LIST IS EMPTY");
return;
while(current.next != None):
print("%d"%current.data,end=" <--> ")
current = current.next;
print(current.data)
print();
def inorder(root):
if root:
inorder(root.leftchild)
print("- %d"%root.value,end=' ')
DLL.append(root.value)
inorder(root.rightchild)

root = Node(1)
root.leftchild	 = Node(2)
root.rightchild	 = Node(3)
root.leftchild.leftchild = Node(4)
root.leftchild.rightchild = Node(5)
root.rightchild.leftchild = Node(6)
print("THE BINARY TREE IS -")
print("      1      ")
print("  2       3  ")
print("4   5   6   -")
DLL = insert()
print("THE IN-ORDER TRAVERSAL IS :",end='')
inorder(root)
DLL.display()```

In the above program-

• The class ‘Node’ stores a node of the binary tree.
• Class ‘DLL_Node’ stores a node of the doubly-linked list.
• The ‘insert’ Python class contains two functions ‘append()’ and ‘display()’.
1. append() –> This function inserts a new node in the doubly-linked list.
2. display() –> It displays the doubly-linked list onto the screen
• The function ‘inorder()’ prints the in-order traversal of the binary tree. And also, it appends the nodes in the doubly-linked list.
• The variable ‘root’ represents the binary tree.
• Here, we create a binary tree without taking values from users for simplicity. But you can also create the binary tree with user-entered node values.
• The variable ‘DLL’ represents the doubly-linked list.
• During the in-order traversal of the binary tree, we append the nodes in the doubly-linked list.
• Finally, we get the in-order traversal of the binary tree in the doubly-linked list.

#### Python program output

The binary tree created by the Python program is-

The output of this Python program is given below-

```[email protected]:~/python\$ python3 dll.py
THE BINARY TREE IS -
1
2       3
4   5   6   -
THE IN-ORDER TRAVERSAL IS :- 4 - 2 - 5 - 1 - 6 - 3

THE RESULTANT DLL IS -
4 <--> 2 <--> 5 <--> 1 <--> 6 <--> 3

[email protected]:~/python\$```

So, the program displays the doubly-linked list created after conversion. The doubly-linked list is shown below-

Thanks for reading this tutorial. I hope it helps you.