Given a Binary Tree of N edges. The task is to convert this to a Circular Doubly Linked List(CDLL) in-place. The left and right pointers in nodes are to be used as previous and next pointers respectively in converted CDLL. The order of nodes in CDLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (left most node in BT) must be head node of the CDLL.
Example 1:
Input:
      1
    /   \
   3     2
Output:
3 1 2 
2 1 3
Explanation: After converting tree to CDLL
when CDLL is is traversed from head to
tail and then tail to head, elements
are displayed as in the output.
Example 2:
Input:
     10
   /    \
  20    30
 /  \
40  60
Output:
40 20 60 10 30 
30 10 60 20 40
Explanation:After converting tree to CDLL,
when CDLL is is traversed from head to
tail and then tail to head, elements
are displayed as in the output.
Your Task:
You don't have to take input. Complete the function bTreeToCList() that takes root as a parameter and returns the head of the list. The printing is done by the driver code. 
Constraints:
1 <= N <= 10^{3}
1 <= Data of a node <= 10^{4}
Expected time complexity: O(N)
Expected auxiliary space: O(h) , where h = height of tree

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3


'''
class Node:
    def __init__(self,val):
        self.data = val
        self.left = None
        self.right = None

'''

class Solution:
    
    #Function to convert binary tree into circular doubly linked list.
    def bTreeToClist(self, root):
        #Your code here


Solutions:
class Solution:

	def bTreeToClist(self, root):
		a = [None]
		b = [None]
		num = root

		def link(num):
			if num == None:
				return num
			link(num.left)
			if b[0] == None:
				a[0] = b[0] = num
			else:
				b[0].right = num
				num.left = b[0]
			b[0] = num
			link(num.right)
		link(num)
		a[0].left = b[0]
		b[0].right = a[0]
		return a[0]


class Solution:

	def bTreeToClist(self, root):
		leav = []
		self.inorder(root, leav)
		head = None
		tmp = None
		for i in leav:
			if head is None:
				node = Node(i)
				node.left = None
				node.right = None
				head = node
				tmp = head
			else:
				node = Node(i)
				node.left = tmp
				tmp.right = node
				tmp = node
		tmp.right = head
		head.left = tmp
		return head

	def inorder(self, rt, leav):
		if rt is None:
			return None
		self.inorder(rt.left, leav)
		leav.append(rt.data)
		self.inorder(rt.right, leav)


class Solution:

	def bTreeToClist(self, root):
		lis = []

		def fun(root):
			if root == None:
				return
			fun(root.left)
			lis.append(root.data)
			fun(root.right)
		fun(root)
		temp = None
		head = None
		for i in lis:
			new = Node(i)
			if temp == None:
				temp = new
				head = temp
			else:
				temp.right = new
				new.left = temp
				temp = temp.right
		temp.right = head
		head.left = temp
		return head


class Solution:

	def bTreeToClist(self, root):
		if root == None:
			return None
		left = self.bTreeToClist(root.left)
		right = self.bTreeToClist(root.right)
		root.left = root.right = root
		return self.concatenate(self.concatenate(left, root), right)

	def concatenate(self, leftList, rightList):
		if leftList == None:
			return rightList
		if rightList == None:
			return leftList
		leftLast = leftList.left
		rightLast = rightList.left
		leftLast.right = rightList
		rightList.left = leftLast
		leftList.left = rightLast
		rightLast.right = leftList
		return leftList


class Solution:

	def __init__(self):
		self.prev = None
		self.head = None

	def createTree(self, root):
		if root is None:
			return root
		self.createTree(root.left)
		if self.prev is None:
			self.head = root
		else:
			self.prev.right = root
			root.left = self.prev
		self.prev = root
		self.createTree(root.right)

	def bTreeToClist(self, root):
		self.createTree(root)
		self.head.left = self.prev
		self.prev.right = self.head
		return self.head


class Solution:

	def bTreeToClist(self, root):
		if root == None:
			return None
		if root.left == None and root.right == None:
			(root.left, root.right) = (root, root)
			return root
		myleft = self.bTreeToClist(root.left)
		myright = self.bTreeToClist(root.right)
		if root.left != None and root.right != None:
			(track1, track2) = (myleft, myright.left)
			(root.left, root.right) = (myleft.left, myright)
			myleft.left.right = myright.left = root
		elif myleft == None:
			(track1, track2) = (root, myright.left)
			(root.right, myright.left) = (myright, root)
		elif myright == None:
			(track1, track2) = (myleft, root)
			(myleft.left.right, root.left) = (root, myleft.left)
		(track1.left, track2.right) = (track2, track1)
		return track1


