Given a special binary tree having random pointers along with the usual left and right pointers. Clone the given tree.
Example 1:
Input:
Output: 1
Explanation: The tree was cloned successfully.
Your Task:
No need to read input or print anything. Complete the function cloneTree() which takes root of the given tree as input parameter and returns the root of the cloned tree. 
Note: The output is 1 if the tree is cloned successfully. Otherwise output is 0.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 ≤ Number of nodes ≤ 100
1 ≤ Data of a node ≤ 1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def cloneTree(self, tree):
        #code here

Solutions:
from collections import deque

class Solution:

	def cloneTree(self, tree):
		newMapp = {}
		oldMapp = {}
		Q = deque([tree])
		while Q:
			ptr = Q.popleft()
			oldMapp[ptr.data] = ptr
			newMapp[ptr.data] = Node(ptr.data)
			if ptr.left:
				Q.append(ptr.left)
			if ptr.right:
				Q.append(ptr.right)
		for (key, ptr) in oldMapp.items():
			if ptr.left:
				newMapp[key].left = newMapp[ptr.left.data]
			if ptr.right:
				newMapp[key].right = newMapp[ptr.right.data]
			if ptr.random:
				newMapp[key].random = newMapp[ptr.random.data]
		return newMapp[tree.data]


class Solution:

	def solve(self, root):
		if root == None:
			return
		new = Node(root.data)
		new.random = root.random
		new.left = self.solve(root.left)
		new.right = self.solve(root.right)
		return new

	def cloneTree(self, tree):
		return self.solve(tree)


class Solution:

	def cloneTree(self, tree):
		d = {}

		def node(tree):
			if not tree:
				return
			if tree not in d:
				root = Node(tree.data)
				d[tree] = root
			else:
				return d[tree]
			root.left = node(tree.left)
			root.right = node(tree.right)
			root.random = node(tree.random)
			return root
		return node(tree)


class Solution:

	def cloneTree(self, tree):
		oldToNew = {}

		def dfs(node):
			if not node:
				return
			if node in oldToNew:
				return node
			copy = Node(node.data)
			oldToNew[node] = copy
			copy.left = dfs(node.left)
			copy.right = dfs(node.right)
			copy.random = dfs(node.random)
			return copy
		return dfs(tree)


class Solution:

	def cloneTree(self, tree):
		s1 = set()

		def make_a_copy(root):
			if root == None:
				return None
			if root in s1:
				return root
			s1.add(root)
			nn = Node(root.data)
			nn.left = make_a_copy(root.left)
			nn.right = make_a_copy(root.right)
			nn.random = make_a_copy(root.random)
			return nn
		return make_a_copy(root)


class Solution:

	def io(self, a):
		if a:
			self.io(a.left)
			print(a.data, end=' ')
			self.io(a.right)

	def cloneTree(self, tree):
		visited = {}
		queue = [tree]
		g = Node(tree.data)
		queue1 = [g]
		while len(queue) > 0:
			x = queue.pop(0)
			y = queue1.pop(0)
			if x in visited:
				continue
			visited[x] = 1
			if x.left:
				y.left = Node(x.left.data)
				queue.append(x.left)
				queue1.append(y.left)
			if x.right:
				y.right = Node(x.right.data)
				queue.append(x.right)
				queue1.append(y.right)
			if x.random:
				y.random = Node(x.random.data)
				queue.append(x.random)
				queue1.append(y.random)
		return g


class Solution:

	def cloneTree(self, tree):

		def recursive(tree):
			if tree is None:
				return None
			cur = Node(tree.data)
			cur.left = recursive(tree.left)
			cur.right = recursive(tree.right)
			cur.random = tree.random
			return cur
		return recursive(tree)


class Solution:

	def cloneTree(self, root):
		myMap = {}

		def dfs(node):
			if not node:
				return
			if node not in myMap:
				clone = Node(node.data)
				myMap[node] = clone
			else:
				return myMap[node]
			clone.left = dfs(node.left)
			clone.right = dfs(node.right)
			clone.random = dfs(node.random)
			return clone
		return dfs(root)


class Solution:

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

	def connectrandom(self, root):
		if root == None:
			return
		root.left.random = root.random
		self.connectrandom(root.left.left)
		self.connectrandom(root.left.right)

	def clone(self, root, node):
		if root == None:
			return
		root.left = node.left
		if node.left:
			node.left = node.left.left
		if node.right:
			node.right = node.right.left
		self.clone(root.left, node.left)
		self.clone(root.right, node.right)

	def cloneTree(self, tree):
		self.makenode(tree)
		node = tree.left
		self.connectrandom(tree)
		self.clone(tree, node)
		return node


