Binary Tree to CDLL

ACDLL, orcircular_doubly_linked_list, is a type of linked list in which each node has a reference to both the previous and next nodes in the list, as well as a special property that the last node in the list points back to the first node, creating a circular structure.

A CDLL can be used to represent a sequence of elements that needs to be traversed in a cyclic manner, such as a playlist of songs that can be played continuously in a loop. It can also be useful in certain algorithms and data structures, such as hash tables or circular buffers.

Compared to a singly linked list or a doubly linked list, a CDLL can offer some advantages in terms of traversal efficiency, since it allows for both forward and backward traversal without the need to reverse the list or maintain a separate stack or queue. However, it also requires more memory for storing the additional reference to the last node, and can be slightly more complex to implement and maintain.

# Python program for conversion
# of Binary Tree to CDLL
 
# A binary tree node has data,
# and left and right pointers
class Node:
	def __init__(self, data):
		self.data = data
		self.left = self.right = None
 
v = []
 
# Function to perform In-Order traversal of the
# tree and store the nodes in a vector
def inorder(root):
	global v
	
	if (root == None):
		return
 
	# first recur on left child
	inorder(root.left)
 
	# append the data of node in vector
	v.append(root.data)
 
	# now recur on right child
	inorder(root.right)
 
# Function to convert Binary Tree to Circular
# Doubly Linked list using the vector which stores
# In-Order traversal of the Binary Tree
def bTreeToCList(root):
 
	global v
	
	# Base cases
	if (root == None):
		return None
 
	# Vector to be used for storing the nodes
	# of tree in In-order form
	v = []
 
	# Calling the In-Order traversal function
	inorder(root)
 
	# Create the head of the linked list pointing
	# to the root of the tree
	head_ref = Node(v[0])
 
	# Create a current pointer to be used in traversal
	curr = head_ref
 
	i = 1
	
	# Traversing the nodes of the tree starting
	# from the second elements
	while ( i < len(v)) :
	
		
		# Create a temporary pointer
		# pointing to current
		temp = curr
 
		# Current's right points to the current
		# node in traversal
		curr.right = Node(v[i])
 
		# Current points to its right
		curr = curr.right
 
		# Current's left points to temp
		curr.left = temp
		i = i + 1
 
	# Current's right points to head of the list
	curr.right = head_ref
 
	# Head's left points to current
	head_ref.left = curr
 
	# Return head of the list
	return head_ref
 
# Display Circular Link List
def displayCList(head):
 
	print("Circular Doubly Linked List is :", end = "")
 
	itr = head
	while(True):
		print(itr.data, end = " ")
		itr = itr.right
		if(head == itr):
			break
 
	print()
 
# Driver Code
root = Node(10)
root.left = Node(12)
root.right = Node(15)
root.left.left = Node(25)
root.left.right = Node(30)
root.right.left = Node(36)
 
head = bTreeToCList(root)
displayCList(head)
 

Solution using Recursion

# Python3 Program to convert a Binary
# Tree to a Circular Doubly Linked List
 
 
class newNode:
	def __init__(self, data):
		self.data = data
		self.left = self.right = None
 
# A function that appends rightList
# at the end of leftList.
 
 
def concatenate(leftList, rightList):
 
	# If either of the list is empty
	# then return the other list
	if (leftList == None):
		return rightList
	if (rightList == None):
		return leftList
 
	# Store the last Node of left List
	leftLast = leftList.left
 
	# Store the last Node of right List
	rightLast = rightList.left
 
	# Connect the last node of Left List
	# with the first Node of the right List
	leftLast.right = rightList
	rightList.left = leftLast
 
	# Left of first node points to
	# the last node in the list
	leftList.left = rightLast
 
	# Right of last node refers to
	# the first node of the List
	rightLast.right = leftList
 
	return leftList
 
# Function converts a tree to a circular
# Linked List and then returns the head
# of the Linked List
 
 
def bTreeToCList(root):
	if (root == None):
		return None
 
	# Recursively convert left and
	# right subtrees
	left = bTreeToCList(root.left)
	right = bTreeToCList(root.right)
 
	# Make a circular linked list of single
	# node (or root). To do so, make the
	# right and left pointers of this node
	# point to itself
	root.left = root.right = root
 
	# Step 1 (concatenate the left list
	#		 with the list with single
	#		 node, i.e., current node)
	# Step 2 (concatenate the returned list
	#		 with the right List)
	return concatenate(concatenate(left,
								root), right)
 
# Display Circular Link List
 
 
def displayCList(head):
	print("Circular Linked List is :")
	itr = head
	first = 1
	while (head != itr or first):
		print(itr.data, end=" ")
		itr = itr.right
		first = 0
	print()
 
 
# Driver Code
if __name__ == '__main__':
	root = newNode(10)
	root.left = newNode(12)
	root.right = newNode(15)
	root.left.left = newNode(25)
	root.left.right = newNode(30)
	root.right.left = newNode(36)
 
	head = bTreeToCList(root)
	displayCList(head)