Convert a given Binary Tree to Doubly Linked List. Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL) In-Place. The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder trave…

gistfile1.py

# Python3 program to convert a given Binary 
# Tree to Doubly Linked List 
class Node: 
	def __init__(self, data): 
		self.data = data 
		self.left = self.right = None

class BinaryTree: 
	root, head = None, None
	
	# A simple recursive function to convert a given 
	# Binary tree to Doubly Linked List 
	def BToDll(self, root: Node): 
		if root is None: 
			return

		# Recursively convert right subtree 
		self.BToDll(root.right) 

		# Insert root into doubly linked list 
		root.right = self.head 

		# Change left pointer of previous head 
		if self.head is not None: 
			self.head.left = root 

		# Change head of doubly linked list 
		self.head = root 

		# Recursively convert left subtree 
		self.BToDll(root.left) 

	@staticmethod
	def print_list(head: Node): 
		print('Extracted Double Linked list is:') 
		while head is not None: 
			print(head.data, end = ' ') 
			head = head.right 

# Driver Code 
if __name__ == '__main__': 
	
	""" 
	Constructing below tree 
			5 
		// \\ 
		3 6 
		// \\ \\ 
		1 4 8 
	// \\ // \\ 
	0 2 7 9 
	"""
	tree = BinaryTree() 
	tree.root = Node(5) 
	tree.root.left = Node(3) 
	tree.root.right = Node(6) 
	tree.root.left.left = Node(1) 
	tree.root.left.right = Node(4) 
	tree.root.right.right = Node(8) 
	tree.root.left.left.left = Node(0) 
	tree.root.left.left.right = Node(2) 
	tree.root.right.right.left = Node(7) 
	tree.root.right.right.right = Node(9) 

	tree.BToDll(tree.root) 
	tree.print_list(tree.head) 

version.cpp

// C++ program to convert a given Binary 
// Tree to Doubly Linked List 
#include <bits/stdc++.h> 

// Structure for tree and linked list 
struct Node 
{ 
	int data; 
	Node *left, *right; 
}; 

// A simple recursive function to convert a given 
// Binary tree to Doubly Linked List 
// root	 --> Root of Binary Tree 
// head_ref --> Pointer to head node of created 
//			 doubly linked list 
void BToDLL(Node* root, Node** head_ref) 
{ 
	// Base cases 
	if (root == NULL) 
		return; 

	// Recursively convert right subtree 
	BToDLL(root->right, head_ref); 

	// insert root into DLL 
	root->right = *head_ref; 

	// Change left pointer of previous head 
	if (*head_ref != NULL) 
		(*head_ref)->left = root; 

	// Change head of Doubly linked list 
	*head_ref = root; 

	// Recursively convert left subtree 
	BToDLL(root->left, head_ref); 
} 

// Utility function for allocating node for Binary 
// Tree. 
Node* newNode(int data) 
{ 
	Node* node = new Node; 
	node->data = data; 
	node->left = node->right = NULL; 
	return node; 
} 

// Utility function for printing double linked list. 
void printList(Node* head) 
{ 
	printf("Extracted Double Linked list is:\n"); 
	while (head) 
	{ 
		printf("%d ", head->data); 
		head = head->right; 
	} 
} 

// Driver program to test above function 
int main() 
{ 
	/* Constructing below tree 
			5 
			/ \ 
			3	 6 
		/ \	 \ 
		1 4	 8 
		/ \	 / \ 
		0 2	 7 9 */
	Node* root = newNode(5); 
	root->left = newNode(3); 
	root->right = newNode(6); 
	root->left->left = newNode(1); 
	root->left->right = newNode(4); 
	root->right->right = newNode(8); 
	root->left->left->left = newNode(0); 
	root->left->left->right = newNode(2); 
	root->right->right->left = newNode(7); 
	root->right->right->right = newNode(9); 

	Node* head = NULL; 
	BToDLL(root, &head); 

	printList(head); 

	return 0; 
} 

O(n), as the solution does a single traversal of given Binary Tree.