from collections import defaultdict

class Solution:

	def cloneTree(self, tree):
		d = {}

		def node(tree):
			if not tree:
				return
			if tree not in d:
				root = Node(tree.data)
				d[tree] = root
			else:
				return d[tree]
			root.left = node(tree.left)
			root.right = node(tree.right)
			root.random = node(tree.random)
			return root
		return node(tree)


class Solution:

	def helper(self, node1, node2):
		if node1 is None:
			return
		self.d1[node1] = node2
		if node1.left:
			node2.left = Node(node1.left.data)
			if node1.left.random:
				node2.left.random = self.d1[node1.left.random]
			self.helper(node1.left, node2.left)
		if node1.right:
			node2.right = Node(node1.right.data)
			if node1.right.random:
				node2.right.random = self.d1[node1.right.random]
			self.helper(node1.right, node2.right)

	def cloneTree(self, tree):
		if not tree:
			return None
		tree1 = Node(tree.data)
		self.d1 = {}
		self.helper(tree, tree1)
		return tree1

class Solution:

	def cloneTree(self, tree):
		d = {}

		def node(tree):
			if not tree:
				return
			if tree not in d:
				root = Node(tree.data)
				d[tree] = root
			else:
				return d[tree]
			root.left = node(tree.left)
			root.right = node(tree.right)
			root.random = node(tree.random)
			return root
		return node(tree)


class Solution:

	def inorder_data(self, root, ans):
		if root:
			self.inorder_data(root.left, ans)
			ans[root] = Node(root.data)
			self.inorder_data(root.right, ans)

	def inorder_ans(self, root, ans):
		if root:
			self.inorder_ans(root.left, ans)
			node = ans[root]
			node.random = ans.get(root.random)
			self.inorder_ans(root.right, ans)

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


class Solution:

	def preorder(self, root, po):
		if root is None:
			return
		po.append([root.data, root.left.data if root.left else -1, root.right.data if root.right else -1, root.random.data if root.random else -1])
		self.preorder(root.left, po)
		self.preorder(root.right, po)

	def dup_tree(self, po, idx, N, ht, rand):
		if idx[0] >= N:
			return
		i = idx[0]
		node = Node(po[i][0])
		if node.data in ht:
			ht[node.data].append(node)
		else:
			ht[node.data] = [node]
		if po[i][3] != -1:
			rand.append([node, po[i][3]])
		if po[i][1] != -1:
			idx[0] += 1
			node.left = self.dup_tree(po, idx, N, ht, rand)
		if po[i][2] != -1:
			idx[0] += 1
			node.right = self.dup_tree(po, idx, N, ht, rand)
		return node

	def cloneTree(self, tree):
		po = []
		ht = {}
		rand = []
		self.preorder(tree, po)
		root = self.dup_tree(po, [0], len(po), ht, rand)
		for r in rand:
			node = r[0]
			dnode = ht[r[1]][0]
			node.random = dnode
		return root


class Solution:

	def cloneTree(self, tree):
		mydic = dict()

		def dfs(node):
			if not node:
				return
			if node in mydic:
				return mydic[node]
			newNode = Node(node.data)
			mydic[node] = newNode
			newNode.left = dfs(node.left)
			newNode.right = dfs(node.right)
			newNode.random = dfs(node.random)
			return newNode
		return dfs(tree)


from collections import deque

class Solution:

	def cloneTree(self, tree):
		cloned = {}
		cloned[tree] = Node(tree.data)
		que = deque()
		que.append(tree)
		while que:
			cur = que.popleft()
			if cur.random and cur.random not in cloned:
				cloned[cur.random] = Node(cur.random.data)
				cloned[cur].random = cloned[cur.random]
			if cur.left:
				cloned[cur.left] = Node(cur.left.data)
				cloned[cur].left = cloned[cur.left]
				que.append(cur.left)
			if cur.right:
				cloned[cur.right] = Node(cur.right.data)
				cloned[cur].right = cloned[cur.right]
				que.append(cur.right)
		return cloned[tree]


