Given a Binary Tree of size N, extract all its leaf nodes to form a Doubly Link List starting from the left most leaf. Modify the original tree to make the DLL thus removing the leaf nodes from the tree. Consider the left and right pointers of the tree to be the previous and next pointer of the DLL respectively.
Note: The generated output will contain the inorder traversal of the modified tree, the DLL from left to right and the DLL from right to left.
Example 1:
Input :
        1
      /   \
     2     3
    / \   / \
   4   5 6   7    
Output: 
Modified Tree :
        1
      /   \
     2     3
Doubly Link List :
4 <-> 5 <-> 6 <-> 7
Explanation:
The leaf nodes are modified to form the DLL 
in-place. Thus their links are removed from 
the tree.
Example 2:
Input :
        1
      /   \
     2     3
    / \   
   4   5 
Output: 
Modified Tree :
        1
      /   
     2    
Doubly Link List :
4 <-> 5 <-> 3
Your Task:  
You don't need to read input or print anything. Complete the function convertToDLL() which takes the root of the given tree as input parameter and returns the head of the doubly link list.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(height of tree)
Constraints:
1 ≤ N ≤ 10^4

Difficulty: MEDIUM
Tags: Tree algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(height of tree)

Starter code:
#User function Template for python3



'''

# Node Class:

class Node:

    def __init__(self,val):

        self.data = val

        self.left = None

        self.right = None

'''



def convertToDLL(root):

    #return the head of the DLL and remove those node from the tree as well.

Solutions:
def convertToDLL(root):
	leaves = []
	root = leavenode(root, leaves)
	head = None
	tmp = None
	for i in leaves:
		if head is None:
			node = Node(i.data)
			node.left = None
			node.right = None
			head = node
			tmp = head
		else:
			node = Node(i.data)
			node.left = tmp
			tmp.right = node
			tmp = node
	return head

def leavenode(rt, leav):
	if rt is None:
		return None
	if rt.left is None and rt.right is None:
		leav.append(rt)
		return None
	rt.left = leavenode(rt.left, leav)
	rt.right = leavenode(rt.right, leav)
	return rt


def convertToDLL(root):
	elements = [None]

	def preorder(root, parent):
		if not root:
			return
		if not root.left and (not root.right):
			elements.append(root)
			if parent.left == root:
				parent.left = None
			else:
				parent.right = None
			return
		preorder(root.left, root)
		preorder(root.right, root)
	preorder(root, None)
	elements += [None]
	for i in range(1, len(elements) - 1):
		elements[i].left = elements[i - 1]
		elements[i].right = elements[i + 1]
	return elements[1]


def creat(lst, n, start):
	start = Node(lst[0])
	curr_node = start
	for data in lst[1:]:
		new_node = Node(data)
		curr_node.right = new_node
		new_node.left = curr_node
		curr_node = new_node
	return start

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

def remove(root):
	if root == None:
		return
	if root.left:
		if root.left.left == None and root.left.right == None:
			root.left = None
	if root.right:
		if root.right.left == None and root.right.right == None:
			root.right = None
	remove(root.left)
	remove(root.right)

def convertToDLL(root):
	lis = []
	leaf(root, lis)
	start = None
	head = creat(lis, len(lis), start)
	remove(root)
	return head


def util(root, prev, dir):
	global head, temp
	if root == None:
		return
	if root.left == None and root.right == None:
		if dir == 'l':
			prev.left = None
		elif dir == 'r':
			prev.right = None
		if head == None:
			head = root
			temp = head
		else:
			temp.right = root
			root.left = temp
			temp = temp.right
		return
	util(root.left, root, 'l')
	util(root.right, root, 'r')

def convertToDLL(root):
	global head, temp
	head = temp = None
	util(root, root, 'root')
	return head


def convertToDLL(root):

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


def convertToDLL_util(root):
	global head
	if root == None:
		return None
	if root.left == None and root.right == None:
		root.right = head
		if head != None:
			head.left = root
		head = root
		return None
	root.right = convertToDLL_util(root.right)
	root.left = convertToDLL_util(root.left)
	return root

def convertToDLL(root):
	global head
	head = None
	root = convertToDLL_util(root)
	return head


def convertToDLL(root):
	leaves = []
	stack = [root]
	visited = set()
	lVis = set()
	while stack:
		top = stack[-1]
		if top.left and top.left not in visited:
			visited.add(top.left)
			stack.append(top.left)
		elif top.right and top.right not in visited:
			visited.add(top.right)
			stack.append(top.right)
		else:
			pop = stack.pop()
			if not pop.left and (not pop.right):
				leaves.append(pop.data)
				lVis.add(pop)
	stack = [root]
	while stack:
		top = stack.pop()
		if top.left:
			if top.left in lVis:
				top.left = None
			else:
				stack.append(top.left)
		if top.right:
			if top.right in lVis:
				top.right = None
			else:
				stack.append(top.right)
	dll = Node(leaves[0])
	cur = dll
	n = len(leaves)
	for i in range(n - 1):
		newNode = Node(leaves[i + 1])
		cur.right = newNode
		newNode.left = cur
		cur = cur.right
	return dll


def fun(root):
	global head
	if root == None:
		return None
	if root.left == None and root.right == None:
		root.right = head
		if head != None:
			head.left = root
		head = root
		return None
	root.right = fun(root.right)
	root.left = fun(root.left)
	return root

def convertToDLL(root):
	global head
	head = None
	root = fun(root)


def convertToDLL(root):
	head = None
	prev = None
	if not root:
		return None
	return build(root, head, prev)[0]

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


def Postorder(root, node):
	if root == None:
		return 0
	l = Postorder(root.left, node)
	r = Postorder(root.right, node)
	if l == 0 and r == 0:
		node[0].right = root
		root.left = node[0]
		node[0] = node[0].right
		return -1
	if l == -1:
		root.left = None
	if r == -1:
		root.right = None
	return 1

