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 traversal (leftmost node in BT) must be the head node of the DLL.
Note: H is the height of the tree and this space is used implicitly for the recursion stack.
 
Example 1:
Input:
      1
    /  \
   3    2
Output:
3 1 2 
2 1 3 
Explanation: DLL would be 3<=>1<=>2
Example 2:
Input:
       10
      /   \
     20   30
   /   \
  40   60
Output:
40 20 60 10 30 
30 10 60 20 40
Explanation:  DLL would be 
40<=>20<=>60<=>10<=>30.
Your Task:
You don't have to take input. Complete the function bToDLL() that takes root node of the tree as a parameter and returns the head of DLL . The driver code prints the DLL both ways.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(H).
Constraints:
1 ≤ Number of nodes ≤ 10^{5}
0 ≤ Data of a node ≤ 10^{5}

Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(H).

Starter code:
#User function Template for python3



'''

class Node:

    """ Class Node """

    def __init__(self, value):

        self.left = None

        self.data = value

        self.right = None

'''



#Function to convert a binary tree to doubly linked list.

class Solution:

    def bToDLL(self,root):

        # do Code here



Solutions:
class Solution:

	def _solve(self, node):
		if not node:
			return None
		left = self._solve(node.left)
		right = self._solve(node.right)
		if left:
			while left.right:
				left = left.right
			left.right = node
			node.left = left
		if right:
			while right.left:
				right = right.left
			right.left = node
			node.right = right
		while node.right:
			node = node.right
		return node

	def bToDLL(self, root):
		if not root:
			return None
		head = self._solve(root)
		while head.left:
			head = head.left
		return head


class Solution:

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

	def bToDLL(self, root):

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


class Solution:

	def bToDLL(self, root):

		def BTToDLLUtil(root):
			if root is None:
				return root
			if root.left:
				left = BTToDLLUtil(root.left)
				while left.right:
					left = left.right
				left.right = root
				root.left = left
			if root.right:
				right = BTToDLLUtil(root.right)
				while right.left:
					right = right.left
				right.left = root
				root.right = right
			return root
		if root is None:
			return root
		root = BTToDLLUtil(root)
		while root.left:
			root = root.left
		return root


class Solution:
	head = None
	prev = None

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


class Solution:

	def bToDLL(self, root: 'Node') -> 'Node':
		count = [0]
		preorder_list = self.preorder(root, count)
		prev = None
		head = Node(-1)
		finale = None
		for i in range(count[0]):
			newNode = Node(-1)
			if prev is not None:
				prev.right = newNode
			else:
				finale = newNode
			newNode.data = preorder_list[i]
			newNode.left = prev
			prev = newNode
		return finale

	def preorder(self, root, count):
		newNode = []
		if root is None:
			pass
		else:
			count[0] += 1
			newNode += self.preorder(root.left, count)
			newNode.append(root.data)
			newNode += self.preorder(root.right, count)
		return newNode


class Solution:

	def bToDLL(self, root):
		self.prev = None

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


class Solution:

	def bToDLL(self, root):
		if root is None:
			return
		stack = []
		head = None
		ptr = None
		current = root
		while current or stack:
			while current:
				stack.append(current)
				current = current.left
			current = stack.pop()
			newNode = Node(current.data)
			if head is None:
				ptr = newNode
				head = ptr
			else:
				ptr.right = newNode
				newNode.left = ptr
				ptr = ptr.right
			current = current.right
		return head


class Node:

	def __init__(self, value):
		self.left = None
		self.data = value
		self.right = None

class Solution:

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

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


def fixPrevPtr(root):
	if root is not None:
		fixPrevPtr(root.left)
		root.left = fixPrevPtr.pre
		fixPrevPtr.pre = root
		fixPrevPtr(root.right)

def fixNextPtr(root):
	prev = None
	while root and root.right != None:
		root = root.right
	while root and root.left != None:
		prev = root
		root = root.left
		root.right = prev
	return root

class Solution:

	def bToDLL(self, root):
		fixPrevPtr.pre = None
		fixPrevPtr(root)
		return fixNextPtr(root)


class Solution:

	def bToDLL(self, root):
		if root is None:
			return root
		node = self.recurse(root)
		while node.left:
			node = node.left
		return node

	def recurse(self, node):
		if node is None:
			return node
		if node.left:
			left = self.recurse(node.left)
			while left.right:
				left = left.right
			left.right = node
			node.left = left
		if node.right:
			right = self.recurse(node.right)
			while right.left:
				right = right.left
			right.left = node
			node.right = right
		return node


