Python program to convert a given binary tree to doubly linked list.

In this program, we need to convert the given binary tree to corresponding doubly liked list.

The binary tree is a tree data structure in which each node has at most two children node.

This can be achieved by traversing the tree in the in-order manner that is, left the child -> root ->right node. Traverse left sub-tree and convert it into the doubly linked list by adding nodes to the end of the list. In this way, the leftmost node will become head of the list. Then, convert the right sub-tree into the doubly linked list.

Python program to convert a given binary tree to doubly linked list

ALGORITHM:

Define a Node class which represents a node in the binary tree. It will have three properties: data left, and right where the left and right represent two children of a node.
Root will represent the root of the binary tree. Head and tail node represent the head and tail of the doubly linked list.
BinaryTreeToDLL() will convert the given binary tree to the corresponding doubly linked list.

Perform inorder traversal of the binary tree by converting the left subtree first.
If the list is empty, both head and tail will point to a node.
If the list is not empty, the node will be inserted at the end of the list. Here, pointer left, and right will represent the previous and next pointer of the doubly linked list.
Now, recursively call BinaryTreeToDLL() to convert the right subtree.

a. display() will show all the nodes present in the list.

Define a new node ‘current’ that will point to the head.
Print current.data till current points to null.
Current will point to the next node in the list in each iteration.

PROGRAM:

#Represent a node of binary tree
class Node:
def __init__(self,data):
self.data = data;
self.left = None;
self.right = None;
class BinaryTreeToDLL:
def __init__(self):
#Represent the root of binary tree
self.root = None;
#Represent the head and tail of the doubly linked list
self.head = None;
self.tail = None;
#convertbtToDLL() will convert the given binary tree to corresponding doubly linked list
def convertbtToDLL(self, node):
#Checks whether node is None
if(node == None):
return;
#Convert left subtree to doubly linked list
self.convertbtToDLL(node.left);
#If list is empty, add node as head of the list
if(self.head == None):
#Both head and tail will point to node
self.head = self.tail = node;
#Otherwise, add node to the end of the list
else:
#node will be added after tail such that tail’s right will point to node
self.tail.right = node;
#node’s left will point to tail
node.left = self.tail;
#node will become new tail
self.tail = node;
#Convert right subtree to doubly linked list
self.convertbtToDLL(node.right);
#display() will print out the nodes of the list
def display(self):
#Node current will point to head
current = self.head;
if(self.head == None):
print(“List is empty”);
return;
print(“Nodes of generated doubly linked list: “);
while(current != None):
#Prints each node by incrementing pointer.
print(current.data),
current = current.right;
bt = BinaryTreeToDLL();
#Add nodes to the binary tree
bt.root = Node(1);
bt.root.left = Node(2);
bt.root.right = Node(3);
bt.root.left.left = Node(4);
bt.root.left.right = Node(5);
bt.root.right.left = Node(6);
bt.root.right.right = Node(7);
#Converts the given binary tree to doubly linked list
bt.convertbtToDLL(bt.root);
#Displays the nodes present in the list
bt.display();

#Represent a node of binary tree class Node: def __init__(self,data): self.data = data; self.left = None; self.right = None; class BinaryTreeToDLL: def __init__(self): #Represent the root of binary tree self.root = None; #Represent the head and tail of the doubly linked list self.head = None; self.tail = None; #convertbtToDLL() will convert the given binary tree to corresponding doubly linked list def convertbtToDLL(self, node): #Checks whether node is None if(node == None): return; #Convert left subtree to doubly linked list self.convertbtToDLL(node.left); #If list is empty, add node as head of the list if(self.head == None): #Both head and tail will point to node self.head = self.tail = node; #Otherwise, add node to the end of the list else: #node will be added after tail such that tail’s right will point to node self.tail.right = node; #node’s left will point to tail node.left = self.tail; #node will become new tail self.tail = node; #Convert right subtree to doubly linked list self.convertbtToDLL(node.right); #display() will print out the nodes of the list def display(self): #Node current will point to head current = self.head; if(self.head == None): print(“List is empty”); return; print(“Nodes of generated doubly linked list: “); while(current != None): #Prints each node by incrementing pointer. print(current.data), current = current.right; bt = BinaryTreeToDLL(); #Add nodes to the binary tree bt.root = Node(1); bt.root.left = Node(2); bt.root.right = Node(3); bt.root.left.left = Node(4); bt.root.left.right = Node(5); bt.root.right.left = Node(6); bt.root.right.right = Node(7); #Converts the given binary tree to doubly linked list bt.convertbtToDLL(bt.root); #Displays the nodes present in the list bt.display();

Output:

Nodes of generated doubly linked list: 
4 2 5 1 6 3 7

by python-tutorials.in
on 8th October 2019

Python program to convert a given binary tree to doubly linked list.