def convertToDLL(root):
	head = Node(-1)
	node = [head]
	Postorder(root, node)
	head = head.right
	head.left = None
	return head


def convertToDLL(root):
	b = []
	bst(root, b)
	head = Node(b[0])
	tmp = head
	b.pop(0)
	for i in b:
		x = Node(i)
		tmp.right = x
		x.left = tmp
		tmp = tmp.right
	return head

def bst(root, b):
	if root.left:
		if root.left.left == None and root.left.right == None:
			b.append(root.left.data)
			root.left = None
		else:
			bst(root.left, b)
	if root.right:
		if root.right.left == None and root.right.right == None:
			b.append(root.right.data)
			root.right = None
		else:
			bst(root.right, b)


def convertToDLL(root):

	def func(root, par, direc, li):
		if root is None:
			return
		if root.left is None and root.right is None:
			li.append(root.data)
			if direc == 0:
				par.left = None
			elif direc == 1:
				par.right = None
			return
		func(root.left, root, 0, li)
		func(root.right, root, 1, li)
	li = []
	func(root, -1, None, li)
	node = Node(li[0])
	dummy = node
	for i in range(1, len(li)):
		ans = Node(li[i])
		node.right = ans
		ans.left = node
		node = node.right
	return dummy


def convertToDLL(root):
	start = Node(0)
	helper(root, start)
	start.right.left = None
	return start.right

def helper(root, head):
	if root is None:
		return head
	if root.left and root.left.left is None and (root.left.right is None):
		leaf = Node(root.left.data)
		leaf.left = head
		head.right = leaf
		head = leaf
		root.left = None
	head = helper(root.left, head)
	if root.right and root.right.left is None and (root.right.right is None):
		leaf = Node(root.right.data)
		leaf.left = head
		head.right = leaf
		head = leaf
		root.right = None
	return helper(root.right, head)


class Solution:

	def __init__(self):
		self.a = None
		self.b = None

	def io(self, a):
		if a == None:
			return
		if a.left == None and a.right == None:
			if self.a == None:
				self.a = Node(a.data)
				self.b = self.a
			else:
				self.b.right = Node(a.data)
				self.b.right.left = self.b
				self.b = self.b.right
			return None
		else:
			o = self.io(a.left)
			p = self.io(a.right)
			a.left = o
			a.right = p
			return a

def convertToDLL(root):
	o = Solution()
	o.io(root)
	return o.a


def helper(node, leaves):
	if not node:
		return
	if not node.left and (not node.right):
		leaves.append(node)
	helper(node.left, leaves)
	helper(node.right, leaves)

def helper1(node, leaves):
	if not node:
		return
	if node.left in leaves:
		node.left = None
	if node.right in leaves:
		node.right = None
	helper1(node.left, leaves)
	helper1(node.right, leaves)

def convertToDLLUtil(leaves):
	(head, temp) = (None, None)
	for i in leaves:
		if not head:
			(head, temp) = (i, i)
		else:
			(i.left, temp.right, temp) = (temp, i, i)
	temp.right = None
	return head

def convertToDLL(root):
	leaves = []
	helper(root, leaves)
	helper1(root, set(leaves))
	return convertToDLLUtil(leaves)


def lo1(root):
	if root is None:
		return
	c = lo1(root.left)
	d = lo1(root.right)
	if root.left is None and root.right is None:
		l.append(root)
		return 1
	if c == 1:
		root.left = None
	if d == 1:
		root.right = None

def convertToDLL(root):
	global l
	l = []
	lo1(root)
	for i in range(len(l) - 1):
		if i == 0:
			l[i].right = l[i + 1]
		else:
			(l[i].left, l[i].right) = (l[i - 1], l[i + 1])
	l[-1].left = l[-2]
	return l[0]


class DLL:

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

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

def isLeaf(root, dll):
	if not root:
		return False
	if not root.left and (not root.right):
		dll.add(root.data)
		return True
	if isLeaf(root.left, dll):
		root.left = None
	if isLeaf(root.right, dll):
		root.right = None

def convertToDLL(root):
	dll = DLL()
	ans = isLeaf(root, dll)
	return dll.head


def convertToDLL(root):
	global a
	a = []

	def sol(root):
		global a
		if root:
			if root.left == None and root.right == None:
				a.append(root.data)
				return None
			root.left = sol(root.left)
			root.right = sol(root.right)
			return root
	sol(root)
	tem = Node(a[0])
	head = tem
	i = 1
	while i < len(a):
		tem.right = Node(a[i])
		k = tem
		tem = tem.right
		tem.left = k
		i = i + 1
	return head


def convertToDLL(root):
	prev = []
	dfs(root, prev)
	head = Node(prev[0])
	head.left = None
	head.right = None
	pre = head
	for i in range(1, len(prev)):
		N = Node(prev[i])
		N.left = pre
		N.right = None
		pre.right = N
		pre = N
	return head

def dfs(root, prev):
	if root and (not root.left) and (not root.right):
		prev.append(root.data)
		return None
	elif root:
		root.left = dfs(root.left, prev)
		root.right = dfs(root.right, prev)
		return root


def is_leaf(node):
	return node.right is None and node.left is None

def rec_ctd(root, aux_dict):
	if root is None:
		return
	if is_leaf(root):
		aux_dict.append(root)
	if root.left:
		if is_leaf(root.left):
			aux_dict.append(root.left.data)
			root.left = None
		else:
			rec_ctd(root.left, aux_dict)
	if root.right:
		if is_leaf(root.right):
			aux_dict.append(root.right.data)
			root.right = None
		else:
			rec_ctd(root.right, aux_dict)

