Given inorder and level-order traversals of a Binary Tree, construct the Binary Tree and return the root Node. 
Input:
First line consists of T test cases. First line of every test case consists of N, denoting number of elements is respective arrays. Second and third line consists of arrays containing Inorder and Level-order traversal respectively.
Output:
Single line output, print the preOrder traversal of array.
Constraints:
1<=T<=100
1<=N<=100
Example:
Input:
2
3
1 0 2 
0 1 2 
7
3 1 4 0 5 2 6 
0 1 2 3 4 5 6 
Output:
0 1 2
0 1 3 4 2 5 6

Difficulty: MEDIUM
Tags: Tree algorithms

Data structures
Skill types: Data structures

Starter code:
#User function Template for python3

'''
class Node:

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

def buildTree(level, ino):
    #code here
    #return root of tree

Solutions:
def build(ino, start, end, d):
	if start > end:
		return None
	if start == end:
		return Node(ino[start])
	idx = start
	for i in range(start + 1, end + 1):
		if d[ino[i]] < d[ino[idx]]:
			idx = i
	root = Node(ino[idx])
	root.left = build(ino, start, idx - 1, d)
	root.right = build(ino, idx + 1, end, d)
	return root

def buildTree(level, ino):
	n = len(ino)
	d = {}
	for i in range(n):
		d[level[i]] = i
	return build(ino, 0, n - 1, d)


from collections import deque

def buildTree(level, ino):
	n = len(ino)
	if n == 0:
		return None
	pos = {}
	for i in range(n):
		pos[ino[i]] = i
	root = Node(level[0])
	idx = pos[level[0]]
	q = deque()
	p = root
	for i in range(1, n):
		idx2 = pos[level[i]]
		if idx2 < idx:
			p.left = Node(level[i])
			q.append(p.left)
		else:
			p.right = Node(level[i])
			q.append(p.right)
			p = q.popleft()
			idx = pos[p.data]
	return root


def buildTree(level, ino):
	return solve(level, 0)

def solve(level1, i):
	root = None
	if i < len(level1):
		root = Node(level1[i])
		root.left = solve(level1, 2 * i + 1)
		root.right = solve(level1, 2 * i + 2)
	return root


from collections import deque

def buildTree(levelOrder, inorder):
	q = deque()
	mp = dict()
	for i in range(len(inorder)):
		mp[inorder[i]] = i
	level_idx = 0
	root = Node(levelOrder[level_idx])
	q.append((root, [0, len(inorder) - 1]))
	level_idx += 1
	while q:
		m = len(q)
		for i in range(m):
			(node, [leftStart, rightEnd]) = q.popleft()
			in_index = mp[node.data]
			(leftEnd, rightStart) = (in_index - 1, in_index + 1)
			if leftStart <= leftEnd:
				node.left = Node(levelOrder[level_idx])
				q.append((node.left, [leftStart, leftEnd]))
				level_idx += 1
			if rightStart <= rightEnd:
				node.right = Node(levelOrder[level_idx])
				q.append((node.right, [rightStart, rightEnd]))
				level_idx += 1
	return root


def buildTree(level, ino):
	if ino:
		for i in range(0, len(level)):
			if level[i] in ino:
				node = Node(level[i])
				mid = ino.index(level[i])
				break
		node.left = buildTree(level, ino[0:mid])
		node.right = buildTree(level, ino[mid + 1:len(ino)])
		return node
	else:
		return None


def buildTree(level, ino):
	if not level and (not ino):
		return None
	else:
		root = level[0]
		r = Node(root)
		idx = ino.index(root)
		il = ino[0:idx]
		ir = ino[idx + 1:]
		ll = []
		lr = []
		for i in range(1, len(level)):
			if level[i] in il:
				ll.append(level[i])
			else:
				lr.append(level[i])
		r.left = buildTree(ll, il)
		r.right = buildTree(lr, ir)
		return r


def buildTree(levelorder, inorder):
	n = len(inorder)
	map = dict()
	for i in range(n):
		map[inorder[i]] = i + 1

	def tempfunc(li, ri, levelorder):
		nonlocal map, inorder
		if li > ri:
			return None
		if li == ri:
			return Node(inorder[li - 1])
		k = map[levelorder[0]]
		tempMap = dict()
		for i in range(li, k):
			tempMap[inorder[i - 1]] = 1
		for i in range(k + 1, ri + 1):
			tempMap[inorder[i - 1]] = 2
		leftLevelList = []
		rightLevelList = []
		for i in levelorder:
			if tempMap.get(i) == 1:
				leftLevelList.append(i)
			elif tempMap.get(i) == 2:
				rightLevelList.append(i)
		left = tempfunc(li, k - 1, leftLevelList)
		right = tempfunc(k + 1, ri, rightLevelList)
		new = Node(levelorder[0])
		new.left = left
		new.right = right
		return new
	return tempfunc(1, n, levelorder)


def buildTree(level, ino):
	if not level or not ino:
		return None
	root = Node(level.pop(0))
	mid = ino.index(root.data)
	left_ino = ino[:mid]
	right_ino = ino[mid + 1:]
	left_level = []
	right_level = []
	for a in level:
		if a in left_ino:
			left_level.append(a)
		else:
			right_level.append(a)
	root.left = buildTree(left_level, left_ino)
	root.right = buildTree(right_level, right_ino)
	return root


def buildTree(level, ino):
	if not level and (not ino):
		return None
	else:
		root = level[0]
		root_node = Node(root)
		index = ino.index(root)
		ino_left = ino[0:index]
		ino_right = ino[index + 1:]
		level_left = []
		level_right = []
		for i in range(1, len(level)):
			if level[i] in ino_left:
				level_left.append(level[i])
			else:
				level_right.append(level[i])
		root_node.left = buildTree(level_left, ino_left)
		root_node.right = buildTree(level_right, ino_right)
		return root_node


def buildTree(level, ino):
	LevelOrder = level
	InOrder = ino
	LevelOrderMap = {}
	for i in LevelOrder:
		LevelOrderMap[i] = 0

	def MakeTree(LevelOrder, InOrder, LevelOrderMap):
		if LevelOrder == []:
			return None
		root = Node(LevelOrder[0])
		for i in range(0, len(InOrder)):
			if InOrder[i] == LevelOrder[0]:
				break
		LSTINO = InOrder[:i]
		LSTLVL = []
		for keys in LevelOrderMap:
			if keys in LSTINO:
				LSTLVL.append(keys)
		RSTINO = InOrder[i + 1:]
		RSTLVL = []
		for keys in LevelOrderMap:
			if keys in RSTINO:
				RSTLVL.append(keys)
		root.left = MakeTree(LSTLVL, LSTINO, LevelOrderMap)
		root.right = MakeTree(RSTLVL, RSTINO, LevelOrderMap)
		return root
	ans = []

	def PreOrder(Node):
		nonlocal ans
		if Node == None:
			return
		ans.append(Node.data)
		PreOrder(Node.left)
		PreOrder(Node.right)
	root = MakeTree(LevelOrder, InOrder, LevelOrderMap)
	PreOrder(root)
	for i in ans:
		print(i, end=' ')
	return


def func(level, ino, mp):
	if len(level) < 1:
		return
	ele = level[0]
	root = Node(ele)
	if len(level) == 1:
		return root
	root_ix = mp[ele]
	l_level = []
	r_level = []
	for i in range(len(level)):
		if mp[level[i]] < root_ix:
			l_level.append(level[i])
		elif mp[level[i]] > root_ix:
			r_level.append(level[i])
	if root_ix != 0:
		root.left = func(l_level, ino, mp)
	if root_ix != len(ino) - 1:
		root.right = func(r_level, ino, mp)
	return root

def buildTree(level, ino):
	mp = {ino[i]: i for i in range(len(ino))}
	return func(level, ino, mp)


def find(ino, level, m, n):
	arr = []
	for i in range(len(level)):
		if level[i] in ino[m:n]:
			arr.append(level[i])
	return arr

def buildTree(level, ino):
	if len(level) == 0:
		return None
	root = Node(level[0])
	root.left = None
	root.right = None
	ele_to_search = level[0]
	for i in range(len(level)):
		if ino[i] == ele_to_search:
			break
	leftList = find(ino, level, 0, i)
	rightList = find(ino, level, i + 1, len(level))
	v1 = ino[:i]
	v11 = ino[i + 1:]
	root.left = buildTree(leftList, v1)
	root.right = buildTree(rightList, v11)
	return root


class Node:

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

class ConstructTree:

	def __init__(self):
		self.dict_ = dict()

	def ConstructMap(self, level):
		for i in range(0, len(level)):
			key = level[i]
			self.dict_[key] = i

	def construct(self, in_, level, start, end):
		if start > end:
			return None
		min_index = start
		for i in range(start + 1, end + 1):
			temp = in_[i]
			if self.dict_.get(in_[min_index]) > self.dict_.get(temp):
				min_index = i
		root = Node(in_[min_index])
		if start == end:
			return root
		root.left = self.construct(in_, level, start, min_index - 1)
		root.right = self.construct(in_, level, min_index + 1, end)
		return root

def buildTree(level, ino):
	obj = ConstructTree()
	obj.ConstructMap(level)
	root = obj.construct(ino, level, 0, len(ino) - 1)
	return root


class makenode:

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

def buildTree1(inorder, levelorder, iStart, iEnd, n):
	if n <= 0:
		return None
	root = makenode(levelorder[0])
	index = -1
	for i in range(iStart, iEnd + 1):
		if levelorder[0] == inorder[i]:
			index = i
			break
	s = set()
	for i in range(iStart, index):
		s.add(inorder[i])
	lLevel = [] * len(s)
	rLevel = [] * (iEnd - iStart - len(s))
	for i in range(1, n):
		if levelorder[i] in s:
			lLevel.append(levelorder[i])
		else:
			rLevel.append(levelorder[i])
	root.left = buildTree1(inorder, lLevel, iStart, index - 1, index - iStart)
	root.right = buildTree1(inorder, rLevel, index + 1, iEnd, iEnd - index)
	return root

def buildTree(level, ino):
	return buildTree1(ino, level, 0, n - 1, n)


def buildTree(level, ino):
	if not level and (not ino):
		return
	root = Node(level[0])
	index = ino.index(level[0])
	pos1 = ino[:index]
	pos2 = ino[index + 1:]
	l1 = []
	l2 = []
	for i in range(1, len(level)):
		if level[i] in pos1:
			l1.append(level[i])
		else:
			l2.append(level[i])
	root.left = buildTree(l1, pos1)
	root.right = buildTree(l2, pos2)
	return root


from collections import deque

def buildTree(level, ino):
	q = deque()
	curr = 0
	root = Node(level[curr])
	curr += 1
	q.append(root)
	while curr != len(level):
		temp = q.popleft()
		temp.left = Node(level[curr])
		curr += 1
		q.append(temp.left)
		if curr != len(level):
			temp.right = Node(level[curr])
			curr += 1
			q.append(temp.right)
	return root


def buildTree(level, inorder):
	if not level or not inorder:
		return None
	root = Node(level[0])
	root_inorder_index = inorder.index(level[0])
	left_inorder = set(inorder[:root_inorder_index])
	right_inorder = set(inorder[root_inorder_index + 1:])
	level_order_left = [i for i in level if i in left_inorder]
	level_order_right = [i for i in level if i in right_inorder]
	root.left = buildTree(level_order_left, inorder[:root_inorder_index])
	root.right = buildTree(level_order_right, inorder[root_inorder_index + 1:])
	return root


def buildTree(level, ino):
	if not level:
		return None
	if not ino:
		return None
	curr = level[0]
	root = Node(curr)
	i = ino.index(curr)
	li = set(ino[:i])
	lef = []
	for ele in level:
		if ele in li:
			lef.append(ele)
	li = set(ino[i + 1:])
	ler = []
	for ele in level:
		if ele in li:
			ler.append(ele)
	root.left = buildTree(lef, ino[:i])
	root.right = buildTree(ler, ino[i + 1:])
	return root


from collections import deque

class Node:

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

def buildTree(level, ino):
	n = len(ino)
	queue1 = deque()
	for i in range(n):
		queue1.append(level[i])
	queue2 = deque()
	hm = {ino[i]: i for i in range(n)}
	root = Node(queue1.popleft())
	queue2.append([root, 0, n - 1])
	while len(queue2):
		k = len(queue2)
		while k:
			k -= 1
			(tmp, l1, h1) = queue2.popleft()
			val = tmp.data
			idx = hm[val]
			if l1 <= idx - 1:
				new_node1 = Node(queue1.popleft())
				tmp.left = new_node1
				queue2.append([new_node1, l1, idx - 1])
			if idx + 1 <= h1:
				new_node2 = Node(queue1.popleft())
				tmp.right = new_node2
				queue2.append([new_node2, idx + 1, h1])
	return root


def buildTree(level, ino):
	root = None
	n = len(level)
	if n <= 0:
		return None
	nodeList = []
	for i in level:
		nodeList.append(Node(i))
	for i in range(n // 2):
		node = nodeList[i]
		next_left_node = 2 * i + 1
		if next_left_node < n:
			node.left = nodeList[next_left_node]
		next_right_node = next_left_node + 1
		if next_right_node < n:
			node.right = nodeList[next_right_node]
	return nodeList[0]


def buildTree(level, ino):
	curr = 0
	n = len(ino)
	root = Node(level[0])
	curr += 1
	q = [root]
	while curr != n:
		node = q.pop(0)
		node.left = Node(level[curr])
		curr += 1
		q.append(node.left)
		if curr != n:
			node.right = Node(level[curr])
			curr += 1
			q.append(node.right)
	return root


def buildTree(level, ino):
	if not ino and (not level):
		return None
	else:
		root = Node(level[0])
		idx = ino.index(level[0])
		in_left = ino[:idx]
		in_right = ino[idx + 1:]
		left = []
		right = []
		for i in range(1, len(level)):
			if level[i] in in_left:
				left.append(level[i])
			if level[i] in in_right:
				right.append(level[i])
		root.left = buildTree(left, in_left)
		root.right = buildTree(right, in_right)
		return root


def buildTree(level, ino):
	if len(ino) == 1:
		return Node(ino[0])
	mp = {ino[i]: i for i in range(len(ino))}
	for i in range(len(level)):
		val = level[i]
		if val in mp:
			root = Node(val)
			root_idx = mp[val]
			break
	if root_idx > 0:
		root.left = buildTree(level, ino[:root_idx])
	if root_idx + 1 < n:
		root.right = buildTree(level, ino[root_idx + 1:])
	return root


def find(ino, lev):
	for i in range(len(ino)):
		if ino[i] == lev:
			return i

def buildTree(levo, ino):
	if not ino:
		return
	count = find(ino, levo[0])
	node = Node(levo.pop(0))
	new_level = []
	for i in range(len(levo) - 1, -1, -1):
		if levo[i] in ino[:count]:
			new_level.insert(0, levo.pop(i))
	node.left = buildTree(new_level, ino[:count])
	node.right = buildTree(levo, ino[count + 1:])
	return node


def buildTree(level, ino):
	if not level or not ino:
		return
	new_node = Node(level[0])
	idx = ino.index(level[0])
	left_ino = ino[:idx]
	left_level = [x for x in level if x in left_ino]
	new_node.left = buildTree(left_level, left_ino)
	right_ino = ino[idx + 1:]
	right_level = [x for x in level if x in right_ino]
	new_node.right = buildTree(right_level, right_ino)
	return new_node


def buildTree(level, ino):
	if ino:
		for i in range(len(level)):
			if level[i] in ino:
				root = Node(level[i])
				mid = ino.index(level[i])
				break
		root.left = buildTree(level, ino[:mid])
		root.right = buildTree(level, ino[mid + 1:])
		return root


from collections import deque

def buildTree(levelorder, inorder):

	def search(alteredinorder, target):
		for i in range(0, len(alteredinorder)):
			if alteredinorder[i] == target:
				return i
		return -1
	que = deque()
	if levelorder:
		root = Node(levelorder[0])
		que.append([inorder, levelorder, root])
	while que:
		current = que.popleft()
		idx = search(current[0], current[2].data)
		templeftin = current[0][0:idx]
		if len(templeftin) > 0:
			templevel = [i for i in current[1] if i in templeftin]
			leftnode = Node(templevel[0])
			current[2].left = leftnode
			que.append([templeftin, templevel, leftnode])
		temprightin = current[0][idx + 1:]
		if len(temprightin) > 0:
			templevel = [i for i in current[1] if i in temprightin]
			rightnode = Node(templevel[0])
			current[2].right = rightnode
			que.append([temprightin, templevel, rightnode])
	return root


def constructTree(level, inorder):
	if len(level) == 0:
		return
	nodeVal = level[0]
	node = Node(nodeVal)
	for (index, val) in enumerate(inorder):
		if val == nodeVal:
			break
	left_inorder = inorder[:index]
	right_inorder = inorder[index + 1:]
	left_level = list()
	right_level = list()
	for nodeVal in level:
		if nodeVal in left_inorder:
			left_level.append(nodeVal)
		elif nodeVal in right_inorder:
			right_level.append(nodeVal)
	node.left = constructTree(left_level, left_inorder)
	node.right = constructTree(right_level, right_inorder)
	return node

def buildTree(level, inorder):
	return constructTree(level, inorder)


from collections import deque

def buildTree(level, ino):
	levelDict = {}
	for (index, val) in enumerate(level):
		if val not in levelDict:
			levelDict[val] = index
	n = len(ino)
	root = construct(ino, levelDict, 0, n - 1)
	return root

def construct(inorder, levelDict, start, end):
	if start > end:
		return None
	minIndex = start
	i = start + 1
	while i <= end:
		if levelDict[inorder[i]] < levelDict[inorder[minIndex]]:
			minIndex = i
		i += 1
	newNode = Node(inorder[minIndex])
	if start == end:
		return newNode
	newNode.left = construct(inorder, levelDict, start, minIndex - 1)
	newNode.right = construct(inorder, levelDict, minIndex + 1, end)
	return newNode

class Node:

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

def preOrd(root):
	if not root:
		return
	print(root.data, end=' ')
	preOrd(root.left)
	preOrd(root.right)
if __name__ == '__main__':
	tcs = int(input())
	for _ in range(tcs):
		n = int(input())
		InOrd = [int(x) for x in input().split()]
		LvlOrd = [int(x) for x in input().split()]
		root = buildTree(LvlOrd, InOrd)
		preOrd(root)
		print()


def ff(l, i):
	if not l:
		return
	y = i.index(l[0])
	r = Node(l[0])
	c = []
	d = []
	for j in l:
		if j in i[:y]:
			c.append(j)
		if j in i[y + 1:]:
			d.append(j)
	r.left = ff(c, i[:y])
	r.right = ff(d, i[y + 1:])
	return r

def buildTree(l, i):
	return ff(l, i)

class Node:

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

def preOrd(root):
	if not root:
		return
	print(root.data, end=' ')
	preOrd(root.left)
	preOrd(root.right)
if __name__ == '__main__':
	tcs = int(input())
	for _ in range(tcs):
		n = int(input())
		InOrd = [int(x) for x in input().split()]
		LvlOrd = [int(x) for x in input().split()]
		root = buildTree(LvlOrd, InOrd)
		preOrd(root)
		print()


def buildTree(level, ino):
	if not ino:
		return None
	node = Node(level[0])
	index = ino.index(level[0])
	in_left = ino[:index]
	in_right = ino[index + 1:]
	level_left = [x for x in level if x in set(in_left)]
	level_right = [x for x in level if x in set(in_right)]
	node.left = buildTree(level_left, in_left)
	node.right = buildTree(level_right, in_right)
	return node

class Node:

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

def preOrd(root):
	if not root:
		return
	print(root.data, end=' ')
	preOrd(root.left)
	preOrd(root.right)
if __name__ == '__main__':
	tcs = int(input())
	for _ in range(tcs):
		n = int(input())
		InOrd = [int(x) for x in input().split()]
		LvlOrd = [int(x) for x in input().split()]
		root = buildTree(LvlOrd, InOrd)
		preOrd(root)
		print()


def buildTree(level, ino):

	def fun(ino, isi, iei, level):
		if isi > iei:
			return None
		root = Node(level[0])
		if len(level) == 1:
			return root
		s = set()
		idx = isi
		while level[0] != ino[idx]:
			s.add(ino[idx])
			idx += 1
		lols = []
		lors = []
		for i in level[1:]:
			if i in s:
				s.remove(i)
				lols.append(i)
			else:
				lors.append(i)
		root.left = fun(ino, isi, idx - 1, lols)
		root.right = fun(ino, idx + 1, iei, lors)
		return root
	n = len(level) - 1
	ans = fun(ino, 0, n, level)

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


def find(level, ino):
	lev = []
	for i in range(len(level)):
		for j in range(len(ino)):
			if ino[j] == level[i]:
				lev.append(level[i])
	return lev

def cons(level, ino, n):
	dict = {}
	for i in range(n):
		dict[ino[i]] = i
	rootIndex = dict[level[0]]
	root = Node(level[0])
	if rootIndex != 0:
		root.left = cons(find(level, ino[0:rootIndex]), ino[0:rootIndex], rootIndex)
	if rootIndex != n - 1:
		root.right = cons(find(level, ino[rootIndex + 1:n]), ino[rootIndex + 1:n], n - rootIndex - 1)
	return root

def buildTree(level, ino):
	n = len(level)
	head = cons(level, ino, n)
	return head


def construct(in_order, lvl_order):
	if len(in_order) == 0 or len(lvl_order) == 0:
		return None
	res = Node(lvl_order.pop(0))
	q = [res]
	in_ = [in_order]
	while len(q) > 0:
		root = q.pop(0)
		in_order = in_.pop(0)
		if root.data in in_order:
			root_index = in_order.index(root.data)
			left_tree_in_order = in_order[:root_index]
			right_tree_in_order = in_order[root_index + 1:]
			if len(left_tree_in_order) > 0:
				root.left = Node(lvl_order.pop(0))
				q.append(root.left)
				in_.append(left_tree_in_order)
			if len(right_tree_in_order) > 0:
				root.right = Node(lvl_order.pop(0))
				q.append(root.right)
				in_.append(right_tree_in_order)
	return res

def buildTree(level, ino):
	root = construct(ino, level)
	return root


class Node:

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

def buildTree(level, ino):
	if ino:
		for i in range(0, len(level)):
			if level[i] in ino:
				node = Node(level[i])
				io_index = ino.index(level[i])
				break
		node.left = buildTree(level, ino[0:io_index])
		node.right = buildTree(level, ino[io_index + 1:len(ino)])
		return node
	else:
		return None


def buildTree(level, ino):
	n = len(level)
	return buildTreeUtil(level, ino, 0, n - 1, n)

def buildTreeUtil(level, ino, start, end, n):
	if n <= 0 or start > end:
		return None
	root = level[0]
	root_index = get_index(ino, start, end, root)
	in_left_set = set(ino[start:root_index])
	(left_level, right_level) = ([], [])
	for i in range(1, n, 1):
		if level[i] in in_left_set:
			left_level.append(level[i])
		else:
			right_level.append(level[i])
	root_node = Node(root)
	root_node.left = buildTreeUtil(left_level, ino, start, root_index - 1, root_index - start)
	root_node.right = buildTreeUtil(right_level, ino, root_index + 1, end, end - root_index)
	return root_node

def get_index(ino, start, end, root):
	for i in range(start, end + 1, 1):
		if ino[i] == root:
			return i


def buil(level, ino):
	if ino:
		for i in range(len(level)):
			if level[i] in ino:
				node = Node(level[i])
				index = ino.index(level[i])
				break
		node.left = buil(level, ino[0:index])
		node.right = buil(level, ino[index + 1:len(ino)])
		return node
	else:
		return None

def buildTree(level, ino):
	n = len(level)
	a = buil(level, ino)
	return a


def buildTree(level, ino):
	n = len(ino)
	if n == 0:
		return None
	data = level[0]
	index = -1
	for i in range(n):
		if ino[i] == data:
			index = i
			break
	if index == -1:
		return None
	root = Node(data)
	li = ino[:index]
	ri = ino[index + 1:]
	ll = []
	rl = []
	for i in range(1, len(level)):
		if level[i] in li:
			ll.append(level[i])
		else:
			rl.append(level[i])
	root.left = buildTree(ll, li)
	root.right = buildTree(rl, ri)
	return root


class Node:

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

def construct(inorder, start, end, d):
	if start > end:
		return None
	index = start
	for j in range(start + 1, end + 1):
		if d.get(inorder[j]) < d.get(inorder[index]):
			index = j
	root = Node(inorder[index])
	root.left = construct(inorder, start, index - 1, d)
	root.right = construct(inorder, index + 1, end, d)
	return root

def buildTree(level, ino):
	d = {}
	for (i, e) in enumerate(level):
		d[e] = i
	return construct(ino, 0, len(ino) - 1, d)


def buildTree(level, ino):
	if not ino or not level:
		return None
	root = Node(level[0])
	index = ino.index(root.data)
	leftTree = ino[:index]
	rightTree = ino[index + 1:]
	(levelLeft, levelRight) = ([], [])
	for value in level[1:]:
		if value in leftTree:
			levelLeft.append(value)
		elif value in rightTree:
			levelRight.append(value)
	root.left = buildTree(levelLeft, leftTree)
	root.right = buildTree(levelRight, rightTree)
	return root


def buildTree(level, ino):
	if not level:
		return
	root = Node(level[0])
	index = 1
	queue = [root]
	while index < len(level):
		newLevel = []
		for node in queue:
			counter = 2
			left = True
			while counter > 0 and index < len(level):
				newNode = Node(level[index])
				if left:
					node.left = newNode
				else:
					node.right = newNode
				index += 1
				counter -= 1
				left = not left
				newLevel.append(newNode)
		queue.clear()
		if newLevel:
			queue.extend(newLevel)
	return root


def buildTree(level, ino):
	if not level:
		return
	root = Node(level[0])
	index = 1
	queue = [root]
	while index < len(level):
		newLevel = []
		for node in queue:
			if index >= len(level):
				break
			newNode = Node(level[index])
			node.left = newNode
			index += 1
			newLevel.append(newNode)
			if index >= len(level):
				break
			newNode = Node(level[index])
			node.right = newNode
			index += 1
			newLevel.append(newNode)
		queue.clear()
		if newLevel:
			queue.extend(newLevel)
	return root


def buildTree(level, ino):
	return constructTree_levelorder_inorder(level, ino)

def constructTree_levelorder_inorder(levelorder, inorder):
	if len(inorder) == 0:
		return None
	rootData = -1
	rootIndex = -1
	for i in levelorder:
		if i in inorder:
			rootData = i
			rootIndex = inorder.index(i)
			break
	if rootIndex == -1:
		return None
	root = Node(rootData)
	root.left = constructTree_levelorder_inorder(levelorder, inorder[:rootIndex])
	root.right = constructTree_levelorder_inorder(levelorder, inorder[rootIndex + 1:])
	return root


def buildTree(level, ino):
	if len(ino) == 0:
		return None
	node = Node(level[0])
	hasset = set()
	left_level = []
	right_level = []
	i = 0
	idx = ino.index(level[0])
	while i < idx:
		hasset.add(ino[i])
		i += 1
	for ele in level[1:]:
		if ele in hasset:
			left_level.append(ele)
		else:
			right_level.append(ele)
	node.left = buildTree(left_level, ino[:idx])
	node.right = buildTree(right_level, ino[idx + 1:])
	return node


def buildTree(level, ino):
	if ino:
		for i in range(len(level)):
			if level[i] in ino:
				curr = Node(level[i])
				x = ino.index(level[i])
				break
		curr.left = buildTree(level, ino[:x])
		curr.right = buildTree(level, ino[x + 1:])
		return curr


def buildTree(level, ino):
	start = 0
	end = len(ino) - 1
	if start > end:
		return -1
	Hash = search(ino)
	root = tobinarytree(level, ino, start, end, Hash)
	return root

def tobinarytree(level, ino, start, end, Hash):
	if start > end:
		return None
	data = ino[(start + end) // 2]
	root = Node(data)
	index = Hash[data]
	if start == None:
		return root
	root.left = tobinarytree(level, ino, start, index - 1, Hash)
	root.right = tobinarytree(level, ino, index + 1, end, Hash)
	return root

def search(inorder):
	Hash = {}
	for i in range(0, len(inorder)):
		Hash[inorder[i]] = i
	return Hash


def buildTree(level, ino):
	if not len(level):
		return None
	rootVal = level[0]
	root = Node(rootVal)
	ind = 0
	while ino[ind] != rootVal:
		ind += 1
	leftIno = ino[:ind]
	rightIno = ino[ind + 1:]
	leftLevel = []
	rightLevel = []
	for val in level[1:]:
		if val in leftIno:
			leftLevel.append(val)
		else:
			rightLevel.append(val)
	root.left = buildTree(leftLevel, leftIno)
	root.right = buildTree(rightLevel, rightIno)
	return root


def buildTree(level, ino):
	if level is None and ino is None:
		return None
	elif level is None and ino is not None or (level is not None and ino is None):
		return None
	else:
		root = Node(level[0])
		ino_root_idx = ino.index(level[0])
		(ino_left, ino_right) = ([], [])
		for i in range(ino_root_idx):
			ino_left.append(ino[i])
		for i in range(ino_root_idx + 1, len(ino)):
			ino_right.append(ino[i])
		N = len(level)
		(level_left, level_right) = ([], [])
		for i in range(1, N):
			if level[i] in ino_left:
				level_left.append(level[i])
			else:
				level_right.append(level[i])
		if level_left:
			root.left = buildTree(level_left, ino_left)
		if level_right:
			root.right = buildTree(level_right, ino_right)
		return root


def preorder_traversal(root, res):
	if root == None:
		return
	res.append(root.data)
	preorder_traversal(root.left, res)
	preorder_traversal(root.right, res)

def aux_func(level, ino, ino_idx_dict, il, ir):
	if not level:
		return None
	val = level[0]
	root = Node(val)
	idx = ino_idx_dict[val]
	lsize = idx - il
	rsize = ir - il
	left_level = []
	right_level = []
	for l in level:
		ino_idx = ino_idx_dict[l]
		if ino_idx >= il and ino_idx < idx:
			left_level.append(l)
		if ino_idx > idx and ino_idx <= ir:
			right_level.append(l)
	if lsize > 0:
		root.left = aux_func(left_level, ino, ino_idx_dict, il, il + lsize - 1)
	if rsize > 0:
		root.right = aux_func(right_level, ino, ino_idx_dict, idx + 1, ir)
	return root

def buildTree(level, ino):
	N = len(ino)
	ino_idx_dict = {ino[i]: i for i in range(N)}
	root = aux_func(level, ino, ino_idx_dict, 0, N - 1)
	res = []
	preorder_traversal(root, res)
	for r in res:
		print(r, end=' ')


def buildTree(level, ino):
	if not level and (not ino):
		return None
	curr = level[0]
	tnode = Node(curr)
	index = ino.index(curr)
	inleft = ino[0:index]
	orleft = []
	oright = []
	inright = ino[index + 1:len(ino)]
	for i in range(1, len(level)):
		if level[i] in inleft:
			orleft.append(level[i])
		elif level[i] in inright:
			oright.append(level[i])
	tnode.left = buildTree(orleft, inleft)
	tnode.right = buildTree(oright, inright)
	return tnode


def f(ino, i, j, d):
	if i > j:
		return
	mn = (i, ino[i])
	for k in range(i, j + 1):
		if d[ino[k]] < d[mn[1]]:
			mn = (k, ino[k])
	root = Node(mn[1])
	root.left = f(ino, i, mn[0] - 1, d)
	root.right = f(ino, mn[0] + 1, j, d)
	return root

def buildTree(level, ino):
	d = dict()
	for i in range(len(level)):
		d[level[i]] = i
	return f(ino, 0, len(ino) - 1, d)


def buildTree(level, ino):

	def construct(start, end):
		if start > end:
			return
		index = l[ino[start]]
		ans = start
		for i in range(start, end + 1):
			if l[ino[i]] < index:
				index = l[ino[i]]
				ans = i
		root = Node(ino[ans])
		if start == end:
			return root
		root.left = construct(start, ans - 1)
		root.right = construct(ans + 1, end)
		return root
	l = {}
	for i in range(len(level)):
		l[level[i]] = i
	return construct(0, len(level) - 1)


def construct_tree(levelorder, inorder):
	if len(levelorder) == 0:
		return None
	cur_node = Node(levelorder[0])
	for i in range(0, len(inorder)):
		if cur_node.data == inorder[i]:
			cur_index = i
	left_inorder = inorder[0:cur_index]
	right_inorder = inorder[cur_index + 1:]
	left_level = []
	right_level = []
	for node in levelorder:
		if node in left_inorder:
			left_level.append(node)
	for node in levelorder:
		if node in right_inorder:
			right_level.append(node)
	cur_node.left = construct_tree(left_level, left_inorder)
	cur_node.right = construct_tree(right_level, right_inorder)
	return cur_node

def buildTree(level, ino):
	return construct_tree(level, ino)


def f(l, r, inorder: list, indices: dict):
	if l > r:
		return None
	min_idx = l
	for i in range(l + 1, r + 1):
		if indices[inorder[i]] < indices[inorder[min_idx]]:
			min_idx = i
	cur = Node(inorder[min_idx])
	cur.left = f(l, min_idx - 1, inorder, indices)
	cur.right = f(min_idx + 1, r, inorder, indices)
	return cur

def buildTree(level, ino):
	indices = dict(((x, i) for (i, x) in enumerate(level)))
	return f(0, len(ino) - 1, ino, indices)


def f(level: list, inorder: list, indices: dict):
	if len(level) == 0:
		return None
	cur = Node(level[0])
	idx = indices[level[0]]
	(left_level, right_level) = ([], [])
	for i in range(1, len(level)):
		if indices[level[i]] < idx:
			left_level.append(level[i])
		else:
			right_level.append(level[i])
	cur.left = f(left_level, inorder, indices)
	cur.right = f(right_level, inorder, indices)
	return cur

def buildTree(level, ino):
	indices = dict(((x, i) for (i, x) in enumerate(ino)))
	return f(level, ino, indices)


def f(level, inorder):
	if len(inorder) == 0:
		return None
	cur = Node(level[0])
	idx = inorder.index(level[0])
	(left_level, right_level) = ([], [])
	for i in range(1, len(level)):
		if inorder.index(level[i]) < idx:
			left_level.append(level[i])
		else:
			right_level.append(level[i])
	cur.left = f(left_level, inorder[:idx])
	cur.right = f(right_level, inorder[idx + 1:])
	return cur

def buildTree(level, ino):
	return f(level, ino)


def buildTree(level, ino):
	root = Node(level[0])
	m = ino.index(root.data)
	leftin = ino[:m]
	rightin = ino[m + 1:]
	leftlevel = level[1:]
	rightlevel = level
	rightlevel.remove(root.data)
	for i in leftin:
		try:
			rightlevel.remove(i)
		except:
			continue
	for i in rightin:
		try:
			leftlevel.remove(i)
		except:
			continue
	if leftin:
		root.left = buildTree(leftlevel, leftin)
	if rightin:
		root.right = buildTree(rightlevel, rightin)
	return root


def buildTree(level, ino):
	if len(level) == 0:
		return None
	if len(level) == 1:
		return Node(level[0])
	root_val = level[0]
	ino_left = []
	ino_right = []
	left = True
	for val in ino:
		if val == root_val:
			left = False
			continue
		if left:
			ino_left.append(val)
		else:
			ino_right.append(val)
	level_left = []
	level_right = []
	for val in level:
		if val in ino_left:
			level_left.append(val)
		if val in ino_right:
			level_right.append(val)
	root = Node(root_val)
	root.left = buildTree(level_left, ino_left)
	root.right = buildTree(level_right, ino_right)
	return root


def buildTree(level, ino):

	def build(ino):
		if not ino:
			return None
		else:
			for ele in level:
				if ele in ino:
					idx = ino.index(ele)
					root = Node(ele)
					break
			root.left = build(ino[0:idx])
			root.right = build(ino[idx + 1:len(ino)])
			return root
	return build(ino)


def buildTree(level, ino):
	if len(level) != len(ino):
		return None
	d = dict()
	for i in range(len(ino)):
		d[ino[i]] = i

	def vfx(ino, isi, iei, level, d):
		if isi > iei:
			return None
		root = Node(level[0])
		if len(level) == 1:
			return root
		index = d[level[0]]
		lofls = []
		lofrs = []
		s = dict()
		for i in range(isi, index):
			s[ino[i]] = i
		for i in range(1, len(level)):
			ele = level[i]
			if len(s) != 0 and s.get(ele) != None:
				lofls.append(ele)
				s.pop(ele)
			else:
				lofrs.append(ele)
		root.left = vfx(ino, isi, index - 1, lofls, d)
		root.right = vfx(ino, index + 1, iei, lofrs, d)
		return root
	return vfx(ino, 0, len(ino) - 1, level, d)


class Node:

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

def func(lev, ino):
	for i in range(len(lev)):
		if lev[i] in ino:
			nn = Node(lev[i])
			ind = ino.index(lev[i])
			nn.left = func(lev, ino[0:ind])
			nn.right = func(lev, ino[ind + 1:len(ino)])
			return nn
	else:
		return None

def buildTree(lev, ino):
	h = {}
	return func(lev, ino)


def buildTree(level, ino):
	if not level:
		return None
	root = Node(level[0])
	if not len(ino):
		return root
	in_indx = ino.index(root.data)
	left_level = []
	right_level = []
	ino_left = ino[:in_indx]
	level = level[1:]
	for i in range(0, len(level)):
		if level[i] in ino_left:
			left_level.append(level[i])
		else:
			right_level.append(level[i])
	root.left = buildTree(left_level, ino_left)
	root.right = buildTree(right_level, ino[in_indx + 1:])
	return root


def buildTree(level, ino):
	if ino:
		for i in range(len(level)):
			if level[i] in ino:
				root = Node(level[i])
				pos = ino.index(root.data)
				break
		root.left = buildTree(level, ino[:pos])
		root.right = buildTree(level, ino[pos + 1:len(ino)])
		return root
	return None


def helper(level, ino, in_left, in_right, mapping):
	if in_left > in_right:
		return None
	root = Node(level[0])
	in_idx = mapping[level[0]]
	left_level = []
	right_level = []
	for ele in level:
		idx = mapping[ele]
		if idx >= in_left and idx < in_idx:
			left_level.append(ele)
		elif idx > in_idx and idx <= in_right:
			right_level.append(ele)
	root.left = helper(left_level, ino, in_left, in_idx - 1, mapping)
	root.right = helper(right_level, ino, in_idx + 1, in_right, mapping)
	return root

def buildTree(level, ino):
	mapping = {}
	for ele in level:
		for i in range(len(ino)):
			if ino[i] == ele:
				mapping[ele] = i
				break
	return helper(level, ino, 0, len(ino) - 1, mapping)