class Solution:

	def bToDLL(self, root):
		arr = []

		def find(root, arr):
			if root:
				find(root.left, arr)
				arr.append(root.data)
				find(root.right, arr)
			return
		find(root, arr)
		head = Node(arr[0])
		temp = head
		for i in range(1, len(arr)):
			el = Node(arr[i])
			temp.right = el
			el.left = temp
			temp = temp.right
		return head


class Solution:

	def bToDLL(self, root):
		inor = []

		def tt(rt):
			if rt is None:
				return False
			tt(rt.left)
			inor.append(rt.data)
			tt(rt.right)
		tt(root)
		head = Node(inor[0])
		tmp = head
		for i in range(1, len(inor)):
			node = Node(inor[i])
			tmp.right = node
			node.left = tmp
			tmp = node
		return head


class Solution:

	def DLL(self, root):
		if root == None:
			return
		global head_ref
		global prev
		self.DLL(root.left)
		if head_ref == None:
			head_ref = root
		else:
			root.left = prev
			prev.right = root
		prev = root
		self.DLL(root.right)

	def bToDLL(self, root):
		global head_ref
		global prev
		(head_ref, prev) = (None, None)
		self.DLL(root)
		return head_ref


class Solution:

	def bToDLL(self, root):
		if root == None:
			return root
		l = self.bToDLL(root.left)
		r = self.bToDLL(root.right)
		if l != None:
			ltemp = l
			while ltemp.right != None:
				ltemp = ltemp.right
			ltemp.right = root
			root.left = ltemp
			if r != None:
				temp = r
				root.right = r
				r.left = root
				while temp.right != None:
					temp = temp.right
				temp.right = None
			else:
				root.right = None
			return l
		else:
			if r != None:
				temp = r
				root.right = r
				r.left = root
				while temp.right != None:
					temp = temp.right
				temp.right = None
			else:
				root.right = None
				root.left = None
			return root


class Solution:

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

	def __init__(self):
		self.prev = None


class Solution:
	h = None
	p = None

	def bToDLL(self, r):
		if not r:
			return
		self.bToDLL(r.left)
		if self.p == None:
			self.h = r
		else:
			self.p.right = r
			r.left = self.p
		self.p = r
		self.bToDLL(r.right)
		return self.h


class Solution:

	def rec_sol(self, root):
		if root.left == None and root.right == None:
			return (root, root)
		start = root
		end = root
		if root.left != None:
			(start_l, end_l) = self.rec_sol(root.left)
			end_l.right = start
			start.left = end_l
			start = start_l
		if root.right != None:
			(start_r, end_r) = self.rec_sol(root.right)
			end.right = start_r
			start_r.left = end
			end = end_r
		return (start, end)

	def bToDLL(self, root):
		(strt, en) = self.rec_sol(root)
		return strt


class Solution:

	def inorder(self, root, arr):
		if root is not None:
			self.inorder(root.left, arr)
			arr.append(root.data)
			self.inorder(root.right, arr)

	def bToDLL(self, root):
		arr = []
		self.inorder(root, arr)
		head = None
		tail = None
		arr.append('x')
		for i in arr:
			if i != 'x':
				a = Node(i)
				if head is None:
					head = a
					tail = a
				else:
					tail.right = a
					a.left = tail
					tail = tail.right
		return head


class Solution:

	def solve(self, root):
		if root is None:
			return
		self.solve(root.left)
		if self.flag == 0:
			self.flag = 1
			self.head = root
			self.prev = root
		else:
			self.prev.right = root
			self.prev.right.left = self.prev
			self.prev = self.prev.right
		self.solve(root.right)

	def bToDLL(self, root):
		if root is None:
			return
		self.head = None
		self.prev = None
		self.flag = 0
		self.solve(root)
		return self.head


class Solution:

	def bToDLL(self, root):

		def find(root, head, tail):
			if root is None:
				return
			find(root.left, head, tail)
			if head[0] == None:
				head[0] = root
			root.left = tail[0]
			if tail[0] != None:
				tail[0].right = root
			tail[0] = root
			find(root.right, head, tail)
		head = [None]
		tail = [None]
		find(root, head, tail)
		return head[0]


class Solution:

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

	def bToDLL(self, root):
		head = [None]
		self.inorder(root, head, [None])
		return head[0]