def convertToDLL(root):
	if root is None:
		return None
	aux_dict = []
	rec_ctd(root, aux_dict)
	first = True
	curr = None
	prev = None
	head = None
	for val in aux_dict:
		if first:
			curr = Node(val)
			curr.left = None
			curr.right = None
			head = curr
			first = False
		else:
			curr.right = Node(val)
			prev = curr
			curr = curr.right
			curr.left = prev
			curr.right = None
	return head


class DLL:

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

	def getHead(self):
		return self.head

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

def isLeaf(root):
	if not root.left and (not root.right):
		return True
	return False

def cutLeaves(root, ll):
	if isLeaf(root):
		print(root.data)
		return root.data
	else:
		if root.left:
			if isLeaf(root.left):
				ll.append(root.left.data)
				root.left = None
			else:
				cutLeaves(root.left, ll)
		if root.right:
			if isLeaf(root.right):
				ll.append(root.right.data)
				root.right = None
			else:
				cutLeaves(root.right, ll)

def convertToDLL(root):
	dll = DLL()
	cutLeaves(root, dll)
	return dll.getHead()


def convertToDLL(root):
	leaves = [None]

	def leafextract(root):
		if root.left == None and root.right == None:
			leaves.append(root)
			return 1
		if root.left:
			if leafextract(root.left):
				root.left = None
		if root.right:
			if leafextract(root.right):
				root.right = None
		return 0
	leafextract(root)
	leaves.append(None)
	for i in range(1, len(leaves) - 1):
		leaves[i].left = leaves[i - 1]
		leaves[i].right = leaves[i + 1]
	return leaves[1]
	return None


def is_leaf(node):
	return node.right is None and node.left is None

def tree(root, l):
	if root == None:
		return
	if is_leaf(root):
		l.append(root)
	if root.left:
		if is_leaf(root.left):
			l.append(root.left.data)
			root.left = None
		else:
			tree(root.left, l)
	if root.right:
		if is_leaf(root.right):
			l.append(root.right.data)
			root.right = None
		else:
			tree(root.right, l)

def convertToDLL(root):
	if root == None:
		return None
	l = []
	tree(root, l)
	first = True
	curr = None
	prev = None
	head = None
	for i in l:
		if first:
			curr = Node(i)
			curr.left = None
			curr.right = None
			head = curr
			first = False
		else:
			curr.right = Node(i)
			prev = curr
			curr = curr.right
			curr.left = prev
			curr.right = None
	return head


def convertToDLL(root):

	def is_leaf(node):
		return node and (not node.left) and (not node.right)
	if is_leaf(root):
		return root
	(head, prev) = ([], [])

	def add_node(node):
		if not head:
			head.append(node)
			prev.append(node)
		else:
			prev[0].right = node
			node.left = prev[0]
			prev[0] = node

	def rec(root):
		if not root:
			return
		if is_leaf(root.left):
			add_node(root.left)
			root.left = None
		else:
			rec(root.left)
		if is_leaf(root.right):
			add_node(root.right)
			root.right = None
		else:
			rec(root.right)
	rec(root)
	return head[0]


def convertToDLL(root):
	leafs = []

	def is_leaf(node):
		return node and (not node.left) and (not node.right)
	if is_leaf(root):
		return root

	def rec(root):
		if not root:
			return
		if is_leaf(root.left):
			leafs.append(root.left)
			root.left = None
		else:
			rec(root.left)
		if is_leaf(root.right):
			leafs.append(root.right)
			root.right = None
		else:
			rec(root.right)
	rec(root)
	for i in range(1, len(leafs)):
		leafs[i - 1].right = leafs[i]
		leafs[i].left = leafs[i - 1]
	return leafs[0]


def update_tree_and_get_leafnode(root, leafnodes):
	if root == None:
		return None
	if root.left is None and root.right is None:
		leafnodes.append(root.data)
		return None
	root.left = update_tree_and_get_leafnode(root.left, leafnodes)
	root.right = update_tree_and_get_leafnode(root.right, leafnodes)
	return root

def getdll(leafnodes):
	head = None
	tail = None
	for i in leafnodes:
		newnode = Node(i)
		if head is None:
			head = newnode
			tail = newnode
			head.right = None
			head.left = None
		else:
			tail.right = newnode
			newnode.left = tail
		tail = newnode
	return head

def convertToDLL(root):
	leafnodes = []
	update_tree_and_get_leafnode(root, leafnodes)
	return getdll(leafnodes)


def convertToDLL(root):
	mem = {'head': None, 'tail': None}

	def leaf(root):
		if root.left or root.right:
			if root.left:
				if leaf(root.left):
					root.left = None
			if root.right:
				if leaf(root.right):
					root.right = None
			return 0
		else:
			if mem['head'] is None:
				mem['head'] = mem['tail'] = root
			else:
				mem['tail'].right = root
				root.left = mem['tail']
				mem['tail'] = mem['tail'].right
			return 1
	leaf(root)
	return mem['head']


def convertToDLL(root):

	def convert(root, dll):
		if not root:
			return (dll, None)
		if not root.left and (not root.right):
			dll.right = root
			root.left = dll
			dll = root
			return (dll, None)
		(ld, root.left) = convert(root.left, dll)
		(rd, root.right) = convert(root.right, ld)
		return (rd, root)
	temp = Node(0)
	convert(root, temp)
	ans = temp.right
	ans.left = None
	return ans


def convertToDLL(root):

	def conver(root, dll):
		if not root:
			return (dll, None)
		if not root.left and (not root.right):
			root.left = dll
			dll.right = root
			dll = root
			return (dll, None)
		(ld, root.left) = conver(root.left, dll)
		(rd, root.right) = conver(root.right, ld)
		return (rd, root)
	ans = Node(0)
	pointer1 = ans
	conver(root, pointer1)
	r = ans.right
	r.left = None
	ans = None
	return r


