Convert a given binary tree to doubly linked list in Python

Post Views: 658

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-

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.