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-
- 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-
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-
siddharth@siddharth-Lenovo-Y520-15IKBN:~/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 siddharth@siddharth-Lenovo-Y520-15IKBN:~/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.