def convertToDLL(root):
	lst = []

	def traverse(root):
		nonlocal lst
		if root == None:
			return None
		if root.left == None and root.right == None:
			lst.append(root.data)
			return None
		root.left = traverse(root.left)
		root.right = traverse(root.right)
		return root
	traverse(root)
	head = Node(-1)
	temp = head
	while lst:
		newnode = Node(lst.pop(0))
		temp.right = newnode
		newnode.left = temp
		temp = temp.right
	head = head.right
	head.left = None
	return head


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

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


def convertToDLL(root):
	head = prev = None

	def f(r):
		if not r:
			return
		if not r.left and (not r.right):
			nonlocal prev, head
			if not prev:
				head = r
				prev = r
			else:
				prev.right = r
				r.left = prev
				prev = r
			return
		else:
			r.left = f(r.left)
			r.right = f(r.right)
			return r
	f(root)
	return head


def convertToDLL(root):
	nodes = []

	def tree(root):
		if root == None:
			return root
		if root.left == None and root.right == None:
			nodes.append(root)
			return None
		root.left = tree(root.left)
		root.right = tree(root.right)
		return root
	tree(root)
	for i in range(len(nodes) - 1):
		if i == 0:
			curr = nodes[i]
			next = nodes[i + 1]
			curr.right = next
			next.left = curr
		else:
			prev = nodes[i - 1]
			curr = nodes[i]
			next = nodes[i + 1]
			curr.right = next
			next.left = curr
			curr.left = prev
	return nodes[0]


def convertToDLL(root):
	global prev
	global head
	if not root.left and (not root.right):
		return root
	prev = None
	head = None

	def traverse(node, par):
		global prev
		global head
		if not node:
			return
		if not node.left and (not node.right):
			if node == par.left:
				par.left = None
			else:
				par.right = None
			if not prev:
				head = node
				prev = node
			else:
				prev.right = node
				node.left = prev
				prev = node
			return
		traverse(node.left, node)
		traverse(node.right, node)
	traverse(root, None)
	return head


def convertToDLL(root):
	notLeaves = set()

	def isLeaves(root):
		if not root.left and (not root.right) and (root not in notLeaves):
			return True
		return False

	def addToDDL(node):
		nonlocal cur
		cur.right = node
		node.left = cur
		cur = cur.right
	dummy = Node(-1)
	cur = dummy

	def dfs(root):
		nonlocal cur
		if not root:
			return
		dfs(root.left)
		if root.left and isLeaves(root.left):
			node = root.left
			root.left = None
			addToDDL(node)
			notLeaves.add(root)
		if root.right and isLeaves(root.right):
			node = root.right
			root.right = None
			addToDDL(node)
			notLeaves.add(root)
		dfs(root.right)
	dfs(root)
	res = dummy.right
	dummy.right = None
	res.left = None
	return res


def convertToDLL(root):

	def with_space():
		leaves = []

		def get_leaves(root, parent):
			if root:
				get_leaves(root.left, root)
				if root.left is None and root.right is None:
					if parent:
						if parent.left == root:
							parent.left = None
						else:
							parent.right = None
					leaves.append(root.data)
					return
				get_leaves(root.right, root)
			return

		def build_dll(leaves):
			prev = None
			head = None
			for leaf in leaves:
				node = Node(leaf)
				if prev is None:
					head = node
				node.left = prev
				if prev is not None:
					prev.right = node
				prev = node
			return head
		get_leaves(root, None)
		return build_dll(leaves)

	def without_space():
		prev = None
		head = None

		def get_leaves(root, parent):
			if root:
				nonlocal prev
				nonlocal head
				if root.left is None and root.right is None:
					if parent:
						if parent.left == root:
							parent.left = None
						else:
							parent.right = None
					if prev is None:
						head = root
					root.left = prev
					if prev is not None:
						prev.right = root
					prev = root
					return
				get_leaves(root.left, root)
				get_leaves(root.right, root)
			return
		get_leaves(root, None)
		return head
	return without_space()


def convertToDLL(root):
	leaf = []
	tree(root, leaf)
	return getdll(leaf)

def getdll(leaf):
	head = None
	tail = None
	for i in leaf:
		newnode = Node(i)
		if head is None:
			head = newnode
			tail = newnode
			head.right = None
			head.left = None
		else:
			tail.right = newnode
			newnode.left = tail
		tail = newnode
	return head

def tree(root, leaf):
	if root == None:
		return None
	if root.left == None and root.right == None:
		leaf.append(root.data)
		return None
	root.left = tree(root.left, leaf)
	root.right = tree(root.right, leaf)
	return root


def convertToDLL(root):

	def getLeafNodes(root, arr, parent, left=True):
		if not root:
			return
		if not root.left and (not root.right):
			if left:
				parent.left = None
			else:
				parent.right = None
			arr.append(root)
		getLeafNodes(root.left, arr, root, True)
		getLeafNodes(root.right, arr, root, False)

	def dll(arr):
		ans = root = Node(arr[0].data)
		for i in range(1, len(arr)):
			root.right = arr[i]
			root = root.right
			root.left = arr[i - 1]
		return ans
	arr = []
	getLeafNodes(root, arr, root)
	return dll(arr)


def convertToDLL(root):
	arr = []

	def solve(root):
		if root is None:
			return None
		if root.left is None and root.right is None:
			arr.append(root.data)
			return None
		root.left = solve(root.left)
		root.right = solve(root.right)
		return root
	solve(root)
	head = None
	prev = None
	for i in arr:
		if head is None:
			head = Node(i)
			prev = head
			tmp = head
		else:
			tmp.right = Node(i)
			tmp.right.left = tmp
			tmp = tmp.right
	return head


def remove_leaf(root):
	if not root:
		return None
	global head, itr
	if not root.left and (not root.right):
		if head is None:
			head = root
			itr = head
		else:
			itr.right = root
			root.left = itr
			itr = itr.right
		return None
	root.left = remove_leaf(root.left)
	root.right = remove_leaf(root.right)
	return root