class Solution:

	def bTreeToClist(self, root):

		def construct(root):
			if root.left is None and root.right is None:
				return [root, root]
			dataL = dataR = None
			if root.left is not None:
				dataL = construct(root.left)
			if root.right is not None:
				dataR = construct(root.right)
			if dataL is not None:
				dataL[1].right = root
				root.left = dataL[1]
			else:
				dataL = [root, root]
			if dataR is not None:
				root.right = dataR[0]
				dataR[0].left = root
			else:
				dataR = [root, root]
			return [dataL[0], dataR[1]]
		data = construct(root)
		data[1].right = data[0]
		data[0].left = data[1]
		return data[0]


class Solution:

	def creat(self, arr, n, start):
		newNode = None
		temp = None
		i = 0
		while i < n:
			newNode = Node(0)
			newNode.data = arr[i]
			if i == 0:
				start = newNode
				newNode.left = start
				newNode.right = start
			else:
				temp = start.left
				temp.right = newNode
				newNode.right = start
				newNode.left = temp
				temp = start
				temp.left = newNode
			i += 1
		return start

	def convert(self, root, lis):
		if root == None:
			return
		self.convert(root.left, lis)
		lis.append(root.data)
		self.convert(root.right, lis)

	def bTreeToClist(self, root):
		lis = []
		self.convert(root, lis)
		start = None
		return self.creat(lis, len(lis), start)


class Solution:

	def bTreeToClist(self, root):
		if root == None:
			return root
		l = self.bTreeToClist(root.left)
		r = self.bTreeToClist(root.right)
		if l != None:
			lend = l.left
			lstart = l
			lend.right = root
			root.left = lend
			if r != None:
				root.right = r
				rend = r.left
				rstart = r
				rstart.left = root
				rend.right = lstart
				lstart.left = rend
			else:
				root.right = lstart
				lstart.left = root
			return l
		else:
			if r != None:
				rend = r.left
				rstart = r
				root.right = rstart
				rstart.left = root
				rend.right = root
				root.left = rend
			else:
				temp = root
				root.left = temp
				root.right = temp
			return root


class Solution:

	def bTreeToClist(self, root):

		def helper(root):
			(a, b) = (root, root)
			if root.left:
				(a, x) = helper(root.left)
				x.right = root
				root.left = x
			if root.right:
				(x, b) = helper(root.right)
				x.left = root
				root.right = x
			return (a, b)
		(a, b) = helper(root)
		a.left = b
		b.right = a
		return a


class Solution:

	def bTreeToClist(self, root):
		s = []
		head = None
		prev = None
		while len(s) > 0 or root:
			if root:
				s.append(root)
				root = root.left
			else:
				root = s.pop()
				if not head:
					head = root
					prev = root
				else:
					prev.right = root
					root.left = prev
					prev = root
				root = root.right
		head.left = prev
		prev.right = head
		return head


class Solution:

	def bTreeToClist(self, root):
		a = []

		def solve(root):
			if root:
				solve(root.left)
				a.append(root.data)
				solve(root.right)
		solve(root)
		n = Node(0)
		p = n
		for i in range(len(a)):
			if i != len(a) - 1:
				k = Node(a[i])
				n.right = k
				k.left = n
				n = n.right
			else:
				k = Node(a[i])
				n.right = k
				k.left = n
				k.right = p.right
		p = p.right
		p.left = None
		return p


class Solution:
	head = None
	prev = None

	def bTreeToClist(self, root):
		if root == None:
			return root
		self.bTreeToClist(root.left)
		if self.prev == None:
			self.head = root
		else:
			self.prev.right = root
			root.left = self.prev
		self.prev = root
		self.bTreeToClist(root.right)
		self.prev.right = self.head
		self.head.left = self.prev
		return self.head


class Solution:

	def __init__(self):
		self.prev = Node(None)
		self.head = Node(None)
		rootval = Node(None)

	def bTreeToClist(self, root):
		self.bToCDLL(root)
		self.head.left = self.prev
		self.prev.right = self.head
		return self.head

	def bToCDLL(self, root):
		if root == None:
			return
		if root.left:
			self.bToCDLL(root.left)
		if self.prev.data == None:
			self.head = self.prev = root
		else:
			root.left = self.prev
			self.prev.right = root
		self.prev = root
		if root.right:
			self.bToCDLL(root.right)
		return self.head


