Construct a binary tree of size N using two given arrays pre[] and preLN[]. Array pre[] represents preorder traversal of a binary tree. Array preLN[] has only two possible values L and N. The value L in preLN[] indicates that the corresponding node in Binary Tree is a leaf node and value N indicates that the corresponding node is a non-leaf node.
Note: Every node in the binary tree has either 0 or 2 children.
Example 1:
Input :      
N = 5
pre[] = {10, 30, 20, 5, 15}
preLN[] = {N, N, L, L, L}
Output:
          10
        /    \
      30      15
     /  \     
   20    5   
 
Your Task:  
You dont need to read input or print anything. Complete the function constructTree() which takes N, pre[] and preLN[] as input parameters and returns the root node of the constructed binary tree.
Note: The output generated by the compiler will contain the inorder traversal of the created binary tree.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{4}
1 ≤ pre[i] ≤ 10^{7}
preLN[i]: {'N', 'L'}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self,val):

        self.data = val

        self.left = None

        self.right = None

'''

def constructTree(pre, preLN, n):

    # code here

Solutions:
def solve(pre, preLN, n):
	if len(pre) == 0:
		return None
	root = Node(pre.pop(0))
	inst = preLN.pop(0)
	if inst == 'L':
		return root
	else:
		root.left = constructTree(pre, preLN, n - 1)
		root.right = constructTree(pre, preLN, n - 1)
	return root

def constructTree(pre, preLN, n):
	return solve(pre, preLN, n)


def constructTree(pre, preLN, n, i=0):
	root = Node(pre[i])
	if preLN[i] == 'N':
		hold = constructTree(pre, preLN, n, i + 1)
		if type(hold) != list:
			root.left = hold
			return root
		(root.left, i) = hold
		hold = constructTree(pre, preLN, n, i + 1)
		if type(hold) != list:
			root.right = hold
			return root
		(root.right, i) = hold
		return [root, i]
	elif preLN[i] == 'L':
		if i + 1 == n:
			return root
		return [root, i]
	else:
		print('7777777')


def solve(pre, preLN, n):
	root = Node(0)
	global i
	i += 1
	if i < n:
		root.data = pre[i]
		if preLN[i] == 'N':
			root.left = solve(pre, preLN, n)
			root.right = solve(pre, preLN, n)
	return root

def constructTree(pre, preLN, n):
	global i
	i = -1
	return solve(pre, preLN, n)


def solve(pre, preLN, n):
	root = None
	global i
	i += 1
	if i < n:
		root = Node(pre[i])
		if preLN[i] == 'N':
			root.left = solve(pre, preLN, n)
			root.right = solve(pre, preLN, n)
	return root

def constructTree(pre, preLN, n):
	global i
	i = -1
	return solve(pre, preLN, n)


def constructTree(pre, preLN, n):
	i = 0

	def rec():
		nonlocal i
		if i >= n:
			return None
		if preLN[i] == 'L':
			new = Node(pre[i])
			return new
		else:
			new = Node(pre[i])
			i += 1
			new.left = rec()
			i += 1
			new.right = rec()
			return new
	return rec()


def constructTree(pre, preLN, n):
	if n == 1:
		return Node(pre[0])

	def fun(pre, ln, n, i):
		if i[0] == n:
			return None
		root = Node(pre[i[0]])
		t = i[0]
		i[0] += 1
		if ln[t] == 'N':
			root.left = fun(pre, ln, n, i)
			root.right = fun(pre, ln, n, i)
		return root
	i = [0]
	return fun(pre, preLN, n, i)


def constructTree(pre, preLN, n):

	def helper(pre, preLN):
		if not pre:
			return None
		root = Node(pre.pop(0))
		if preLN.pop(0) == 'L':
			return root
		root.left = helper(pre, preLN)
		root.right = helper(pre, preLN)
		return root
	return helper(pre, preLN)


def Construct(pre, preLN, preindx, n):
	if preindx[0] >= n:
		return None
	root = Node(pre[preindx[0]])
	if preLN[preindx[0]] == 'L':
		preindx[0] += 1
		return root
	preindx[0] += 1
	root.left = Construct(pre, preLN, preindx, n)
	root.right = Construct(pre, preLN, preindx, n)
	return root

def constructTree(pre, preLN, n):
	preindx = [0]
	return Construct(pre, preLN, preindx, n)


def constructTree(pre, preLN, n):

	def _solve(i):
		nd = Node(pre[i])
		if preLN[i] == 'N':
			(nd.left, i) = _solve(i + 1)
			(nd.right, i) = _solve(i + 1)
		return (nd, i)
	(head, _) = _solve(0)
	return head


def constructTree(pre, preLN, n):

	def _solve(i):
		nd = Node(pre[i])
		isleaf = preLN[i] == 'L'
		if not isleaf:
			(nd.left, i) = _solve(i + 1)
			(nd.right, i) = _solve(i + 1)
		return (nd, i)
	(head, _) = _solve(0)
	return head


def constructTree(pre, preLN, n):
	pre.reverse()
	preLN.reverse()
	root = Node(pre.pop())
	if preLN.pop() == 'N':
		helper(pre, preLN, root)
	return root

def helper(pre, LN, root):
	root.left = Node(pre.pop())
	if LN.pop() == 'N':
		helper(pre, LN, root.left)
	root.right = Node(pre.pop())
	if LN.pop() == 'N':
		helper(pre, LN, root.right)
	return


from collections import deque

def make(root, nd):
	if root.left == None:
		root.left = nd
		return
	root.right = nd
	return

def constructTree(pre, preLN, n):
	root = Node(-1)
	current = root
	stack = deque()
	for i in range(n):
		nd = Node(pre[i])
		while stack and current.left and current.right:
			current = stack.pop()
		make(current, nd)
		if preLN[i] == 'N':
			stack.append(current)
			current = nd
	return root.left


class Solution:

	def __init__(self):
		self.c = 0

	def construct(self, a, b):
		if self.c == len(a):
			return None
		g = Node(a[self.c])
		if b[self.c] == 'L':
			return g
		else:
			self.c += 1
			g.left = self.construct(a, b)
			self.c += 1
			g.right = self.construct(a, b)
			return g

def constructTree(pre, preLN, n):
	o = Solution()
	return o.construct(pre, preLN)


def make_tree(pre, preln):
	if not pre or not preln:
		return None
	t = preln.pop(0)
	if t == 'L':
		return Node(pre.pop(0))
	node = Node(pre.pop(0))
	node.left = make_tree(pre, preln)
	node.right = make_tree(pre, preln)
	return node

def constructTree(pre, preLN, n):
	return make_tree(pre, preLN)


def constructTree(pre, preLN, n):
	index = [0]

	def build():
		if index[0] == n:
			return None
		node = Node(pre[index[0]])
		index[0] += 1
		if preLN[index[0] - 1] == 'N':
			node.left = build()
			node.right = build()
		return node
	root = build()
	return root


import queue

def rev_preorder(root, pre, preLN, idx):
	if root is None:
		return
	if root.left is None:
		i = idx[0]
		idx[0] += 1
		root.left = Node(pre[i])
		if preLN[i] != 'L':
			rev_preorder(root.left, pre, preLN, idx)
	if root.right is None:
		i = idx[0]
		idx[0] += 1
		root.right = Node(pre[i])
		if preLN[i] != 'L':
			rev_preorder(root.right, pre, preLN, idx)

def constructTree(pre, preLN, n):
	root = Node(pre[0])
	if preLN[0] == 'L':
		return root
	rev_preorder(root, pre, preLN, [1])
	return root


def constructTree(pre, arr, n):
	st = []
	root = None
	for i in range(n):
		node = Node(pre[i])
		if root is None:
			root = node
		if arr[i] == 'N':
			if st != []:
				if st[-1].left is None:
					st[-1].left = node
				else:
					st[-1].right = node
					st.pop()
			st.append(node)
		elif st[-1].left is None:
			st[-1].left = node
		else:
			st[-1].right = node
			st.pop()
	return root


def treeConstruction(pre, leafNodeMap):
	if len(pre):
		root = Node(pre.pop(0))
		if leafNodeMap[root.data] == 'N':
			root.left = treeConstruction(pre, leafNodeMap)
			root.right = treeConstruction(pre, leafNodeMap)
		return root
	return

def constructTree(pre, preLN, n):
	if n < 1 or not len(pre):
		return
	leafNodeMap = {pre[index]: preLN[index] for index in range(len(preLN))}
	return treeConstruction(pre, leafNodeMap)


def construct(pre, preLN, a):
	if a[0] < len(pre):
		root = Node(pre[a[0]])
		if preLN[a[0]] == 'N':
			a[0] += 1
			root.left = construct(pre, preLN, a)
			a[0] += 1
			root.right = construct(pre, preLN, a)
	return root

def constructTree(pre, preLN, n):
	a = [0]
	return construct(pre, preLN, a)


i = 0

def constructTree(pre, preLN, n):
	global i
	i = 0
	root = constructTreeUtil(pre, preLN, n)
	return root

def constructTreeUtil(pre, preLN, n):
	global i
	if i >= n:
		return
	root = Node(pre[i])
	i += 1
	if preLN[i - 1] == 'N':
		root.left = constructTreeUtil(pre, preLN, n)
		root.right = constructTreeUtil(pre, preLN, n)
	return root


def constructTree(pre, preLN, n):
	stack = []
	tree = Node(pre[0])
	if preLN[0] == 'L':
		return tree
	node = tree
	stack.append(node)
	for i in range(1, n):
		if preLN[i - 1] == 'N':
			node.left = Node(pre[i])
			if preLN[i] == 'N':
				stack.append(node.left)
			node = node.left
		else:
			node = stack.pop()
			node.right = Node(pre[i])
			if preLN[i] == 'N':
				stack.append(node.right)
			node = node.right
	return tree


class newNode:

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

def constructTreeUtil(pre, preLN, index_ptr, n):
	index = index_ptr[0]
	if index == n:
		return None
	temp = newNode(pre[index])
	index_ptr[0] += 1
	if preLN[index] == 'N':
		temp.left = constructTreeUtil(pre, preLN, index_ptr, n)
		temp.right = constructTreeUtil(pre, preLN, index_ptr, n)
	return temp

def constructTree(pre, preLN, n):
	index = [0]
	return constructTreeUtil(pre, preLN, index, n)


def func(pre, arr, idx_arr, n):
	idx = idx_arr[0]
	if idx == n:
		return None
	temp = Node(pre[idx])
	idx_arr[0] += 1
	if arr[idx] == 'N':
		temp.left = func(pre, arr, idx_arr, n)
		temp.right = func(pre, arr, idx_arr, n)
	return temp

def constructTree(pre, arr, n):
	idx_arr = [0]
	return func(pre, arr, idx_arr, n)

def constructTreeIter(pre, arr, n):
	st = []
	root = None
	for i in range(n):
		ele = arr[i]
		node = Node(pre[i])
		if root is None:
			root = node
		if ele == 'N':
			st.append(node)
		elif st[-1].left is not None:
			st[-1].left = node
		elif st[-1].right is not None:
			st[-1].right = node
		while st[-1].left is not None and st[-1].right is not None:
			temp = st.pop()
			if st == []:
				break
			if st[-1].left is not None:
				st[-1].left = temp
			elif st[-1].right is not None:
				st[-1].right = temp
	return root


def constructTree(pre, preLN, n):
	if n == 0:
		return None
	idx = [0]
	return constructTreeUtil(pre, preLN, n, idx)

def constructTreeUtil(pre, preLN, n, idx):
	if idx[0] == n:
		return
	index = idx[0]
	node = Node(pre[index])
	idx[0] += 1
	if preLN[index] == 'N':
		node.left = constructTreeUtil(pre, preLN, n, idx)
		node.right = constructTreeUtil(pre, preLN, n, idx)
	return node


def Create_a_tree(pre, preRQ, index):
	if index == len(pre):
		return (None, index)
	tree = Node(pre[index])
	tree_type = preRQ[index]
	index = index + 1
	if tree_type == 'N':
		(tree.left, index) = Create_a_tree(pre, preRQ, index)
		(tree.right, index) = Create_a_tree(pre, preRQ, index)
	return (tree, index)

def constructTree(pre, preLN, n):
	index = 0
	(root, idx) = Create_a_tree(pre, preLN, index)
	return root


def rec_build_tree(pre, preLN, idx):
	if idx == len(pre):
		return (None, idx)
	root = Node(pre[idx])
	root_type = preLN[idx]
	idx += 1
	if root_type == 'N':
		(root.left, idx) = rec_build_tree(pre, preLN, idx)
		(root.right, idx) = rec_build_tree(pre, preLN, idx)
	return (root, idx)

def constructTree(pre, preLN, n):
	idx = 0
	(root, _) = rec_build_tree(pre, preLN, idx)
	return root


def constructTree_(pre, preLN, i):
	if i > len(pre):
		return (None, 0)
	new_node = Node(pre[i])
	start_i = i
	if preLN[i] == 'N':
		(left, next_i) = constructTree_(pre, preLN, i + 1)
		i += next_i
		(right, next_i) = constructTree_(pre, preLN, i + 1)
		i += next_i
		new_node.left = left
		new_node.right = right
	return (new_node, i - start_i + 1)

def constructTree(pre, preLN, n):
	(out, _) = constructTree_(pre, preLN, 0)
	return out


class TreeNode:

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

class Solution:

	def __init__(self) -> None:
		self.curr_idx = 0

	def specialPre(self, preorder, metainfo):
		if metainfo[self.curr_idx] == 'L':
			new_node = TreeNode(preorder[self.curr_idx])
			self.curr_idx += 1
			return new_node
		root = TreeNode(preorder[self.curr_idx])
		self.curr_idx += 1
		root.left = self.specialPre(preorder, metainfo)
		root.right = self.specialPre(preorder, metainfo)
		return root

	def buildTree(self, preorder, metainfo):
		return self.specialPre(preorder, metainfo)

def constructTree(pre, preLN, n):
	sol = Solution()
	return sol.buildTree(pre, preLN)


def constructTree(pre, preLN, n):
	idx = [0]

	def rec():
		if idx[0] >= n:
			return None
		node = Node(pre[idx[0]])
		idx[0] += 1
		if preLN[idx[0] - 1] == 'L':
			return node
		node.left = rec()
		node.right = rec()
		return node
	return rec()


def func(pre, arr, idx_arr, n):
	idx = idx_arr[0]
	if idx == n:
		return None
	temp = Node(pre[idx])
	idx_arr[0] += 1
	if arr[idx] == 'N':
		temp.left = func(pre, arr, idx_arr, n)
		temp.right = func(pre, arr, idx_arr, n)
	return temp

def constructTree(pre, arr, n):
	idx_arr = [0]
	return func(pre, arr, idx_arr, n)


def f(pre, preLN, indx, n):
	idx = indx[0]
	if idx == n:
		return
	tree = Node(pre[idx])
	indx[0] += 1
	if preLN[idx] == 'N':
		tree.left = f(pre, preLN, indx, n)
		tree.right = f(pre, preLN, indx, n)
	return tree

def constructTree(pre, preLN, n):
	indx = [0]
	return f(pre, preLN, indx, n)


def f(pre, preLN, index, N):
	idx = index[0]
	if idx == N:
		return None
	temp = Node(pre[idx])
	index[0] += 1
	if preLN[idx] == 'N':
		temp.left = f(pre, preLN, index, N)
		temp.right = f(pre, preLN, index, N)
	return temp

def constructTree(pre, preLN, n):
	index = [0]
	return f(pre, preLN, index, n)


def build(pre, LN, n, irr):
	i = irr[0]
	if i == n:
		return None
	node = Node(pre[i])
	if LN[i] == 'N':
		irr[0] += 1
		node.left = build(pre, LN, n, irr)
		irr[0] += 1
		node.right = build(pre, LN, n, irr)
	return node

def constructTree(pre, preLN, n):
	irr = [0]
	return build(pre, preLN, n, irr)


def constructTree(pre, preLN, n):
	t = Node(pre[0])
	stack = [t]
	for i in range(1, len(pre)):
		while stack and stack[-1].left and stack[-1].right:
			stack.pop()
		nd = Node(pre[i])
		if not stack[-1].left:
			stack[-1].left = nd
		else:
			stack[-1].right = nd
		if preLN[i] == 'N':
			stack.append(nd)
	return t


def constructTree(pre, preLN, n):

	def solve(pre, preLN, n, i):
		index = i[0]
		if index >= n:
			return None
		newNode = Node(pre[index])
		i[0] += 1
		if preLN[index] == 'N':
			newNode.left = solve(pre, preLN, n, i)
			newNode.right = solve(pre, preLN, n, i)
		return newNode
	if n < 1 or not len(pre):
		return
	i = [0]
	return solve(pre, preLN, n, i)


def constructTree(pre, preLN, n):
	i = [0]

	def dfs():
		if preLN[i[0]] == 'L':
			node = Node(pre[i[0]])
			i[0] += 1
			return node
		node = Node(pre[i[0]])
		i[0] += 1
		node.left = dfs()
		node.right = dfs()
		return node
	return dfs()


def constructTree(pre, preLN, n):
	idx = [0]

	def helper():
		i = idx[0]
		if i == n:
			return None
		root = Node(pre[i])
		idx[0] += 1
		if preLN[i] == 'N':
			root.left = helper()
			root.right = helper()
		return root
	return helper()


def fun(pre, preLN, idx, n):
	if idx[0] >= n:
		return
	elif preLN[idx[0]] == 'L':
		temp = Node(pre[idx[0]])
		idx[0] += 1
		return temp
	else:
		root = Node(pre[idx[0]])
		ans = root
		idx[0] += 1
		root.left = fun(pre, preLN, idx, n)
		root.right = fun(pre, preLN, idx, n)
		return ans

def constructTree(pre, preLN, n):
	idx = [0]
	return fun(pre, preLN, idx, n)


def fullTree(pre, preLn, indepre, indxpreLn):
	if indepre == len(pre):
		return
	node = Node(pre[indepre[0]])
	indepre[0] += 1
	if indepre[0] == len(pre):
		return node
	if preLn[indxpreLn[0]] != 'L':
		indxpreLn[0] += 1
		node.left = fullTree(pre, preLn, indepre, indxpreLn)
		indxpreLn[0] += 1
		node.right = fullTree(pre, preLn, indepre, indxpreLn)
	return node

def constructTree(pre, preLN, n):
	tree = fullTree(pre, preLN, [0], [0])
	return tree


def constructTree(pre, preLN, n):

	def util(pre, preLN, i, n):
		index = i[0]
		if index == n:
			return None
		node = Node(pre[index])
		i[0] += 1
		if preLN[index] == 'N':
			node.left = util(pre, preLN, i, n)
			node.right = util(pre, preLN, i, n)
		return node
	i = [0]
	return util(pre, preLN, i, n)


def constructTree(pre, preLN, n):
	stack = []
	for (val, ln) in zip(pre, preLN):
		if ln == 'N':
			stack.append(Node(val))
		else:
			cur = Node(val)
			while stack:
				if not stack[-1].left:
					stack[-1].left = cur
					break
				elif not stack[-1].right:
					stack[-1].right = cur
					cur = stack[-1]
					stack.pop()
			if not stack:
				return cur


def constructTree(pre, preLN, n):
	i = 0

	def solve(pre, ln):
		nonlocal i
		if i < len(pre):
			root = Node(pre[i])
			if ln[i] == 'L':
				return root
			i += 1
			root.left = solve(pre, ln)
			i += 1
			root.right = solve(pre, ln)
			return root
	if n == 0:
		return None
	return solve(pre, preLN)


def constructTree(pre, preLN, n):
	index = [0]
	return constructTreeUtil(pre, preLN, index, n)

def constructTreeUtil(pre, preLN, index_ptr, n):
	index = index_ptr[0]
	if index == n:
		return None
	temp = Node(pre[index])
	index_ptr[0] += 1
	if preLN[index] == 'N':
		temp.left = constructTreeUtil(pre, preLN, index_ptr, n)
		temp.right = constructTreeUtil(pre, preLN, index_ptr, n)
	return temp


def constructTree(pre, preLN, n):
	index = [0]
	return helper(pre, preLN, index, n)

def helper(pre, preLN, inptr, n):
	index = inptr[0]
	if index == n:
		return None
	temp = Node(pre[index])
	inptr[0] += 1
	if preLN[index] == 'N':
		temp.left = helper(pre, preLN, inptr, n)
		temp.right = helper(pre, preLN, inptr, n)
	return temp


def constructTree(pre, preLN, n):
	index = 0

	def construct(pre, preLN):
		nonlocal index
		if preLN[index] == 'L':
			root = Node(pre[index])
			index += 1
			return root
		root = Node(pre[index])
		index += 1
		root.left = construct(pre, preLN)
		root.right = construct(pre, preLN)
		return root
	return construct(pre, preLN)


def constructTree(pre, preLN, n):
	pre_index = [0]
	return solve(pre, preLN, pre_index, n)

def solve(pre, preLN, pre_index, n):
	if pre_index[0] >= n:
		return
	root_val = pre[pre_index[0]]
	root_node = Node(root_val)
	status = preLN[pre_index[0]]
	pre_index[0] += 1
	if status == 'L':
		return root_node
	root_node.left = solve(pre, preLN, pre_index, n)
	root_node.right = solve(pre, preLN, pre_index, n)
	return root_node


def constructTree(pre, preLN, n):
	global i
	i = 0

	def solve():
		global i
		node = Node(pre[i])
		if preLN[i] == 'L':
			i += 1
			return node
		i += 1
		node.left = solve()
		node.right = solve()
		return node
	return solve()


def constructTree(pre, preLN, n):

	def create(arr, ln, i):
		if i[0] >= len(pre):
			return None
		nn = Node(arr[i[0]])
		if ln[i[0]] == 'L':
			return nn
		else:
			i[0] += 1
			lv = create(arr, ln, i)
			i[0] += 1
			rv = create(arr, ln, i)
			nn.left = lv
			nn.right = rv
			return nn
	i = [0]
	return create(pre, preLN, i)


def constructTree(pre, preLN, n):

	def check(pre, preLN, idx, n):
		i = idx[0]
		if i == n:
			return False
		root = Node(pre[i])
		idx[0] += 1
		if preLN[i] == 'N':
			root.left = check(pre, preLN, idx, n)
			root.right = check(pre, preLN, idx, n)
		return root
	idx = [0]
	return check(pre, preLN, idx, n)


def constructTree(pre, preLN, n):
	if len(pre) == 0:
		return None
	n -= 1
	root = Node(pre.pop(0))
	type = preLN.pop(0)
	if type == 'L':
		return root
	left_tree_node = constructTree(pre, preLN, n)
	right_tree_node = constructTree(pre, preLN, n)
	root.left = left_tree_node
	root.right = right_tree_node
	return root


def constructTree(pre, preLN, n):
	i = -1

	def code(n):
		nonlocal i
		i += 1
		if i == n:
			return
		if preLN[i] == 'L':
			root = Node(pre[i])
			return root
		root = Node(pre[i])
		root.left = code(n)
		root.right = code(n)
		return root
	return code(n)


def buildtree(pre, preLN, n, idx):
	i = idx[0]
	if i == n:
		return None
	root = Node(pre[i])
	idx[0] = idx[0] + 1
	if preLN[i] == 'N':
		root.left = buildtree(pre, preLN, n, idx)
		root.right = buildtree(pre, preLN, n, idx)
	return root

def constructTree(pre, preLN, n):
	idx = [0]
	Tree = buildtree(pre, preLN, n, idx)
	return Tree

class Node:

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

def printInorder(root):
	if not root:
		return
	printInorder(root.left)
	print(root.data, end=' ')
	printInorder(root.right)
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		n = int(input())
		pre = list(map(int, input().strip().split()))
		preln = list(map(str, input().strip().split()))
		root = constructTree(pre, preln, n)
		printInorder(root)
		print()


def constructTreeUtil(pre, preLN, index_ptr, n):
	index = index_ptr[0]
	if index == n:
		return None
	temp = Node(pre[index])
	index_ptr[0] += 1
	if preLN[index] == 'N':
		temp.left = constructTreeUtil(pre, preLN, index_ptr, n)
		temp.right = constructTreeUtil(pre, preLN, index_ptr, n)
	return temp

def constructTree(pre, preLN, n):
	index = [0]
	return constructTreeUtil(pre, preLN, index, n)

class Node:

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

def printInorder(root):
	if not root:
		return
	printInorder(root.left)
	print(root.data, end=' ')
	printInorder(root.right)
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		n = int(input())
		pre = list(map(int, input().strip().split()))
		preln = list(map(str, input().strip().split()))
		root = constructTree(pre, preln, n)
		printInorder(root)
		print()


index = 0

class Node:

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

def constructTree(pre, preLN, n):
	if n < 1 or not len(pre):
		return
	leafNodeMap = {pre[index]: preLN[index] for index in range(len(preLN))}
	return treeConstruction(pre, leafNodeMap)

def treeConstruction(pre, leafNodeMap):
	if len(pre):
		root = Node(pre.pop(0))
		if leafNodeMap[root.data] == 'N':
			root.left = treeConstruction(pre, leafNodeMap)
			root.right = treeConstruction(pre, leafNodeMap)
		return root
	return

class Node:

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

def printInorder(root):
	if not root:
		return
	printInorder(root.left)
	print(root.data, end=' ')
	printInorder(root.right)
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		n = int(input())
		pre = list(map(int, input().strip().split()))
		preln = list(map(str, input().strip().split()))
		root = constructTree(pre, preln, n)
		printInorder(root)
		print()


def incremnt_counter():
	constructTree.count = constructTree.count + 1

def get_static_count():
	return constructTree.count

def solve(pre, preNL, n, i):
	i = get_static_count()
	if i == n:
		return None
	temp = Node(pre[i])
	incremnt_counter()
	if preNL[i] == 'N':
		temp.left = solve(pre, preNL, n, i)
		temp.right = solve(pre, preNL, n, i)
	return temp

def constructTree(pre, preLN, n):
	constructTree.count = 0
	return solve(pre, preLN, n, constructTree.count)

class Node:

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

def printInorder(root):
	if not root:
		return
	printInorder(root.left)
	print(root.data, end=' ')
	printInorder(root.right)
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		n = int(input())
		pre = list(map(int, input().strip().split()))
		preln = list(map(str, input().strip().split()))
		root = constructTree(pre, preln, n)
		printInorder(root)
		print()


def constructTree_util(pre, preLN, n, index):
	ind = index[0]
	if index[0] == n:
		return None
	root = Node(pre[ind])
	index[0] += 1
	if preLN[ind] == 'L':
		return root
	root.left = constructTree_util(pre, preLN, n, index)
	root.right = constructTree_util(pre, preLN, n, index)
	return root

def constructTree(pre, preLN, n):
	index = [0]
	return constructTree_util(pre, preLN, n, index)

class Node:

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

def printInorder(root):
	if not root:
		return
	printInorder(root.left)
	print(root.data, end=' ')
	printInorder(root.right)
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		n = int(input())
		pre = list(map(int, input().strip().split()))
		preln = list(map(str, input().strip().split()))
		root = constructTree(pre, preln, n)
		printInorder(root)
		print()


def constructTree(pre, preLN, n):

	def solve(pre, preLN):
		nonlocal ind
		if ind >= len(pre):
			return None
		root = Node(pre[ind])
		ln = preLN[ind]
		ind += 1
		if preLN[ind - 1] == 'N':
			root.left = solve(pre, preLN)
			root.right = solve(pre, preLN)
		return root
	ind = 0
	return solve(pre, preLN)

class Node:

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

def printInorder(root):
	if not root:
		return
	printInorder(root.left)
	print(root.data, end=' ')
	printInorder(root.right)
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		n = int(input())
		pre = list(map(int, input().strip().split()))
		preln = list(map(str, input().strip().split()))
		root = constructTree(pre, preln, n)
		printInorder(root)
		print()


def constructTree(pre, preLN, n):
	root = Node(pre[0])
	k = [root]
	N = root
	for i in range(1, n):
		c = Node(pre[i])
		if N:
			N.left = c
		else:
			k.pop().right = c
		if preLN[i] == 'N':
			N = c
			k.append(c)
		else:
			N = None
	return root

class Node:

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

def printInorder(root):
	if not root:
		return
	printInorder(root.left)
	print(root.data, end=' ')
	printInorder(root.right)
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		n = int(input())
		pre = list(map(int, input().strip().split()))
		preln = list(map(str, input().strip().split()))
		root = constructTree(pre, preln, n)
		printInorder(root)
		print()


def constructTree(pre, preLN, n):
	pre_index = [0]
	return solve(pre, preLN, n, pre_index)

def solve(pre, preLN, n, pre_index):
	if pre_index[0] >= n:
		return None
	root = pre[pre_index[0]]
	root_node = Node(root)
	status = preLN[pre_index[0]]
	pre_index[0] += 1
	if status == 'L':
		return root_node
	root_node.left = solve(pre, preLN, n, pre_index)
	root_node.right = solve(pre, preLN, n, pre_index)
	return root_node

class Node:

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

def printInorder(root):
	if not root:
		return
	printInorder(root.left)
	print(root.data, end=' ')
	printInorder(root.right)
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		n = int(input())
		pre = list(map(int, input().strip().split()))
		preln = list(map(str, input().strip().split()))
		root = constructTree(pre, preln, n)
		printInorder(root)
		print()


def constructTree(pre, preLN, n):
	if len(pre) == 1:
		return Node(pre[0])
	idx = [0]
	n = len(pre)
	root = buildTree(pre, preLN, idx, n)
	return root

def buildTree(pre, preLN, idx, n):
	ind = idx[0]
	if ind >= n:
		return
	root = Node(pre[ind])
	idx[0] += 1
	if preLN[ind] == 'N':
		root.left = buildTree(pre, preLN, idx, n)
		root.right = buildTree(pre, preLN, idx, n)
	return root


class temp:

	def __init__(self):
		self.i = 0

def fun(pre, preLN, obj):
	root = Node(pre[obj.i])
	obj.i = obj.i + 1
	if preLN[obj.i - 1] == 'L':
		root.left = None
		root.right = None
		return root
	else:
		root.left = fun(pre, preLN, obj)
		root.right = fun(pre, preLN, obj)
		return root

def constructTree(pre, preLN, n):
	obj = temp()
	root = fun(pre, preLN, obj)
	return root


def constructTree(pre, preLN, n):
	node_stack = []
	prev_sign = ' '
	for index in range(0, len(pre)):
		cur_node = Node(pre[index])
		if index == 0:
			node_stack.append(cur_node)
			continue
		track_back = index - 1
		prev_node = node_stack[track_back]
		while preLN[track_back] == 'L' or (prev_node.left is not None and prev_node.right is not None):
			track_back -= 1
			prev_node = node_stack[track_back]
		if prev_node.left is None:
			prev_node.left = cur_node
		elif prev_node.right is None:
			prev_node.right = cur_node
		node_stack.append(cur_node)
	return node_stack[0]

class Node:

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

def printInorder(root):
	if not root:
		return
	printInorder(root.left)
	print(root.data, end=' ')
	printInorder(root.right)
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		n = int(input())
		pre = list(map(int, input().strip().split()))
		preln = list(map(str, input().strip().split()))
		root = constructTree(pre, preln, n)
		printInorder(root)
		print()


def constructTree(pre, preLN, n):

	def rec():
		nonlocal i
		if i == len(pre):
			return None
		root = Node(pre[i])
		if preLN[i] == 'N':
			i += 1
			root.left = rec()
			i += 1
			root.right = rec()
		return root
	i = 0
	return rec()


def helper(pre, d):
	if len(pre):
		root = Node(pre.pop(0))
		if d[root.data] == 'N':
			root.left = helper(pre, d)
			root.right = helper(pre, d)
		return root
	return

def constructTree(pre, preLN, n):
	if n < 1:
		return
	d = {pre[i]: preLN[i] for i in range(n)}
	return helper(pre, d)


def solve(arr, brr):
	if arr[brr[0]] == -1:
		brr[0] += 1
		return None
	root = Node(arr[brr[0]])
	brr[0] += 1
	root.left = solve(arr, brr)
	root.right = solve(arr, brr)
	return root

def constructTree(pre, preLN, n):
	arr = []
	for i in range(n):
		arr.append(pre[i])
		if preLN[i] == 'L':
			arr.append(-1)
			arr.append(-1)
	brr = [0]
	root = solve(arr, brr)
	return root


def constructTree(pre, preLN, n):

	def solve():
		if pre == []:
			return None
		node = Node(pre.pop(0))
		ty = preLN.pop(0)
		if ty == 'N':
			node.left = solve()
			node.right = solve()
			return node
		else:
			return node
	return solve()


def constructTree(pre, preLN, n):
	index = [0]
	root = Util(pre, preLN, n, index)
	if root is None:
		print('None')
	return root

def Util(pre, preLN, n, index):
	if index[0] >= n:
		return None
	newNode = Node(pre[index[0]])
	if preLN[index[0]] == 'L':
		return newNode
	index[0] += 1
	newNode.left = Util(pre, preLN, n, index)
	index[0] += 1
	newNode.right = Util(pre, preLN, n, index)
	return newNode


def constructTree(pre, preLN, n):
	if len(pre) == 0:
		return None
	type = preLN.pop(0)
	if type == 'L':
		root = Node(pre.pop(0))
		return root
	if type == 'N':
		root = Node(pre.pop(0))
		root.left = constructTree(pre, preLN, n)
		root.right = constructTree(pre, preLN, n)
		return root


def constructTree(pre, preLN, n):
	(root, _) = buildTree(pre, preLN, 0)
	return root

def buildTree(pre, preLN, i):
	if i > len(pre):
		return (None, i)
	node = Node(pre[i])
	if preLN[i] == 'N':
		(node.left, i) = buildTree(pre, preLN, i + 1)
		(node.right, i) = buildTree(pre, preLN, i + 1)
		return (node, i)
	else:
		return (node, i)


class Node:

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

def constructTree(pre, preLN, n):
	root = Node(pre[0])
	if preLN[0] == 'L':
		stack = []
	else:
		stack = [root]
		for i in range(1, n):
			if preLN[i] == 'N':
				prev = stack[-1]
				curr = Node(pre[i])
				if prev.left == None:
					prev.left = curr
				elif prev.right == None:
					prev.right = curr
					stack.pop()
				stack.append(curr)
			if preLN[i] == 'L':
				prev = stack[-1]
				curr = Node(pre[i])
				if prev.left == None:
					prev.left = curr
				else:
					temp = stack.pop()
					if temp.right == None:
						temp.right = curr
	return root