def convertToDLL(root):
	global head, itr
	head = None
	remove_leaf(root)
	return head


def remove_leaf(root, arr):
	if not root:
		return None
	if not root.left and (not root.right):
		arr.append(root)
		return None
	root.left = remove_leaf(root.left, arr)
	root.right = remove_leaf(root.right, arr)
	return root

def convertToDLL(root):
	leafs = []
	remove_leaf(root, leafs)
	head = leafs.pop(0)
	head.left = None
	pre = head
	itr = leafs.pop(0)
	for _ in range(len(leafs)):
		pre.right = itr
		itr.left = pre
		pre = itr
		itr = leafs.pop(0)
	pre.right = itr
	itr.left = pre
	return head


class dl:

	def __init__(self, val):
		self.data = val
		self.prev = None
		self.next = None

def convertToDLL(root):
	global head
	head = None
	check(root)
	return head

def check(root):
	global head
	if root is None:
		return None
	if root.left is None and root.right is None:
		root.right = head
		if head != None:
			head.left = root
		head = root
		return None
	root.right = check(root.right)
	root.left = check(root.left)
	return root


def ino(root, l, p):
	if root is None:
		return
	ino(root.left, l, root)
	l.append([root, p, 0, 0])
	ino(root.right, l, root)

def convertToDLL(root):
	b = []
	ino(root, b, None)
	l = []
	n = len(b)
	for i in range(n):
		if b[i][0].left is None and b[i][0].right is None:
			l.append(Node(b[i][0].data))
			if b[i][1]:
				if b[i][1].right == b[i][0]:
					b[i][3] = 1
				if b[i][1].left == b[i][0]:
					b[i][2] = 1
	for i in b:
		if i[2] == 1:
			i[1].left = None
		if i[3] == 1:
			i[1].right = None
	if len(l) == 1:
		return l[0]
	if len(l) == 2:
		l[0].right = l[1]
		l[1].left = l[0]
		return l[0]
	n = len(l)
	for i in range(1, n - 1):
		l[i - 1].right = l[i]
		l[i].left = l[i - 1]
		l[i].right = l[i + 1]
		l[i + 1].left = l[i]
	return l[0]


def recur(root):
	global headref, tailref
	if not root:
		return
	if not root.left and (not root.right):
		if headref:
			tailref.right = root
			root.left = tailref
			tailref = tailref.right
		else:
			headref = root
			tailref = root
		return None
	root.left = recur(root.left)
	root.right = recur(root.right)
	return root

def convertToDLL(root):
	global headref, tailref
	headref = None
	tailref = None
	recur(root)
	return headref


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

def helper(li):
	head = None
	tail = None
	for ele in li:
		new_node = Node(ele)
		if head is None:
			head = new_node
			head.right = None
			head.left = None
		else:
			tail.right = new_node
			new_node.left = tail
		tail = new_node
	return head

def convertToDLL(root):
	li = []
	leaf_Node_Finder(root, li)
	return helper(li)


def convertToDLL(root):
	(head, curr) = ([None], [None])
	res = solve(root, head, curr)
	if res:
		root = None
	return head[0]

def solve(root, head, curr):
	if not root:
		return 0
	if not root.left and (not root.right):
		if curr[0]:
			curr[0].right = root
			root.left = curr[0]
		curr[0] = root
		if not head[0]:
			head[0] = curr[0]
		return 1
	left_res = solve(root.left, head, curr)
	if left_res:
		root.left = None
	right_res = solve(root.right, head, curr)
	if right_res:
		root.right = None
	return 0


def convertToDLL(root):
	if not root:
		return
	leaves = []
	getLeaves(root, leaves)
	dll_head = Node(leaves[0])
	cur = dll_head
	for i in range(1, len(leaves)):
		new = Node(leaves[i])
		new.left = cur
		cur.right = new
		cur = cur.right
	return dll_head

def getLeaves(root, leaves):
	if not root:
		return
	if not root.left and (not root.right):
		leaves.append(root.data)
		return None
	root.left = getLeaves(root.left, leaves)
	root.right = getLeaves(root.right, leaves)
	return root


def convertToDLL(root):

	def _toDLL(lst):
		for i in range(len(lst) - 1):
			lst[i].right = lst[i + 1]
			lst[i + 1].left = lst[i]
		return lst[0]

	def _isleaf(nd):
		return nd and nd.left is None and (nd.right is None)

	def _extract_leaves(nd, lst):
		if not nd:
			return
		if _isleaf(nd.left):
			lst.append(nd.left)
			nd.left = None
		else:
			_extract_leaves(nd.left, lst)
		if _isleaf(nd.right):
			lst.append(nd.right)
			nd.right = None
		else:
			_extract_leaves(nd.right, lst)
	if _isleaf(root):
		return root
	lst = []
	_extract_leaves(root, lst)
	head = _toDLL(lst)
	return head
from collections import deque

class Node:

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

def inOrder(root):
	if root is None:
		return
	inOrder(root.left)
	print(root.data, end=' ')
	inOrder(root.right)

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		head = convertToDLL(root)
		inOrder(root)
		print()
		temp = head
		last = None
		while temp != None:
			print(temp.data, end=' ')
			last = temp
			temp = temp.right
		print()
		temp = last
		while temp != None:
			print(temp.data, end=' ')
			temp = temp.left
		print()


def convertToDLL(root):

	def dfs(root):
		nonlocal lst
		if not root:
			return None
		if not root.left and (not root.right):
			lst.append(root.data)
			return None
		root.left = dfs(root.left)
		root.right = dfs(root.right)
		return root
	lst = []
	dfs(root)
	curr = None
	flag = True
	Prev = None
	head = None
	for node in lst:
		if flag:
			head = Node(node)
			curr = head
			curr.next = None
			flag = False
		else:
			curr.right = Node(node)
			Prev = curr
			curr = curr.right
			curr.left = Prev
	return head