class Solution:

	def bTreeToClist(self, root):
		li = []

		def inorder(root):
			if root == None:
				return
			inorder(root.left)
			li.append(root.data)
			inorder(root.right)
		inorder(root)
		temp = None
		head = None
		for i in li:
			newnode = Node(i)
			if temp == None:
				temp = newnode
				head = temp
			else:
				temp.right = newnode
				newnode.left = temp
				temp = temp.right
		temp.right = head
		head.left = temp
		return head


class Solution:

	def bTreeToClist(self, root):
		st = []
		dum = Node(-1)
		curr = dum
		while True:
			if root:
				st.append(root)
				root = root.left
			elif len(st) == 0:
				break
			else:
				root = st.pop()
				curr.right = root
				root.left = curr
				curr = curr.right
				root = root.right
		curr.right = dum.right
		dum.right.left = curr
		return curr.right


class Solution:

	def add(self, node):
		self.last = node
		if self.prev:
			self.prev.right = node
			node.left = self.prev
			self.prev = node
		else:
			self.head = node
			self.prev = node

	def inorder(self, node):
		if node:
			self.inorder(node.left)
			self.add(node)
			self.inorder(node.right)

	def bTreeToClist(self, root):
		self.head = None
		self.prev = None
		self.inorder(root)
		self.last.right = self.head
		self.head.left = self.last
		return self.head


class Solution:

	def bTreeToClist(self, root):
		head = Node(-1)
		first = head
		last = None
		curr = root
		while curr != None:
			if curr.left == None:
				curr.left = first
				first.right = curr
				first = first.right
				curr = curr.right
			else:
				temp = curr.left
				while temp.right != None and temp.right != curr:
					temp = temp.right
				if temp.right == curr:
					curr.left = first
					first.right = curr
					first = first.right
					curr = curr.right
				else:
					temp.right = curr
					curr = curr.left
		head = head.right
		head.left = first
		first.right = head
		return head


class Solution:

	def bTreeToClist(self, root):
		cur = None

		def helper(root):
			nonlocal cur
			if root == None:
				return None
			helper(root.left)
			root.left = cur
			cur = root
			helper(root.right)
		helper(root)
		if cur == None:
			return None
		cur.right = None
		temp1 = cur
		temp2 = cur.left
		while temp1 != None and temp2 != None:
			temp2.right = temp1
			temp1 = temp1.left
			temp2 = temp2.left
		cur.right = temp1
		temp1.left = cur
		return temp1


class Solution:

	def __init__(self):
		self.d = []

	def io(self, a):
		if a:
			self.io(a.left)
			self.d.append(a.data)
			self.io(a.right)

	def bTreeToClist(self, root):
		self.io(root)
		head = Node(self.d[0])
		tail = head
		for i in range(1, len(self.d)):
			tail.right = Node(self.d[i])
			tail.right.left = tail
			tail = tail.right
		if tail != head:
			tail.right = head
			head.left = tail
		return head


class Solution:

	def bTreeToClist(self, root):

		def TreeToClist(root):
			if root is None:
				return (None, None)
			if not root.left and (not root.right):
				return (root, root)
			(left_l, left_r) = TreeToClist(root.left)
			(right_l, right_r) = TreeToClist(root.right)
			if left_r and right_l:
				left_r.right = root
				root.left = left_r
				root.right = right_l
				right_l.left = root
				return (left_l, right_r)
			elif not left_r and right_l:
				root.right = right_l
				right_l.left = root
				return (root, right_r)
			elif left_r and (not right_l):
				left_r.right = root
				root.left = left_r
				return (left_l, root)
		(l, r) = TreeToClist(root)
		r.right = l
		l.left = r
		return l


class Solution:

	def bTreeToClist(self, root):

		def func(root, li):
			if root is None:
				return
			func(root.left, li)
			li.append(root.data)
			func(root.right, li)
		li = []
		func(root, li)
		cur = Node(li[0])
		dummy = cur
		ind = 1
		for i in range(1, len(li)):
			ans = Node(li[i])
			cur.right = ans
			ans.left = cur
			cur = cur.right
		cur.right = dummy
		dummy.left = cur
		return dummy


class Solution:

	def bTreeToClist(self, root):
		arr = self.helper(root)
		arr.append(arr[0])
		for i in range(len(arr) - 1):
			arr[i].right = arr[i + 1]
			arr[i + 1].left = arr[i]
		return arr[0]

	def helper(self, root):
		if root is None:
			return []
		output = []
		output += self.helper(root.left)
		output += [root]
		output += self.helper(root.right)
		return output