class Solution:

	def cloneTree(self, tree):
		n = Node(tree.data)
		tq = [tree]
		rq = [n]
		visited = {}
		while len(tq) > 0:
			onode = tq.pop(0)
			nnode = rq.pop(0)
			if onode in visited:
				continue
			visited[onode] = True
			if onode.left != None:
				lnode = Node(onode.left.data)
				nnode.left = lnode
				if onode.left not in visited:
					tq.append(onode.left)
					rq.append(nnode.left)
			if onode.right != None:
				rnode = Node(onode.right.data)
				nnode.right = rnode
				if onode.right not in visited:
					tq.append(onode.right)
					rq.append(nnode.right)
			if onode.random != None:
				ranode = Node(onode.random.data)
				nnode.random = ranode
				if onode.random not in visited:
					tq.append(onode.random)
					rq.append(nnode.random)
		return n


class Solution:

	def cloneTree(self, tree):
		mapp = {}
		cloned_root = self.cloneUtil(tree, mapp)
		return cloned_root

	def cloneUtil(self, root, mapp):
		if root in mapp:
			return mapp[root]
		if not root:
			return
		node = Node(root.data)
		mapp[root] = node
		if root.left:
			mapp[root].left = self.cloneUtil(root.left, mapp)
		if root.right:
			mapp[root].right = self.cloneUtil(root.right, mapp)
		if root.random:
			mapp[root].random = self.cloneUtil(root.random, mapp)
		return mapp[root]


class Solution:

	def cloneTree(self, tree):
		dic = dict()

		def rec(nod):
			if nod is None:
				return None
			tem = Node(nod.data)
			tem.random = nod.random
			tem.left = rec(nod.left)
			tem.right = rec(nod.right)
			return tem
		root = rec(tree)
		return root


class Solution:

	def cloneTree(self, tree):
		dic = dict()

		def rec(nod):
			if nod is None:
				return None
			tem = Node(nod.data)
			dic[nod.data] = tem.data
			tem.left = rec(nod.left)
			tem.right = rec(nod.right)
			return tem
		root = rec(tree)

		def rec2(n, m):
			if n is None or m is None:
				return
			m.random = n.random
			rec2(n.left, m.left)
			rec2(n.right, m.right)
		rec2(tree, root)
		return root


class Solution:

	def clone_tree_util(self, root, mp):
		if root is None:
			return None
		if root in mp:
			return mp[root]
		cloned_node = Node(root.data)
		mp[root] = cloned_node
		cloned_node.left = self.clone_tree_util(root.left, mp)
		cloned_node.right = self.clone_tree_util(root.right, mp)
		cloned_node.random = self.clone_tree_util(root.random, mp)
		return cloned_node

	def cloneTree(self, tree):
		mp = {}
		return self.clone_tree_util(tree, mp)


class Solution:

	def traverse_tree(self, tree):
		self.c += 1
		tree.c = self.c
		if tree.left is not None:
			self.traverse_tree(tree.left)
		if tree.right is not None:
			self.traverse_tree(tree.right)

	def copy_recursively(self, tree):
		node = Node(data=tree.data)
		self.found[tree.data] = node
		if tree.left is not None:
			node.left = self.copy_recursively(tree.left)
		if tree.right is not None:
			node.right = self.copy_recursively(tree.right)
		return node

	def copy_random_pointer(self, tree, new_tree):
		if tree.random is not None:
			new_tree.random = self.found[tree.random.data]
		if tree.left is not None:
			self.copy_random_pointer(tree.left, new_tree.left)
		if tree.right is not None:
			self.copy_random_pointer(tree.right, new_tree.right)

	def cloneTree(self, tree):
		self.c = 0
		self.traverse_tree(tree)
		self.found = {}
		new_tree = self.copy_recursively(tree)
		self.c = 0
		self.copy_random_pointer(tree, new_tree)
		return new_tree


class Solution:

	def cloneTree(self, tree):
		if tree is None:
			return None
		hashMap = {}
		newTree = self.cloneTreeUtil(tree, hashMap)
		self.connectRandomTree(tree, newTree, hashMap)
		return newTree

	def cloneTreeUtil(self, tree, hashMap):
		if tree is None:
			return None
		newNode = Node(tree.data)
		hashMap[newNode.data] = newNode
		newNode.left = self.cloneTreeUtil(tree.left, hashMap)
		newNode.right = self.cloneTreeUtil(tree.right, hashMap)
		return newNode

	def connectRandomTree(self, tree, newTree, hashMap):
		if tree is None:
			return
		if tree.random:
			newTree.random = hashMap[tree.random.data]
		self.connectRandomTree(tree.left, newTree.left, hashMap)
		self.connectRandomTree(tree.right, newTree.right, hashMap)