from collections import deque

class Node:

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

def inOrder(root):
	if root is None:
		return
	inOrder(root.left)
	print(root.data, end=' ')
	inOrder(root.right)

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		head = convertToDLL(root)
		inOrder(root)
		print()
		temp = head
		last = None
		while temp != None:
			print(temp.data, end=' ')
			last = temp
			temp = temp.right
		print()
		temp = last
		while temp != None:
			print(temp.data, end=' ')
			temp = temp.left
		print()


def is_leaf(node):
	return node.right is None and node.left is None

def rec_ctd(root, aux_dict):
	if root is None:
		return
	if is_leaf(root):
		aux_dict.append(root)
	if root.left:
		if is_leaf(root.left):
			aux_dict.append(root.left.data)
			root.left = None
		else:
			rec_ctd(root.left, aux_dict)
	if root.right:
		if is_leaf(root.right):
			aux_dict.append(root.right.data)
			root.right = None
		else:
			rec_ctd(root.right, aux_dict)

def convertToDLL(root):
	if root is None:
		return None
	aux_dict = []
	rec_ctd(root, aux_dict)
	first = True
	curr = None
	prev = None
	head = None
	for val in aux_dict:
		if first:
			curr = Node(val)
			head = curr
			first = False
		else:
			curr.right = Node(val)
			prev = curr
			curr = curr.right
			curr.left = prev
			curr.right = None
	return head
from collections import deque

class Node:

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

def inOrder(root):
	if root is None:
		return
	inOrder(root.left)
	print(root.data, end=' ')
	inOrder(root.right)

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		head = convertToDLL(root)
		inOrder(root)
		print()
		temp = head
		last = None
		while temp != None:
			print(temp.data, end=' ')
			last = temp
			temp = temp.right
		print()
		temp = last
		while temp != None:
			print(temp.data, end=' ')
			temp = temp.left
		print()


def convertToDLL(root):

	def convert(root1):
		global ans
		global cur
		if root1 == None:
			return None
		if root1.left == None and root1.right == None:
			nde = Node(root1.data)
			if ans == None:
				cur = nde
				ans = nde
			else:
				cur.right = nde
				nde.left = cur
				cur = nde
			return None
		root1.left = convert(root1.left)
		root1.right = convert(root1.right)
		return root1
	global ans
	global cur
	ans = None
	cur = None
	convert(root)
	return ans
from collections import deque

class Node:

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

def inOrder(root):
	if root is None:
		return
	inOrder(root.left)
	print(root.data, end=' ')
	inOrder(root.right)

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		head = convertToDLL(root)
		inOrder(root)
		print()
		temp = head
		last = None
		while temp != None:
			print(temp.data, end=' ')
			last = temp
			temp = temp.right
		print()
		temp = last
		while temp != None:
			print(temp.data, end=' ')
			temp = temp.left
		print()


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

def helper(li):
	head = None
	tail = None
	for ele in li:
		new_node = Node(ele)
		if head is None:
			head = new_node
			head.right = None
			head.left = None
		else:
			tail.right = new_node
			new_node.left = tail
		tail = new_node
	return head

def convertToDLL(root):
	li = []
	leaf_Node_Finder(root, li)
	return helper(li)
from collections import deque

class Node:

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

def inOrder(root):
	if root is None:
		return
	inOrder(root.left)
	print(root.data, end=' ')
	inOrder(root.right)

def buildTree(s):
	if len(s) == 0 or s[0] == 'N':
		return None
	ip = list(map(str, s.split()))
	root = Node(int(ip[0]))
	size = 0
	q = deque()
	q.append(root)
	size = size + 1
	i = 1
	while size > 0 and i < len(ip):
		currNode = q[0]
		q.popleft()
		size = size - 1
		currVal = ip[i]
		if currVal != 'N':
			currNode.left = Node(int(currVal))
			q.append(currNode.left)
			size = size + 1
		i = i + 1
		if i >= len(ip):
			break
		currVal = ip[i]
		if currVal != 'N':
			currNode.right = Node(int(currVal))
			q.append(currNode.right)
			size = size + 1
		i = i + 1
	return root
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		root = buildTree(s)
		head = convertToDLL(root)
		inOrder(root)
		print()
		temp = head
		last = None
		while temp != None:
			print(temp.data, end=' ')
			last = temp
			temp = temp.right
		print()
		temp = last
		while temp != None:
			print(temp.data, end=' ')
			temp = temp.left
		print()


def convertToDLL(root):
	(head, tail) = (None, None)
	s = []

	def helper(root):
		if root is None:
			return
		if root.left is None and root.right is None:
			s.append(root)
			return None
		root.left = helper(root.left)
		root.right = helper(root.right)
		return root
	root = helper(root)
	while s:
		node = s.pop()
		if head is None:
			head = node
			tail = node
			node.right = None
		else:
			tail.left = node
			node.right = tail
			tail = tail.left
	return tail


def isleaf(root):
	if not root:
		return False
	return not root.left and (not root.right)

def inorder_c(root, array):
	if not root:
		return None
	if isleaf(root.left):
		ishead_flag = array[1]
		if not ishead_flag:
			array[2] = root.left
			array[1] = True
		temp = root.left
		root.left = None
		if array[0]:
			array[0].right = temp
		temp.left = array[0]
		array[0] = temp
	else:
		inorder_c(root.left, array)
	if isleaf(root.right):
		ishead_flag = array[1]
		if not ishead_flag:
			array[2] = root.right
			array[1] = True
		temp = root.right
		root.right = None
		if array[0]:
			array[0].right = temp
		temp.left = array[0]
		array[0] = temp
	else:
		inorder_c(root.right, array)

def convertToDLL(root):
	prev = None
	ishead = False
	head = None
	array = [prev, ishead, head]
	inorder_c(root, array)
	return array[2]