class Solution:

	def bTreeToClist(self, root):
		(head, tail) = self.bToDllUtil(root)
		if head:
			head.left = tail
			tail.right = head
		return head

	def bToDllUtil(self, root):
		if not root:
			return (None, None)
		if not root.left and (not root.right):
			return (root, root)
		(head, tail) = self.bToDllUtil(root.left)
		if tail:
			tail.right = root
		root.left = tail
		(head2, tail2) = self.bToDllUtil(root.right)
		root.right = head2
		if head2:
			head2.left = root
		n_head = head if head else root
		n_tail = tail2 if tail2 else root
		return (n_head, n_tail)


class Solution:

	def bTreeToClist(self, root):
		pair = self.helper(root)
		pair.tail.right = pair.head
		return pair.head

	def helper(self, root):
		if root == None:
			return Pair(None, None)
		LeftDLL = self.helper(root.left)
		RightDLL = self.helper(root.right)
		p = Pair(LeftDLL.head, RightDLL.tail)
		if LeftDLL.tail == None:
			root.left = None
			p.head = root
		else:
			root.left = LeftDLL.tail
			LeftDLL.tail.right = root
		if RightDLL.head == None:
			root.right = None
			p.tail = root
		else:
			root.right = RightDLL.head
			RightDLL.head.left = root
		return p

class Pair:
	head = None
	tail = None

	def __init__(self, head, tail):
		self.head = head
		self.tail = tail


class CDLL:

	def __init__(self, head=None):
		self.head = head
		self.tail = head

	def add(self, val):
		node = Node(val)
		if not self.head:
			self.head = node
			self.tail = node
			self.tail.right = self.head
		else:
			self.tail.right = node
			node.left = self.tail
			self.tail = node
			node.right = self.head

class Solution:

	def bTreeToClist(self, root):

		def inO(root, tra=[]):
			if root:
				tra = inO(root.left, tra)
				tra.append(root.data)
				tra = inO(root.right, tra)
			return tra
		tra = inO(root, [])
		res = CDLL()
		for i in tra:
			res.add(i)
		return res.head


class Solution:

	def bTreeToClist(self, root):
		prev = None
		return helper(root)

def helper(root):
	head = [None]
	prev = [None]

	def tree(root):
		if root == None:
			return root
		tree(root.left)
		if prev[0] == None:
			head[0] = prev[0] = root
		else:
			prev[0].right = root
			root.left = prev[0]
		prev[0] = root
		tree(root.right)
	tree(root)
	head[0].left = prev[0]
	prev[0].right = head[0]
	return head[0]


def join(a, b):
	if a is None:
		return b
	if b is None:
		return a
	a_end = a.left
	b_end = b.left
	a.left = b_end
	b_end.right = a
	b.left = a_end
	a_end.right = b
	return a

class Solution:

	def bTreeToClist(self, root):
		if root is None:
			return None
		left = self.bTreeToClist(root.left)
		right = self.bTreeToClist(root.right)
		root.left = root.right = root
		return join(join(left, root), right)


class Solution:

	def bTreeToClist(self, root):
		b = []
		Solution.bT(root, b)
		head = Node(b[0])
		p = head
		b.pop(0)
		for i in b:
			tmp = Node(i)
			tmp.left = p
			p.right = tmp
			p = tmp
		p.right = head
		head.left = p
		return head

	def bT(root, b):
		if root.left != None:
			Solution.bT(root.left, b)
		b.append(root.data)
		if root.right != None:
			Solution.bT(root.right, b)
		return


class Solution:

	def helper(self, node):
		if node is None:
			return
		self.helper(node.left)
		if self.root is None:
			self.root = node
		else:
			(self.prev.right, node.left) = (node, self.prev)
		self.prev = node
		self.helper(node.right)

	def bTreeToClist(self, root):
		(self.root, self.prev) = (None, None)
		self.helper(root)
		(self.root.left, self.prev.right) = (self.prev, self.root)
		return self.root