from collections import defaultdict

class Solution:

	def cloneTree(self, root):
		hmap = defaultdict()

		def preOrder(n1):
			if not n1:
				return None
			if n1.data not in hmap:
				node = Node(n1.data)
				hmap[n1.data] = node
			else:
				node = hmap[n1.data]
			random_node = n1.random
			if random_node:
				if random_node.data in hmap:
					node.random = hmap[random_node.data]
				else:
					x = Node(random_node.data)
					hmap[random_node.data] = x
					node.random = x
			if n1.left:
				node.left = preOrder(n1.left)
			if n1.right:
				node.right = preOrder(n1.right)
			return node
		new_root = preOrder(root)
		return new_root


class Solution:

	def cloneTree(self, tree):
		if not tree:
			return None
		return self.dfs(tree, {})

	def dfs(self, root, oldToNew):
		if not root:
			return None
		if root in oldToNew:
			return oldToNew[root]
		newNode = Node(root.data)
		oldToNew[root] = newNode
		newNode.left = self.dfs(root.left, oldToNew)
		newNode.right = self.dfs(root.right, oldToNew)
		newNode.random = self.dfs(root.random, oldToNew)
		return newNode


class Solution:

	def cloneTree(self, tree):
		if not tree:
			return
		else:
			if not tree.left and (not tree.right):
				return tree
			root = Node(tree.data)
			root.random = tree.random
			root.left = self.cloneTree(tree.left)
			root.right = self.cloneTree(tree.right)
			return root


class Solution:

	def cloneTree(self, tree):
		if tree is None:
			return None
		tree_copy = Node(tree.data)
		tree_copy.left = self.cloneTree(tree.left)
		tree_copy.right = self.cloneTree(tree.right)
		tree_copy.random = self.cloneTree(tree.random)
		return tree_copy


class Solution:

	def cloneTree(self, tree):
		d = dict()

		def traversal(tree):
			if tree == None:
				return None
			if tree not in d:
				root = Node(tree.data)
				d[tree] = root
			else:
				return d[tree]
			root.left = traversal(tree.left)
			root.right = traversal(tree.right)
			root.random = traversal(tree.random)
			return root
		return traversal(tree)


class Solution:

	def c(self, h, he):
		if h == None:
			return
		self.ra[h] = h.random
		self.cl[h] = he
		if h.left == None and h.right == None:
			return
		if h.left is not None:
			he.left = Node(h.left.data)
			self.cl[h.left] = he.left
			self.c(h.left, he.left)
		if h.right is not None:
			he.right = Node(h.right.data)
			self.cl[h.right] = he.right
			self.c(h.right, he.right)

	def cloneTree(self, tree):
		self.cl = {}
		self.ra = {}
		he = Node(tree.data)
		self.c(tree, he)
		for i in self.ra:
			if self.ra[i] is not None:
				self.cl[i].random = self.ra[i]
		return he


class Solution:

	def cloneTree(self, tree):
		h = {}

		def func(tree):
			if not tree:
				return None
			if tree in h:
				return h[tree]
			root = Node(tree.data)
			h[tree] = root
			root.left = func(tree.left)
			root.right = func(tree.right)
			root.random = func(tree.random)
			return root
		return func(tree)


def fun(tree, d):
	if tree == None:
		return None
	if tree in d:
		pass
	else:
		root = Node(0)
		root.data = tree.data
		d[tree] = 1
		root.left = fun(tree.left, d)
		root.right = fun(tree.right, d)
		root.random = fun(tree.random, d)
		return root

class Solution:

	def cloneTree(self, tree):
		d = {}
		return fun(tree, d)


import copy

class Solution:

	def cloneTree(self, tree):
		return copy.deepcopy(tree)


class Solution:

	def cloneTree(self, tree):
		if not tree:
			return tree
		nodes = [tree]
		first = prev = Node(None)
		while nodes:
			new_nodes = []
			for node in nodes:
				prev.data = node.data
				prev.left = node.left
				prev.right = node.right
				prev.random = node.random
				if node.left:
					new_nodes.append(node.left)
				if node.right:
					new_nodes.append(node.right)
			nodes = new_nodes
			prev = Node(None)
		return first