class Solution:

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

	def bToDLL(self, root):
		l = []
		self.inorder(l, root)
		head = Node(l[0])
		prev = head
		for i in range(1, len(l)):
			temp = Node(l[i])
			prev.right = temp
			temp.left = prev
			prev = temp
		return head


class Solution:
	final = None
	temp = None

	def bToDLL(self, root):
		if root:
			self.bToDLL(root.left)
			if self.final == None:
				self.final = Node(root.data)
				self.temp = self.final
			else:
				curr = self.temp
				self.temp.right = Node(root.data)
				self.temp = self.temp.right
				self.temp.left = curr
			self.bToDLL(root.right)
		return self.final


class Solution:

	def bToDLL(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)
		return a


class Solution:

	def bToDLL(self, root):
		head = None
		curr = head
		prev = None
		stack = []
		while stack or root:
			if root:
				stack.append(root)
				root = root.left
			else:
				t = stack.pop()
				if not head:
					head = Node(t.data)
					curr = head
				else:
					new_node = Node(t.data)
					curr.right = new_node
					new_node.left = curr
					curr = curr.right
				root = t.right
		curr = head
		while curr:
			curr = curr.right
		return head


class Solution:

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

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

	def bToDLL(self, root):
		if not root:
			return None
		self.bToDLL(root.left)
		self.insert(root)
		self.bToDLL(root.right)
		return self.head

	def solve(self, root):
		if not root:
			return
		self.solve(root.left)
		if self.flag == 0:
			self.flag = 1
			(self.prev, self.head) = (root, root)
		else:
			self.prev.right = root
			self.prev.right.left = self.prev
			self.prev = self.prev.right
		self.solve(root.right)


class Solution:

	def __init__(self):
		self.head = None

	def insert(self, root):
		if not self.head:
			self.head = Node(root)
		else:
			head = self.head
			while head.right:
				head = head.right
			head.right = Node(root)
			head.right.left = head

	def bToDLL(self, root):
		if root is None:
			return None
		if root.left:
			leftHead = self.bToDLL(root.left)
			while leftHead.right:
				leftHead = leftHead.right
			leftHead.right = root
			root.left = leftHead
		if root.right:
			rightHead = self.bToDLL(root.right)
			while rightHead.left:
				rightHead = rightHead.left
			rightHead.left = root
			root.right = rightHead
		current = root
		while current.left:
			current = current.left
		return current


class Solution:

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

	def bToDLL(self, root):
		if root:
			self.bToDLL(root.left)
			t = Node(root.data)
			if self.p is None:
				self.p = t
				self.head = t
				t.left = None
				t.right = None
			else:
				self.p.right = t
				t.left = self.p
				t.right = None
				self.p = t
			self.bToDLL(root.right)
		return self.head


class Solution:

	def bToDLL(self, root):

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


class Solution:

	def bToDLL(self, root):
		self.head = None
		self.prev = None

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


class Solution:

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

	def bToDLL(self, root):
		a = self.inorder(root)
		head = None
		last = None
		for i in a:
			newnode = Node(i)
			if head == None:
				head = newnode
			if last is not None:
				last.right = newnode
				newnode.left = last
				newnode.right = None
			last = newnode
		return head

	def inorder(self, root):
		li = []
		if root is None:
			return li
		li.extend(self.inorder(root.left))
		li.append(root.data)
		li.extend(self.inorder(root.right))
		return li


class Solution:

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

	def bToDLL(self, root):
		self.inorder(root)
		head = None
		last = None
		for i in self.li[:]:
			if i is None:
				self.li.remove(i)
				continue
			newnode = Node(i)
			if head is None:
				head = newnode
			if last is not None:
				last.right = newnode
				newnode.left = last
			last = newnode
		return head

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


class Solution:

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

	def bToDLL(self, root):
		arr = []
		self.inorder(root, arr)
		if not arr:
			return None
		head = Node(arr[0])
		prev_node = head
		for i in range(1, len(arr)):
			new_node = Node(arr[i])
			prev_node.right = new_node
			new_node.left = prev_node
			prev_node = new_node
		return head


class Solution:

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

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


class Solution:

	def bToDLL(self, root):

		def inorder(root, a):
			if root != None:
				inorder(root.left, a)
				a.append(root.data)
				inorder(root.right, a)
		a = []
		inorder(root, a)
		p = Node(0)
		head = p
		for i in range(len(a)):
			node = Node(a[i])
			node.left = p
			p.right = node
			p = p.right
		node.right = None
		head = head.right
		head.left = None
		return head