class Solution:

	def helper(self, node):
		if node is None:
			return
		(templeft, tempright) = (node.left, node.right)
		(node.left, node.right) = (None, None)
		self.helper(templeft)
		if self.root:
			temp = self.root
			while temp.right:
				temp = temp.right
			(temp.right, node.left) = (node, temp)
		else:
			self.root = node
		self.helper(tempright)
		self.last = node

	def bTreeToClist(self, root):
		if root is None:
			return
		if not root.left and (not right.right):
			(root.right, root.left) = (root, root)
			return root
		(self.root, self.last) = (None, None)
		self.helper(root)
		temp = self.root
		while temp.right:
			temp = temp.right
		temp.right = self.root
		return self.root

	def bTreeToClist(self, root):
		(head, prev) = ([None], [None])

		def tree(root):
			if root == None:
				return root
			tree(root.left)
			if prev[0] == None:
				head[0] = prev[0] = root
			else:
				prev[0].right = root
				root.left = prev[0]
			prev[0] = root
			tree(root.right)
		tree(root)
		(head[0].left, prev[0].right) = (prev[0], head[0])
		return head[0]


class LinkedList:

	def __init__(self):
		self.head = None
		self.last_node = None

	def getHead(self):
		return self.head

	def getTail(self):
		return self.last_node

	def append(self, new_data):
		if not self.last_node:
			self.head = Node(new_data)
			self.last_node = self.head
			self.last_node.right = self.head
			self.head.left = self.last_node
		else:
			x = Node(new_data)
			x.left = self.last_node
			self.last_node.right = x
			self.last_node = x
			self.last_node.right = self.head
			self.head.left = self.last_node

class Solution:

	def __init__(self):
		pass

	def bTreeToCListHelper(self, root, ll):
		if root.left:
			self.bTreeToCListHelper(root.left, ll)
		ll.append(root.data)
		if root.right:
			self.bTreeToCListHelper(root.right, ll)

	def bTreeToClist(self, root):
		ll = LinkedList()
		self.bTreeToCListHelper(root, ll)
		return ll.getHead()


class Solution:

	def bTreeToClist(self, root):
		prev = [None]
		head = self.connect(root, prev)
		head.left = prev[0]
		prev[0].right = head
		return head

	def connect(self, root, prev):
		if root is None:
			return root
		head = self.connect(root.left, prev)
		if prev[0] is None:
			head = root
		else:
			root.left = prev[0]
			prev[0].right = root
		prev[0] = root
		self.connect(root.right, prev)
		return head


class Solution:

	def bTreeToClist(self, root):
		if not root:
			return
		(self.head, self.pre) = (None, None)

		def inorder(node):
			if not node:
				return
			inorder(node.left)
			if not self.pre:
				self.head = node
				self.pre = node
			else:
				self.pre.right = node
				node.left = self.pre
				self.pre = node
			inorder(node.right)
		inorder(root)
		self.head.left = self.pre
		self.pre.right = self.head
		return self.head


class Solution:

	def bTreeToClist(self, root):
		if not root:
			return root
		self.prev = dummy = Node(-1)

		def inorder(node):
			if node is None:
				return
			inorder(node.left)
			self.prev.right = node
			node.left = self.prev
			self.prev = node
			inorder(node.right)
		inorder(root)
		self.prev.right = dummy.right
		dummy.right.left = self.prev
		return dummy.right


class Solution:

	def bTreeToClist(self, root):
		dummy = Node(-1)
		tail = dummy

		def dfs(root):
			nonlocal tail
			if root:
				dfs(root.left)
				tail.right = root
				root.left = tail
				tail = tail.right
				dfs(root.right)
		dfs(root)
		dummy.right.left = tail
		tail.right = dummy.right
		return dummy.right


class Solution:

	def traverse(self, root):
		if not root:
			return [None, None]
		[h1, t1] = self.traverse(root.left)
		[h2, t2] = self.traverse(root.right)
		head = root
		tail = root
		head.left = t1
		if t1:
			t1.right = head
			head = h1
		tail.right = h2
		if h2:
			h2.left = tail
			tail = t2
		return [head, tail]

	def bTreeToClist(self, root):
		[h, t] = self.traverse(root)
		if h and t:
			t.right = h
			h.left = t
		return h


class Solution:

	def bTreeToClist(self, root):
		head = Node(0)
		t = head
		st = []
		while st or root:
			if root:
				st.append(root)
				root = root.left
			else:
				root = st.pop(-1)
				t.right = root
				root.left = t
				t = root
				root = root.right
		head = head.right
		head.left = t
		t.right = head
		return head