class Solution:

	def cloneTree(self, tree):

		def _solve(nd):
			if not nd:
				return None
			nodes.append(nd)
			mp[nd.data] = new = Node(nd.data)
			new.left = _solve(nd.left)
			new.right = _solve(nd.right)
			return new
		nodes = []
		mp = {}
		new = _solve(tree)
		for o in nodes:
			if o.random is not None:
				mp[o.data].random = mp[o.random.data]
		return new


class Solution:

	def cloneTree(self, tree):
		if not tree:
			return
		if tree.left is None and tree.right is None:
			root = Node(tree.data)
			root.random = tree.random
			return root
		root = Node(tree.data)
		root.left = self.cloneTree(tree.left)
		root.right = self.cloneTree(tree.right)
		root.random = self.cloneTree(tree.random)
		return root


class Solution:

	def cloneLeftAndRight(self, node, cloneNode, visitedMap):
		visitedMap[node.data] = cloneNode
		if node.left:
			cloneNode.left = Node(node.left.data)
			self.cloneLeftAndRight(node.left, cloneNode.left, visitedMap)
		if node.right:
			cloneNode.right = Node(node.right.data)
			self.cloneLeftAndRight(node.right, cloneNode.right, visitedMap)

	def cloneRandom(self, node, cloneNode, visitedMap):
		if node.random is not None:
			cloneNode.random = visitedMap[node.random.data]
		if node.left:
			self.cloneRandom(node.left, cloneNode.left, visitedMap)
		if node.right:
			self.cloneRandom(node.right, cloneNode.right, visitedMap)

	def cloneTree(self, tree):
		visitedMap = {}
		cloneRoot = Node(tree.data)
		self.cloneLeftAndRight(tree, cloneRoot, visitedMap)
		self.cloneRandom(tree, cloneRoot, visitedMap)
		return cloneRoot


class Solution:

	def cloneTree(self, tree):
		d = {}

		def rec(x):
			if not x:
				return
			if x in d:
				return d[x]
			y = Node(x.data)
			d[x] = y
			y.left = rec(x.left)
			y.right = rec(x.right)
			y.random = rec(x.random)
			return y
		return rec(tree)


class Solution:

	def copy(self, root, hm):
		if not root:
			return None
		node = Node(root.data)
		hm[root] = node
		node.left = self.copy(root.left, hm)
		node.right = self.copy(root.right, hm)
		return node

	def assign_random(self, newroot, root, hm):
		if not root:
			return None
		root.random = hm[newroot.random]
		self.assign_random(newroot.left, root.left, hm)
		self.assign_random(newroot.right, root.right, hm)

	def cloneTree(self, tree):
		hm = {}
		hm[None] = None
		newtree = self.copy(tree, hm)
		self.assign_random(newtree, tree, hm)
		return newtree


class Solution:

	def copy(self, root, random, newptr):
		if not root:
			return
		node = Node(root.data)
		node.left = root.left
		node.right = root.right
		random[root.data] = root.random
		newptr[node.data] = node
		self.copy(root.left, random, newptr)
		self.copy(root.right, random, newptr)
		return node

	def assign_random(self, root, random, newptr):
		if not root:
			return
		if random[root.data]:
			newptr[root.data].random = newptr[random[root.data].data]
		self.assign_random(root.left, random, newptr)
		self.assign_random(root.right, random, newptr)

	def cloneTree(self, tree):
		random = {}
		newptr = {}
		root = self.copy(tree, random, newptr)
		self.assign_random(tree, random, newptr)
		return root


class Solution:

	def cloneTree(self, tree):

		def cloneTree(root):
			if not root:
				return
			clone = Node(root.data)
			clone.left = cloneTree(root.left)
			clone.right = cloneTree(root.right)
			clone.random = cloneTree(root.random)
			return clone
		return cloneTree(root)


class Solution:

	def clone(self, node, d):
		if not node:
			return None
		clone = Node(node.data)
		d[node] = clone
		clone.left = self.clone(node.left, d)
		clone.right = self.clone(node.right, d)
		return clone

	def copyr(self, node, clone, d):
		if not clone:
			return
		clone.random = d[node.random]
		self.copyr(node.left, clone.left, d)
		self.copyr(node.right, clone.right, d)

	def cloneTree(self, tree):
		if not tree:
			return None
		d = dict()
		d[None] = None
		clo = self.clone(tree, d)
		self.copyr(clo, tree, d)
		return clo