class Solution:

	def bToDLL(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 a:
			k = Node(i)
			n.right = k
			k.left = n
			n = n.right
		p = p.right
		p.left = None
		return p


class Solution:

	def __init__(self):
		self.prev = None

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

	def bToDLL(self, root):
		self.prev = None
		curr = self.convert(root)
		return curr


class Solution:

	def ino(self, root, l):
		if root:
			self.ino(root.left, l)
			l.append(root.data)
			self.ino(root.right, l)

	def bToDLL(self, root):
		l = []
		self.ino(root, l)
		head = Node(l[0])
		h = head
		for i in range(1, len(l)):
			ne = Node(l[i])
			ne.left = h
			h.right = ne
			h = h.right
		return head


class Solution:

	def preorder(self, root):
		ans = []
		if root.left:
			ans.extend(self.preorder(root.left))
		ans.append(root.data)
		if root.right:
			ans.extend(self.preorder(root.right))
		return ans

	def bToDLL(self, root):
		li = self.preorder(root)
		head = None
		temp = None
		leng = len(li)
		for i in range(leng):
			val = Node(li[i])
			if head == None:
				head = val
				temp = head
			else:
				temp.right = val
				val.left = temp
				temp = val
		return head


class Solution:

	def bToDLL(self, root):

		def convert(node, prev):
			if not node:
				return prev
			prev = convert(node.left, prev)
			if prev:
				prev.right = node
				node.left = prev
			prev = node
			prev = convert(node.right, prev)
			return prev
		head = convert(root, None)
		while head and head.left:
			head = head.left
		return head


class Solution:
	head = None
	previous = None

	def bToDLL(self, root):
		self.switch(root)
		return self.head

	def switch(self, node):
		l = node.left
		r = node.right
		if l:
			self.switch(l)
		if self.previous:
			node.left = self.previous
			self.previous.right = node
			self.previous = node
		if not node.left and (not self.head):
			self.head = node
			self.previous = node
		if r:
			self.switch(r)


class Solution:

	def InOrder(self, root):
		if root == None:
			return []
		else:
			return self.InOrder(root.left) + [root.data] + self.InOrder(root.right)

	def bToDLL(self, root):
		inOrder = self.InOrder(root)
		head = Node(inOrder[0])
		prev = head
		for i in range(1, len(inOrder)):
			curr = Node(inOrder[i])
			curr.left = prev
			prev.right = curr
			prev = curr
		return head


class Solution:

	def bToDLL(self, root):
		self.head = self.tail = None

		def convert(root):
			if root.left:
				convert(root.left)
			if self.tail == None:
				self.head = root
				self.tail = root
			else:
				self.tail.right = root
				root.left = self.tail
				self.tail = root
			if root.right:
				convert(root.right)
		convert(root)
		return self.head


class Solution:

	def __init__(self):
		self.head = None
		self.nodes = []
		self.tail = None

	def add_node(self):
		for item in self.nodes:
			if self.head == None:
				self.head = item
				item.left = None
				item.right = None
				self.tail = item
			else:
				tmp = self.tail
				tmp.right = item
				item.left = tmp
				self.tail = item

	def inorder(self, current):
		if current:
			self.inorder(current.left)
			self.nodes.append(current)
			self.inorder(current.right)

	def bToDLL(self, root):
		self.inorder(root)
		self.add_node()
		return self.head


class Solution:

	def bToDLL(self, root):
		head = [None]
		prev = [None]
		self.binary_tree_dll_util(root, head, prev)
		return head[0]

	def binary_tree_dll_util(self, root, head_arr, prev_arr):
		if root is None:
			return None
		self.binary_tree_dll_util(root.left, head_arr, prev_arr)
		if head_arr[0] is None:
			head_arr[0] = root
			prev_arr[0] = root
		else:
			prev_arr[0].right = root
			root.left = prev_arr[0]
			prev_arr[0] = root
		self.binary_tree_dll_util(root.right, head_arr, prev_arr)


class Solution:

	def bToDLL(self, root):
		result = []

		def inorder(root):
			nonlocal result
			if root == None:
				return
			inorder(root.left)
			result.append(root.data)
			inorder(root.right)
		inorder(root)
		news = DLL()
		head = news
		for i in result:
			curr = DLL(i)
			curr.left = head
			head.right = curr
			curr = curr.right
			head = head.right
		news = news.right
		news.left = None
		return news

class DLL:

	def __init__(self, value=None):
		self.left = None
		self.data = value
		self.right = None


class Solution:

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


class Solution:

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

	def traverse(self, root):
		if root == None:
			return
		self.traverse(root.left)
		self.res.append(root)
		self.traverse(root.right)

	def bToDLL(self, root):
		self.traverse(root)
		head = Node(self.res[0].data)
		head1 = head
		n = len(self.res)
		for i in range(1, n):
			b = Node(self.res[i].data)
			head1.right = b
			b.left = head1
			head1 = head1.right
		return head


class Solution:

	def bToDLL(self, root):
		ob = Solution()
		if root is None:
			return root
		if root.left is not None:
			left_sub = ob.bToDLL(root.left)
			while left_sub.right:
				left_sub = left_sub.right
			left_sub.right = root
			root.left = left_sub
		if root.right:
			right_sub = ob.bToDLL(root.right)
			while right_sub.left:
				right_sub = right_sub.left
			right_sub.left = root
			root.right = right_sub
		while root.left:
			root = root.left
		return root


class Solution:

	def helper(self, root, parent=None):
		if root == None:
			return (None, None)
		(l_h, l_t) = self.helper(root.left)
		(r_h, r_t) = self.helper(root.right)
		if l_t:
			root.left = l_t
			l_t.right = root
		if r_h:
			root.right = r_h
			r_h.left = root
		head = l_h if l_h else root
		tail = r_t if r_t else root
		return (head, tail)

	def bToDLL(self, root):
		return self.helper(root)[0]


class Solution:

	def bToDLL(self, root):
		temp = []

		def traverse(root):
			if root.left:
				traverse(root.left)
			temp.append(root.data)
			if root.right:
				traverse(root.right)
		traverse(root)
		head = Node(temp[0])
		ptr = head
		for i in range(1, len(temp)):
			newnode = Node(temp[i])
			newnode.left = ptr
			ptr.right = newnode
			ptr = newnode
		return head


class Solution:

	def bToDLL(self, root):
		self.head = None
		self.prev = None
		self.curr = None

		def solve(node):
			if not node:
				return
			solve(node.left)
			new = Node(node.data)
			if not self.prev:
				self.prev = new
				self.curr = new
				self.head = new
			else:
				self.prev = self.curr
				self.curr.right = new
				new.left = self.prev
				self.curr = self.curr.right
			solve(node.right)
		solve(root)
		return self.head


class Solution:

	def bToDLL(self, root):

		def dll(root):
			if root == None:
				return [None, None]
			l = dll(root.left)
			r = dll(root.right)
			head = root
			tail = root
			root.left = l[1]
			if l[1] != None:
				l[1].right = root
				head = l[0]
			root.right = r[0]
			if r[0] != None:
				r[0].left = root
				tail = r[1]
			return [head, tail]
		answer = dll(root)
		return answer[0]
		a


class Solution:

	def bToDLL(self, root):

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


class Solution:

	def __init__(self):
		self.node = Node(0)
		self.ret = self.node

	def convert(self, root):
		if not root:
			return
		self.convert(root.left)
		node = Node(root.data)
		node.left = self.node
		self.node.right = node
		self.node = node
		self.convert(root.right)

	def bToDLL(self, root):
		self.convert(root)
		self.ret = self.ret.right
		self.ret.left = None
		return self.ret


class Solution:

	def bToDLL(self, root):
		self.prev = temp = Node(-1)

		def inorderm(node=root):
			if not node:
				return
			inorderm(node.left)
			self.prev.right = node
			node.left = self.prev
			self.prev = node
			inorderm(node.right)
		inorderm()
		temp.right.left = None
		return temp.right


from collections import deque

class Solution:

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

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


class Solution:

	def bToDLL(self, root):
		start = [None]
		head = [None]
		tail = [None]

		def btd(root):
			if root == None:
				return (None, None)
			(lh, lt) = btd(root.left)
			if lt == None and start[0] == None:
				start[0] = root
			if lh == None:
				lh = root
			if lt != None:
				lt.right = root
				root.left = lt
			(rh, rt) = btd(root.right)
			if rh != None:
				root.right = rh
				rh.left = root
			else:
				rt = root
			return (lh, rt)
		btd(root)
		return start[0]


class Solution:

	def bToDLL(self, root):
		inorder = []

		def fun(root):
			if root == None:
				return False
			fun(root.left)
			inorder.append(root.data)
			fun(root.right)
		fun(root)
		new = Node(inorder[0])
		temp = new
		for i in range(1, len(inorder)):
			node = Node(inorder[i])
			new.right = node
			node.left = new
			new = node
		return temp