class Solution:

	def get_inorder(self, root, order):
		if root is None:
			return
		ptr = root
		if ptr.left is not None:
			self.get_inorder(ptr.left, order)
		order.append(ptr.data)
		if ptr.right is not None:
			self.get_inorder(ptr.right, order)

	def bTreeToClist(self, root):
		inorder = []
		self.get_inorder(root, inorder)
		nodes = [Node(val) for val in inorder]
		head = nodes[0]
		prev = nodes[-1]
		for (node, one_ahead) in zip(nodes[:-1], nodes[1:]):
			curr = node
			curr.left = prev
			curr.right = one_ahead
			prev = curr
		curr = curr.right
		curr.left = prev
		curr.right = head
		return head


class Solution:

	def __init__(self):
		self.head = None
		self.tail = None

	def bTreeToClist(self, root):
		if root != None:
			self.bTreeToClist(root.left)
			if self.head == None and self.tail == None:
				self.head = Node(root.data)
				self.tail = self.head
			else:
				new_node = Node(root.data)
				self.tail.right = new_node
				self.tail.right.left = self.tail
				self.tail = new_node
				self.tail.right = self.head
				self.head.left = self.tail
			self.bTreeToClist(root.right)
		return self.head


class Solution:

	def bTreeToClist(self, root):
		ans = []

		def dfs(root):
			if not root:
				return
			dfs(root.left)
			ans.append(root.data)
			dfs(root.right)
		dfs(root)
		head = tail = Node(ans[0])
		for i in range(1, len(ans)):
			node = Node(ans[i])
			tail.right = node
			node.left = tail
			tail = tail.right
		head.left = tail
		tail.right = head
		return head


class Solution:

	def concat(self, leftList, rightList):
		if not leftList:
			return rightList
		if not rightList:
			return leftList
		leftLast = leftList.left
		rightLast = rightList.left
		leftLast.right = rightList
		rightList.left = leftLast
		leftList.left = rightLast
		rightLast.right = leftList
		return leftList

	def bTreeToClist(self, root):
		if not root:
			return
		left = self.bTreeToClist(root.left)
		right = self.bTreeToClist(root.right)
		root.left = root.right = root
		return self.concat(self.concat(left, root), right)


class Solution:

	def convert(self, root):
		if not root:
			return [None, None]
		root_head = root
		root_tail = root
		(left_head, left_tail) = self.convert(root.left)
		(right_head, right_tail) = self.convert(root.right)
		root.left = left_tail
		root.right = right_head
		if left_head:
			left_tail.right = root
			root_head = left_head
		if right_head:
			right_head.left = root
			root_tail = right_tail
		return [root_head, root_tail]

	def bTreeToClist(self, root):
		(head, tail) = self.convert(root)
		head.left = tail
		tail.right = head
		return head


class Solution:

	def bTreeToClist(self, root):
		dummy = Node(None)
		prev = [dummy]

		def rec(root):
			if not root:
				return
			rec(root.left)
			prev[0].right = root
			root.left = prev[0]
			prev[0] = root
			rec(root.right)
		rec(root)
		head = dummy.right
		head.left = prev[0]
		prev[0].right = head
		return head


class Solution:

	def bTreeToClist(self, root):
		head = None
		tail = None
		stack = []
		while 1:
			while root:
				stack.append(root)
				root = root.left
			if not stack:
				break
			else:
				tmp = stack.pop()
				node = Node(tmp.data)
				if not tail:
					head = node
					tail = node
				else:
					tail.right = node
					node.left = tail
					tail = node
				root = tmp.right
		if tail:
			tail.right = head
			head.left = tail
		return head


class Solution:

	def concate(self, leftlist, rightlist):
		if leftlist is None:
			return rightlist
		if rightlist is None:
			return leftlist
		leftlast = leftlist.left
		rightlast = rightlist.left
		leftlast.right = rightlist
		rightlist.left = leftlast
		leftlist.left = rightlast
		rightlast.right = leftlist
		return leftlist

	def bTreeToClist(self, root):
		if root is None:
			return None
		leftlist = self.bTreeToClist(root.left)
		rightlist = self.bTreeToClist(root.right)
		root.left = root.right = root
		return self.concate(self.concate(leftlist, root), rightlist)


class Solution:

	def bTreeToClist(self, root):
		head = None
		prev = None
		curr = root
		flag = 0
		while curr is not None:
			if curr.left is None:
				new_node = Node(curr.data)
				if prev:
					prev.right = new_node
				new_node.right = None
				new_node.left = prev
				prev = new_node
				if flag == 0:
					head = prev
					flag += 1
				curr = curr.right
			else:
				pred = curr.left
				while pred.right is not None and pred.right is not curr:
					pred = pred.right
				if pred.right is None:
					pred.right = curr
					curr = curr.left
				else:
					pred.right = None
					new_node = Node(curr.data)
					prev.right = new_node
					new_node.left = prev
					new_node.right = None
					prev = new_node
					curr = curr.right
		prev.right = head
		head.left = prev
		return head