class Solution:

	def cloneTree(self, tree):
		visit = set()

		def dfs(root):
			if root == None:
				return
			if root in visit:
				return
			visit.add(root)
			copy = Node(root.data)
			copy.left = dfs(root.left)
			copy.right = dfs(root.right)
			copy.random = dfs(root.random)
			visit.remove(root)
			return copy
		return dfs(root)


class Solution:

	def copyLeftRightNode(self, node, mymap):
		if not node:
			return None
		cloneNode = Node(node.data)
		mymap[node] = cloneNode
		cloneNode.left = self.copyLeftRightNode(node.left, mymap)
		cloneNode.right = self.copyLeftRightNode(node.right, mymap)
		return cloneNode

	def copyRandom(self, node, cloneNode, mymap):
		if not cloneNode:
			return
		cloneNode.random = mymap[node.random]
		self.copyRandom(node.left, cloneNode.left, mymap)
		self.copyRandom(node.right, cloneNode.right, mymap)

	def cloneTree(self, tree):
		if not tree:
			return None
		mymap = dict()
		mymap[None] = None
		newTree = self.copyLeftRightNode(tree, mymap)
		self.copyRandom(newTree, tree, mymap)
		return newTree


class Solution:

	def cloneTree(self, tree):
		if tree:
			a = Node(tree.data)
			if tree.random:
				a.random = Node(tree.random.data)
			a.left = self.cloneTree(tree.left)
			a.right = self.cloneTree(tree.right)
			return a

class Node:

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

	def __str__(self):
		return str(self.data)

def printInord(a, b):
	if not a and (not b):
		return 1
	if a and b:
		t = int(a.data == b.data and printInord(a.left, b.left) and printInord(a.right, b.right))
		if a.random and b.random:
			return int(t and a.random.data == b.random.data)
		if a.random == b.random:
			return t
		return 0
	return 0
if __name__ == '__main__':
	tcs = int(input())
	for _ in range(tcs):
		map = dict()
		n = int(input())
		arrnode = [x for x in input().split()]
		root = None
		i = 0
		while i < 3 * n:
			(n1, n2, lr) = (int(arrnode[i]), int(arrnode[i + 1]), arrnode[i + 2])
			if n1 in map:
				parent = map[n1]
			else:
				parent = Node(n1)
				map[n1] = parent
				if not root:
					root = parent
			child = Node(n2)
			map[n2] = child
			if lr == 'R':
				parent.right = child
			elif lr == 'L':
				parent.left = child
			else:
				parent.random = map[n2]
			i += 3
		ansTree = Solution().cloneTree(root)
		if ansTree == root:
			print(0)
		else:
			print(int(printInord(root, ansTree)))


from collections import OrderedDict

class Solution:

	def cloneTree(self, tree):
		dic = OrderedDict()
		stack = [tree]
		head = ans = Node(tree.data)
		dic[tree] = ans
		stack1 = [ans]
		while True:
			(node, head) = (stack.pop(), stack1.pop())
			if node:
				stack.append(node.right)
				stack.append(node.left)
				if node.left and node.left in dic:
					head.left = dic[node.left]
				elif node.left:
					head.left = Node(node.left.data) if node.left else None
					dic[node.left] = head.left
				if node.right and node.right in dic:
					head.right = dic[node.right]
				elif node.right:
					head.right = Node(node.right.data) if node.right else None
					dic[node.right] = head.right
				if node.random and node.random in dic:
					head.random = dic[node.random]
				elif node.random:
					head.random = Node(node.random.data) if node.random else None
					dic[node.random] = head.random
				stack1.append(head.right)
				stack1.append(head.left)
			if not len(stack):
				break
		return ans

class Node:

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

	def __str__(self):
		return str(self.data)

def printInord(a, b):
	if not a and (not b):
		return 1
	if a and b:
		t = int(a.data == b.data and printInord(a.left, b.left) and printInord(a.right, b.right))
		if a.random and b.random:
			return int(t and a.random.data == b.random.data)
		if a.random == b.random:
			return t
		return 0
	return 0
if __name__ == '__main__':
	tcs = int(input())
	for _ in range(tcs):
		map = dict()
		n = int(input())
		arrnode = [x for x in input().split()]
		root = None
		i = 0
		while i < 3 * n:
			(n1, n2, lr) = (int(arrnode[i]), int(arrnode[i + 1]), arrnode[i + 2])
			if n1 in map:
				parent = map[n1]
			else:
				parent = Node(n1)
				map[n1] = parent
				if not root:
					root = parent
			child = Node(n2)
			map[n2] = child
			if lr == 'R':
				parent.right = child
			elif lr == 'L':
				parent.left = child
			else:
				parent.random = map[n2]
			i += 3
		ansTree = Solution().cloneTree(root)
		if ansTree == root:
			print(0)
		else:
			print(int(printInord(root, ansTree)))