def ln(root, arr):
	if root == None:
		return
	if not root.left and (not root.right):
		arr.append(root)
	ln(root.left, arr)
	ln(root.right, arr)
	return arr

def rt(root, hm):
	if root == None:
		return
	if hm.get(root.left):
		root.left = None
	if hm.get(root.right):
		root.right = None
	rt(root.left, hm)
	rt(root.right, hm)
	return

def convertToDLL(root):
	arr = []
	arr = ln(root, arr)
	hm = {}
	for i in range(len(arr)):
		hm[arr[i]] = 1
	rt(root, hm)
	head = arr[0]
	for i in range(len(arr) - 1):
		arr[i].right = arr[i + 1]
		arr[i + 1].left = arr[i]
	return head


def isleaf(node):
	return node.right is None and node.left is None

def traverse(root, arr):
	if root is None:
		return arr
	if isleaf(root):
		arr.append(root)
	if root.left:
		if isleaf(root.left):
			arr.append(root.left)
			root.left = None
		else:
			traverse(root.left, arr)
	if root.right:
		if isleaf(root.right):
			arr.append(root.right)
			root.right = None
		else:
			traverse(root.right, arr)
	return arr

def convertToDLL(root):
	if root is None:
		return root
	dll = Node(0)
	start = dll
	curr = root
	arr = []
	arr = traverse(root, arr)
	for node in arr:
		start.right = node
		node.left = start
		node.right = None
		start = start.right
	dll.right.left = None
	return dll.right


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

def convertToDLL(root):
	l = []
	p = None
	DLL(root, l)
	head = Node(l[0])
	p = head
	for i in range(1, len(l)):
		temp = Node(l[i])
		p.right = temp
		temp.left = p
		p = p.right
	return head


def convertToDLL(root):
	ans = Node(-1)
	ans.left = None
	temp = ans
	li = []

	def leafDelete(root):
		if not root:
			return None
		if not root.left and (not root.right):
			li.append(root)
			return None
		root.left = leafDelete(root.left)
		root.right = leafDelete(root.right)
		return root
	root = leafDelete(root)
	for i in li:
		temp.right = i
		i.left = temp
		temp = temp.right
	ans = ans.right
	ans.left = None
	return ans


def convertToDLL(root):
	arr = []
	inorder(root, arr)
	head = None
	prev = None
	for i in range(len(arr)):
		if head == None:
			head = arr[i]
			prev = head
		else:
			prev.right = arr[i]
			arr[i].left = prev
			prev = arr[i]
	return head

def inorder(root, arr):
	if root:
		if root.left == None and root.right == None:
			arr.append(root)
			return root
		x = inorder(root.left, arr)
		if x is not None:
			root.left = None
		y = inorder(root.right, arr)
		if y is not None:
			root.right = None
	return


def convertToDLL(root):
	l1 = [[-1, -1, root, 0]]
	l2 = []
	d = []

	def isleaf(root):
		if root == None:
			return False
		if root.left == None and root.right == None:
			return True
		return False

	def f(root, cd, d):
		if root == None:
			return
		if isleaf(root.left):
			d.append(root.left)
			root.left = None
		else:
			f(root.left, cd - 1, d)
		if isleaf(root.right):
			d.append(root.right)
			root.right = None
		else:
			f(root.right, cd + 1, d)
	f(root, 0, d)
	p = None
	head = None
	for j in d:
		if p == None:
			p = j
			head = j
		else:
			j.left = p
			p.right = j
			p = j
	return head


def dll(root, a):
	if root == None:
		return
	else:
		if root.left == None and root.right == None:
			a.append(root)
		dll(root.left, a)
		dll(root.right, a)

def mtree(root, dict):
	if root:
		if root.left in dict.keys():
			root.left = None
		if root.right in dict.keys():
			root.right = None
		mtree(root.left, dict)
		mtree(root.right, dict)

def convertToDLL(root):
	a = []
	dict = {}
	dll(root, a)
	for i in range(len(a)):
		dict[a[i]] = 1
	mtree(root, dict)
	a[0].left = None
	for i in range(len(a) - 1):
		a[i].right = a[i + 1]
		a[i + 1].left = a[i]
	a[len(a) - 1].right = None
	return a[0]


def convertToDLL(root):

	def dfs(root):
		if root is None:
			return
		if root.left is None and root.right is None:
			if head[0] is None:
				head[0] = root
				head[1] = root
			else:
				head[1].right = root
				root.left = head[1]
				head[1] = root
			return
		(l, r) = (root.left, root.right)
		if root.left is not None and root.left.left is None and (root.left.right is None):
			root.left = None
		if root.right is not None and root.right.left is None and (root.right.right is None):
			root.right = None
		dfs(l)
		dfs(r)
	head = [None, None]
	dfs(root)
	return head[0]


def convertToDLL(root):
	if root == None:
		return
	head = [None]
	tail = [None]
	rec(root, head, tail)
	return head[0]

def rec(root, head, tail):
	if root == None:
		return
	if root.left == None and root.right == None:
		if head[0] == None:
			head[0] = root
			tail[0] = root
		else:
			tail[0].right = root
			root.left = tail[0]
			tail[0] = root
		return None
	root.left = rec(root.left, head, tail)
	root.right = rec(root.right, head, tail)
	return root


def preorder(temp, lst):
	if temp:
		if temp.left == None and temp.right == None:
			lst.append(temp.data)
		preorder(temp.left, lst)
		preorder(temp.right, lst)