class Solution:

	def __init__(self):
		self.pre = None
		self.start = None

	def bTreeToClist1(self, root):
		if root == None:
			return None
		left = self.bTreeToClist1(root.left)
		if self.pre == None:
			self.pre = root
			self.start = self.pre
		else:
			self.pre.right = root
			root.left = self.pre
			self.pre = self.pre.right
		right = self.bTreeToClist1(root.right)

	def bTreeToClist(self, root):
		self.bTreeToClist1(root)
		self.start.left = self.pre
		self.pre.right = self.start
		return self.start


class Solution:

	def __init__(self):
		self.prev = None

	def bToDLL(self, root):
		if not root:
			return None
		h = self.bToDLL(root.left)
		if self.prev is None:
			h = root
		else:
			root.left = self.prev
			self.prev.right = root
		self.prev = root
		self.bToDLL(root.right)
		return h

	def bTreeToClist(self, root):
		h = self.bToDLL(root)
		self.prev.right = h
		h.left = self.prev
		return h


class Solution:

	def ino(self, r, l):
		if r is None:
			return
		self.ino(r.left, l)
		l.append(r)
		self.ino(r.right, l)

	def bTreeToClist(self, root):
		l = []
		self.ino(root, l)
		n = len(l)
		for i in range(n - 1):
			l[i].right = l[i + 1]
			l[i + 1].left = l[i]
		l[n - 1].right = l[0]
		l[0].left = l[n - 1]
		return l[0]


class Solution:

	def __init__(self):
		self.head = None
		self.tail = None

	def addInCircular(self, data):
		tem = self.head
		if tem is None:
			self.head = Node(data)
			self.head.right = self.head
			self.head.left = self.head
			self.tail = self.head
		else:
			self.tail.right = Node(data)
			self.tail.right.left = self.tail
			self.tail = self.tail.right
			self.tail.right = self.head
			self.head.left = self.tail

	def bTreeToClist(self, root):
		tem = root

		def inorder(tem):
			if tem is None:
				return
			inorder(tem.left)
			self.addInCircular(tem.data)
			inorder(tem.right)
		inorder(tem)
		return self.head


class Solution:
	head = tail = None

	def bTreeToClist(self, root):

		def inorder(root):
			if root.left:
				inorder(root.left)
			if Solution.head is None:
				Solution.head = Solution.tail = root
			else:
				root.data
				Solution.tail.right = root
				root.left = Solution.tail
				Solution.tail = Solution.tail.right
			if root.right:
				inorder(root.right)
		inorder(root)
		Solution.tail.right = Solution.head
		root = Solution.head
		Solution.tail = Solution.head = None
		return root


class Solution:

	def bTreeToClist(self, root):

		def convert(root):
			if not root:
				return
			left = convert(root.left)
			if left:
				rightmost = left
				while rightmost.right:
					rightmost = rightmost.right
				rightmost.right = root
				root.left = rightmost
			right = convert(root.right)
			if right:
				leftmost = right
				while leftmost.left:
					leftmost = leftmost.left
				leftmost.left = root
				root.right = leftmost
			return root
		a = convert(root)
		aleft = a
		while aleft.left:
			aleft = aleft.left
		aright = a
		while aright.right:
			aright = aright.right
		aleft.left = aright
		aright.right = aleft
		return aleft


class Solution:

	def bTreeToClist(self, root):
		prev = None
		head = None

		def traverse(root):
			nonlocal prev, head
			if root == None:
				return
			traverse(root.left)
			temp = Node(root.data)
			if prev == None:
				head = temp
			else:
				temp.left = prev
				prev.right = temp
			prev = temp
			traverse(root.right)
		traverse(root)
		head.left = prev
		prev.right = head
		return head


class Solution:

	def __init__(self):
		self.prev = None
		self.head = None

	def bTreeToClist(self, root):
		self.inorder(root)
		self.head.left = self.prev
		self.prev.right = self.head
		return self.head

	def inorder(self, root):
		if not root:
			return
		self.inorder(root.left)
		if self.head is None:
			self.head = root
		else:
			self.prev.right = root
			root.left = self.prev
		self.prev = root
		self.inorder(root.right)