class Solution:

	def cloneTree(self, root):
		mapp = {}
		root = self.cloneTreeUtil(root, mapp)
		return root

	def cloneTreeUtil(self, root, mapp):
		if not root:
			return None
		if root.data not in mapp:
			node = Node(root.data)
			mapp[node.data] = node
		if root.random:
			val = mapp.get(root.random.data, None)
			if not val:
				node.random = Node(root.random.data)
			else:
				node.random = val
		node.left = self.cloneTreeUtil(root.left, mapp)
		node.right = self.cloneTreeUtil(root.right, mapp)
		return node


class Solution:

	def cloneTree(self, tree):
		d = {}

		def helper(node):
			if node == None:
				return None
			clone = Node(node.data)
			d[node.data] = [node.random, clone]
			clone.left = helper(node.left)
			clone.right = helper(node.right)
			return clone
		ans = helper(tree)

		def traverse(node):
			if node == None:
				return None
			temp = d[node.data]
			if temp != None:
				node.random = temp[0]
			else:
				node.random = None
			traverse(node.left)
			traverse(node.right)
		traverse(ans)
		return ans


class Solution:

	def cloneTree(self, tree):
		root = Node(tree.data)
		qq = []
		qq.append(root)
		qq.append(None)
		hm = {}
		q = []
		q.append(tree)
		q.append(None)
		while q:
			temp = q.pop(0)
			curr = qq.pop(0)
			if temp == None and q:
				q.append(None)
				qq.append(None)
			elif temp == None and q == []:
				break
			else:
				if temp.left:
					q.append(temp.left)
					curr.left = Node(temp.left.data)
					qq.append(curr.left)
				if temp.right:
					q.append(temp.right)
					curr.right = Node(temp.right.data)
					qq.append(curr.right)
				hm[temp] = curr
		q.append(tree)
		q.append(None)
		qq.append(root)
		qq.append(None)
		while q:
			temp = q.pop(0)
			curr = qq.pop(0)
			if temp == None and q:
				q.append(None)
				qq.append(None)
			elif temp == None and q == []:
				break
			else:
				if temp.left:
					q.append(temp.left)
					qq.append(curr.left)
				if temp.right:
					q.append(temp.right)
					qq.append(curr.right)
				if temp.random:
					if hm.get(temp.random):
						curr.random = hm[temp.random]
					else:
						curr.random = Node(temp.random.data)
		return root


class Solution:

	def clone(self, root):
		if root is None:
			return None
		root_copy = Node(root.data)
		root_copy.left = self.clone(root.left)
		root_copy.right = self.clone(root.right)
		return root_copy

	def cloneRandom(self, clone_root, root):
		if root is None:
			return None
		clone_root.random = root.random
		self.cloneRandom(clone_root.left, root.left)
		self.cloneRandom(clone_root.right, root.right)
		return clone_root

	def cloneTree(self, tree):
		clone_root = self.clone(tree)
		main_root = self.cloneRandom(clone_root, tree)
		return main_root


class Solution:

	def clone(self, tree, dict):
		if tree != None:
			node = Node(tree.data)
			node.left = self.clone(tree.left, dict)
			node.right = self.clone(tree.right, dict)
			dict[node] = tree
			return node

	def cloneTree(self, tree):
		dict = {}
		node = self.clone(tree, dict)
		for i in dict.keys():
			i.random = dict[i].random
		return node


class Solution:

	def cloneTree(self, tree):
		a = Node(tree.data)
		d = {tree.data: a}
		rd = {}
		q = [tree]
		while q:
			c = q.pop(0)
			if c.left:
				q.append(c.left)
				d[c.data].left = Node(c.left.data)
				d[c.left.data] = d[c.data].left
			if c.right:
				q.append(c.right)
				d[c.data].right = Node(c.right.data)
				d[c.right.data] = d[c.data].right
			if c.random:
				rd[c.data] = c.random.data
		for k in rd:
			d[k].random = d[rd[k]]
		return a


