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

## About binary tree

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
- Linked lists

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-

## Doubly-linked list

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.head = None; self.tail = None; def append(self, new_data): new_node = DLL_Node(data = new_data) if self.head is None: self.head = self.tail = new_node else: self.tail.next = new_node new_node.prev = self.tail self.tail=new_node def display(self): print("\n\nTHE RESULTANT DLL IS -") current = self.head; if(self.head == None): 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.

Also read:

Insertion and Deletion in a Binary search tree in Python

## Leave a Reply