class Solution:

	def bTreeToClist(self, root):
		head = last = None

		def f(r):
			if not r:
				return (None, None)
			nonlocal head, last
			(ll, lr) = f(r.left)
			last = r
			if not head:
				head = r
			(rl, rr) = f(r.right)
			if lr:
				lr.right = r
				r.left = lr
			if rl:
				rl.left = r
				r.right = rl
			if ll and rr:
				return (ll, rr)
			elif ll:
				return (ll, r)
			elif rr:
				return (r, rr)
			else:
				return (r, r)
		f(root)
		head.left = last
		last.right = head
		return head


class Solution:

	def __init__(self):
		self.prev = None
		self.head = None

	def dll(self, root):
		if not root:
			return
		self.dll(root.left)
		if self.prev == None:
			self.head = root
		else:
			root.left = self.prev
			self.prev.right = root
		self.prev = root
		self.dll(root.right)

	def bTreeToClist(self, root):
		self.dll(root)
		self.prev.right = self.head
		self.head.left = self.prev
		return self.head


class Solution:

	def bTreeToClist(self, root):
		head = [None]
		prev = [None]

		def traverse(root, head, prev):
			if not root:
				return
			traverse(root.left, head, prev)
			if not head[0]:
				head[0] = root
				prev[0] = root
			else:
				prev[0].right = root
				root.left = prev[0]
				prev[0] = root
			traverse(root.right, head, prev)
		traverse(root, head, prev)
		prev[0].right = head[0]
		head[0].left = prev[0]
		return head[0]


class Solution:

	def bTreeToClist(self, root):
		if root == None:
			return
		flag = [0]
		head = Node(0)
		lis = deque()
		Solution().rec(root, head, flag, lis)
		head = Node(0)
		point = head
		head.data = lis[0]
		lis.popleft()
		while lis:
			no = Node(lis[0])
			lis.popleft()
			point.right = no
			no.left = point
			if point.right != None:
				point = point.right
		head.left = point
		point.right = head
		return head

	def rec(self, root, head, flag, lis):
		if root == None:
			return
		Solution().rec(root.left, head, flag, lis)
		if flag[0] == 0:
			head.data = root.data
			lis.append(head.data)
			head.left = None
			flag.append(head)
			flag[0] = 1
		else:
			point = Node(root.data)
			lis.append(point.data)
			head.right = point
			point.left = head
			head = head.right
		if root.right != None:
			Solution().rec(root.right, head, flag, lis)
		return head


class Solution:

	def bTreeToClist(self, root):
		res = self.Inorder(root)
		if len(res) == 1:
			res[0].left = None
			return res[0]
		for i in range(len(res) - 1):
			node = res[i]
			next_node = res[i + 1]
			if node is not None:
				if i == 0:
					node.left = None
					node.right = next_node
				else:
					prev_node = res[i - 1]
					node.left = prev_node
					node.right = next_node
		prev_node = node
		node = node.right
		node.left = prev_node
		node.right = res[0]
		res[0].left = node
		return res[0]

	def Inorder(self, root):
		res = []
		self._inorder(root, res)
		return res

	def _inorder(self, root, res):
		if not root:
			return
		self._inorder(root.left, res)
		res.append(root)
		self._inorder(root.right, res)


class Solution:

	def bTreeToClist(self, root):
		(prev, head) = (None, None)

		def solve(root):
			nonlocal prev
			nonlocal head
			if not root:
				return None
			solve(root.left)
			if not prev:
				head = root
			else:
				root.left = prev
				prev.right = root
			prev = root
			solve(root.right)
		solve(root)
		head.left = prev
		prev.right = head
		return head


class Solution:

	def bTreeToClist(self, root):
		l = []

		def inorder(node):
			if not node:
				return
			inorder(node.left)
			l.append(node)
			inorder(node.right)
		inorder(root)
		head = l[0]
		for i in range(len(l) - 1):
			l[i].right = l[i + 1]
			l[i + 1].left = l[i]
			l[i].left = l[i - 1]
			l[i - 1].right = l[i]
		return head


class Solution:

	def bTreeToClist(self, root):
		nodes = []

		def inorder(root):
			if not root:
				return
			inorder(root.left)
			nodes.append(root)
			inorder(root.right)
		inorder(root)
		dummy = Node(-1)
		curr = dummy
		for node in nodes:
			curr.right = node
			node.left = curr
			curr = curr.right
		start = dummy.right
		start.left = curr
		curr.right = start
		return start