def convertToDLL(root):
	queue = []
	lst = []
	t = None
	preorder(root, lst)
	queue.append(root)
	while len(queue) != 0:
		prev = t
		t = queue[0]
		queue.pop(0)
		if t.left:
			queue.append(t.left)
			if t.left.left == None and t.left.right == None:
				t.left = None
		if t.right:
			queue.append(t.right)
			if t.right.left == None and t.right.right == None:
				t.right = None
	head = None
	k = None
	for i in lst:
		if head == None:
			head = Node(i)
			k = head
		else:
			k.right = Node(i)
			k.right.left = k
			k = k.right
	return head


def convertToDLL(root):
	if root is None:
		return root
	leaves = []
	findLeaves(root, leaves)
	first = 1
	curr = None
	prev = None
	head = None
	for leaf in leaves:
		if first:
			curr = Node(leaf)
			curr.left = None
			curr.right = None
			head = curr
			first = 0
		else:
			curr.right = Node(leaf)
			prev = curr
			curr = curr.right
			curr.left = prev
			curr.right = None
	return head

def isLeaf(root):
	if root.left is None and root.right is None:
		return 1
	return 0

def findLeaves(root, leaves):
	if root is None:
		return root
	if isLeaf(root):
		leaves.append(root.data, leaves)
	if root.left is not None:
		if isLeaf(root.left):
			leaves.append(root.left.data)
			root.left = None
		else:
			findLeaves(root.left, leaves)
	if root.right is not None:
		if isLeaf(root.right):
			leaves.append(root.right.data)
			root.right = None
		else:
			findLeaves(root.right, leaves)


def convertToDLL(root):

	def createDLL(root, prevLeaf):
		if not root:
			return False
		if not root.left and (not root.right):
			root.left = prevLeaf[0]
			prevLeaf[0] = root
			return True
		else:
			isLeaf = createDLL(root.left, prevLeaf)
			if isLeaf:
				root.left = None
			isLeaf = createDLL(root.right, prevLeaf)
			if isLeaf:
				root.right = None
			return False
	prevLeaf = [None]
	createDLL(root, prevLeaf)
	curr = prevLeaf[0]
	prev = None
	while curr:
		curr.right = prev
		prev = curr
		curr = curr.left
	return prev


def convertToDLL(root):
	head = [None, None]
	parents = set()
	_convert(root, head, parents)
	return head[0]

def _convert(root, head, parents):
	if not root:
		return
	_convert(root.left, head, parents)
	if root.left and isLeaf(root.left) and (root.left not in parents):
		_modify_root(root.left, root, head, parents)
	if root.right and isLeaf(root.right) and (root.right not in parents):
		_modify_root(root.right, root, head, parents)
	_convert(root.right, head, parents)

def _modify_root(node, parent, head, parents):
	if not head[0]:
		listNode = Node(node.data)
		head[0] = listNode
		head[1] = head[0]
	else:
		listNode = Node(node.data)
		head[1].right = listNode
		listNode.left = head[1]
		head[1] = listNode
	if node is parent.left:
		parent.left = None
	elif node is parent.right:
		parent.right = None
	parents.add(parent)

def isLeaf(node):
	return node.left is None and node.right is None


def convertToDLL(root):
	arr = Conversion(root)
	return arr[0]

def leafnodes(root, arr, Hash):
	if root == None:
		return arr
	if root.left == None and root.right == None:
		arr.append(root)
		p_root = Hash[root]
		if p_root.left == root:
			p_root.left = None
		if p_root.right == root:
			p_root.right = None
		return arr
	arr = leafnodes(root.left, arr, Hash)
	arr = leafnodes(root.right, arr, Hash)
	return arr

def Hashmap(root):
	q = []
	q.append(root)
	Hash = dict()
	Hash[root] = None
	while len(q) != 0:
		temp = q.pop(0)
		if temp.left != None:
			Hash[temp.left] = temp
			q.append(temp.left)
		if temp.right != None:
			Hash[temp.right] = temp
			q.append(temp.right)
	return Hash

def Conversion(root):
	temp = None
	arr = []
	Hash = Hashmap(root)
	arr = leafnodes(root, arr, Hash)
	for i in range(0, len(arr) - 1):
		arr[i].left = temp
		arr[i].right = arr[i + 1]
		temp = arr[i]
	last = arr.pop()
	last.left = temp
	last.right = None
	arr.append(last)
	return arr


def convertToDLL(root):
	head = prev = None

	def util(root):
		nonlocal head, prev
		if root is None:
			return False
		if root.left is None and root.right is None:
			if prev is None:
				head = root
				prev = root
			else:
				prev.right = root
				prev.right.left = prev
				prev = prev.right
			return True
		if util(root.left):
			root.left = None
		if util(root.right):
			root.right = None
		return False
	util(root)
	return head


def recur(root, rootdll, lastref):
	if not root:
		return
	if not root.left and (not root.right):
		if not rootdll[0]:
			rootdll[0] = root
			lastref[0] = root
		else:
			root.left = lastref[0]
			lastref[0].right = root
			lastref[0] = root
		return None
	root.left = recur(root.left, rootdll, lastref)
	root.right = recur(root.right, rootdll, lastref)
	return root

def convertToDLL(root):
	rootdll = [None]
	lastref = [None]
	recur(root, rootdll, lastref)
	return rootdll[0]


def convertUtil(root):
	global head
	if root == None:
		return None
	if root.left == None and root.right == None:
		root.right = head
		if head != None:
			head.left = root
		head = root
		return None
	root.right = convertUtil(root.right)
	root.left = convertUtil(root.left)
	return root

def convertToDLL(root):
	global head
	head = None
	root = convertUtil(root)
	return head


def helper(root, dll):
	if not root:
		return None
	if not root.left and (not root.right):
		dll.append(root.data)
		return None
	root.left = helper(root.left, dll)
	root.right = helper(root.right, dll)
	return root

def convertToDLL(root):
	lst = []
	helper(root, lst)
	dll = Node(lst[0])
	curr = dll
	for i in lst[1:]:
		t = Node(i)
		curr.right = t
		t.left = curr
		curr = t
	return dll