class Solution:

	def cloneTree(self, tree):
		hashTable = {}
		if tree == None:
			return tree
		newRoot = self.preorder(tree, hashTable)
		for node in hashTable:
			if node.random not in hashTable:
				if node.random == None:
					hashTable[node].random = None
				else:
					hashTable[node].random = Node(node.random.data)
			else:
				hashTable[node].random = hashTable[node.random]
		return newRoot

	def preorder(self, root, hashTable):
		if root == None:
			return None
		newNode = Node(root.data)
		hashTable[root] = newNode
		newNode.left = self.preorder(root.left, hashTable)
		newNode.right = self.preorder(root.right, hashTable)
		return newNode


class Solution:

	def cloneTree(self, tree):
		root = self.clone(tree)
		return root

	def clone(self, root):
		if root is None:
			return None
		else:
			_node = Node(root.data)
			if root.random is not None:
				_node.random = Node(root.random.data)
			_node.left = self.clone(root.left)
			_node.right = self.clone(root.right)
			return _node


class Solution:

	def cloneTree(self, tree):
		mp = dict()
		s = []
		s.append(tree)
		while len(s) > 0:
			c = s.pop()
			temp = Node(c.data)
			mp[c.data] = temp
			if c.right:
				s.append(c.right)
			if c.left:
				s.append(c.left)
		s = []
		s.append(tree)
		while len(s) > 0:
			c = s.pop()
			if c.left:
				mp[c.data].left = mp[c.left.data]
				s.append(c.left)
			else:
				mp[c.data].left = None
			if c.right:
				mp[c.data].right = mp[c.right.data]
				s.append(c.right)
			else:
				mp[c.data].right = None
			if c.random:
				mp[c.data].random = mp[c.random.data]
			else:
				mp[c.data].random = None
		return mp[tree.data]


class Solution:

	def cloneTree(self, tree):
		if not tree:
			return
		temp = Node(tree.data)
		temp.left = self.cloneTree(tree.left)
		temp.right = self.cloneTree(tree.right)
		temp.random = tree.random
		return temp


class Solution:

	def cloneTree(self, tree, random=False):
		if tree is None:
			return None
		if random:
			return tree
		newNode = Node(tree.data)
		newNode.left = self.cloneTree(tree.left)
		newNode.right = self.cloneTree(tree.right)
		newNode.random = self.cloneTree(tree.random, random=True)
		return newNode


class Solution:

	def simple_clone(self, root):
		if root is None:
			return None
		else:
			new_root = Node(root.data)
			if root.random:
				new_root.random = Node(root.random.data)
			new_root.left = self.simple_clone(root.left)
			new_root.right = self.simple_clone(root.right)
		return new_root

	def cloneTree(self, root):
		new_root = self.simple_clone(root)
		return new_root


from collections import deque

class Solution:

	def cloneTree(self, tree):
		new_root = Node(tree.data)
		(new_root.left, new_root.right, new_root.random) = (tree.left, tree.right, tree.random)
		q = deque([tree])
		while q:
			n = len(q)
			for _ in range(n):
				node = q.popleft()
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
				if node.random == tree:
					node.random = new_root
		return new_root


def helper(root, d):
	if root:
		clone = Node(root.data)
		d[root.data] = [root.random, clone]
		clone.left = helper(root.left, d)
		clone.right = helper(root.right, d)
		return clone

def traverse(node, d):
	if node:
		temp = d[node.data]
		if temp[0] is not None:
			node.random = d[temp[0].data][1]
		else:
			node.random = None
		traverse(node.left, d)
		traverse(node.right, d)

class Solution:

	def cloneTree(self, root):
		if root:
			d = {}
			ans = helper(root, d)
			traverse(ans, d)
			return ans
		return


class Solution:

	def cloneTree(self, tree):
		if tree is None:
			return None
		hashMap = {}
		newTree = self.cloneTreeUtil(tree, hashMap)
		self.connectRandomPointer(tree, newTree, hashMap)
		return newTree

	def connectRandomPointer(self, tree, newTree, hashMap):
		if tree is None:
			return
		if tree.random:
			newRandom = hashMap[tree.random.data]
			newTree.random = newRandom
		self.connectRandomPointer(tree.left, newTree.left, hashMap)
		self.connectRandomPointer(tree.right, newTree.right, hashMap)

	def cloneTreeUtil(self, tree, hashMap):
		if tree is None:
			return
		newTree = Node(tree.data)
		hashMap[newTree.data] = newTree
		newTree.left = self.cloneTreeUtil(tree.left, hashMap)
		newTree.right = self.cloneTreeUtil(tree.right, hashMap)
		return newTree