Given the binary Tree of and two-node values. Check whether the two-node values are cousins of each other or not.
Example 1:
Input:
      1
    /   \
   2     3
a = 2, b = 3
Output: 0
Example 2:
Input:
       1
     /   \ 
    2     3
   /       \
  5         4 
a = 5, b = 4
Output: 1
Explanation: Here, nodes 5 and 4 are
at the same level and have different
parent nodes. Hence, they both are cousins 
Your Task:
You don't need to read input or print anything. Your task is to complete the function isCousins() that takes the root node of the tree (having all nodes distinct), and two integers 'a' and 'b' as inputs. It returns true if the nodes with given values 'a' and 'b' are Cousins of each other and returns false otherwise. 
Two nodes value are cousins of each other if they are at the same level and have different parents. (The driver code will print 1 if the returned values is true,otherwise 0.)
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1<=Number of Nodes<=1000
Note: The Input/Ouput format and Example given are used for system's internal purpose, and should be used by a user for Expected Output only. As it is a function problem, hence a user should not read any input from stdin/console. The task is to complete the function specified, and not to write the full code.

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self,val):

        self.data=val

        self.left=None

        self.right=None

'''

# Returns true if the nodes with values 'a' and 'b' are cousins. Else returns false

def isCousin(root, a, b):

    # Your code here

Solutions:
def isCousin(root, a, b):
	if root is None:
		return 0
	q = [root]
	lev = False
	cou = True
	while q:
		l = len(q)
		a_exist = False
		b_exist = False
		for i in range(l):
			p = q.pop(0)
			if p.data == a:
				a_exist = True
			elif p.data == b:
				b_exist = True
			if a_exist and b_exist:
				lev = True
			if p.left and p.right:
				if p.left.data == a and p.right.data == b:
					cou = False
				elif p.left.data == b and p.right.data == a:
					cou = False
			if p.left:
				q.append(p.left)
			if p.right:
				q.append(p.right)
	if lev and cou:
		return 1
	else:
		return 0


def isCousin(root, a, b):

	def level(root, key):
		if root is None:
			return (None, -1)
		if root.left and root.left.data == key:
			return (root, 1)
		if root.right and root.right.data == key:
			return (root, 1)
		(temp1, count1) = level(root.left, key)
		(temp2, count2) = level(root.right, key)
		if temp1:
			return (temp1, 1 + count1)
		if temp2:
			return (temp2, 1 + count2)
		return (None, 0)
	(par1, l1) = level(root, a)
	(par2, l2) = level(root, b)
	if l1 == l2 and par1 != par2:
		return True
	return False


def isCousin(root, a, b):
	l = [root, 'a']
	a1 = False
	b1 = False
	while True:
		w = l.pop(0)
		while w != 'a':
			if w.left != None and w.right != None:
				if w.left.data == a and w.right.data == b or (w.left.data == b and w.right.data == a):
					return False
			if w.left != None:
				l.append(w.left)
			if w.right != None:
				l.append(w.right)
			if w.data == a:
				a1 = True
			elif w.data == b:
				b1 = True
			w = l.pop(0)
		if a1 == True and b1 == True:
			return True
		if l == []:
			return False
		l.append('a')
		a1 = False
		b1 = False


def isCousin(root, a, b):

	def helper(root, x):
		d = [None, -1]
		if root.left is not None:
			if root.left.data == x:
				return [root, 1]
			else:
				d = helper(root.left, x)
				d[1] += 1
		if d[0] is None and root.right is not None:
			if root.right.data == x:
				return [root, 1]
			else:
				d = helper(root.right, x)
				d[1] += 1
		return d
	l = helper(root, a)
	r = helper(root, b)
	if l[0] is None or r[0] is None:
		return False
	elif l[0] == r[0]:
		return False
	else:
		return l[1] == r[1]


from collections import deque

def isCousin(root, a, b):
	myQ = deque()
	myQ.append([root, None, 1])
	while myQ:
		times = len(myQ)
		while times:
			(holdQ, orgQ, level) = myQ.popleft()
			if holdQ.left != None:
				myQ.append([holdQ.left, holdQ, level + 1])
			if holdQ.right != None:
				myQ.append([holdQ.right, holdQ, level + 1])
			times -= 1
		mylist = []
		for bucket in myQ:
			if bucket[0].data == a or bucket[0].data == b:
				mylist.append(bucket)
		if len(mylist) == 1:
			return 0
		elif len(mylist) == 2:
			(first, second) = mylist
			return True if first[1] != second[1] and first[2] == second[2] else False
	return False


def isCousin(root, a, b):
	l = [root]
	ap = -1
	bp = -1
	al = -1
	bl = -1
	level = 0
	c = 0
	while l:
		r = []
		for i in l:
			if i.left:
				r.append(i.left)
				if i.left.data == a:
					al = level + 1
					c += 1
					ap = i
				if i.left.data == b:
					bl = level + 1
					c += 1
					bp = i
			if i.right:
				r.append(i.right)
				if i.right.data == a:
					al = level + 1
					c += 1
					ap = i
				if i.right.data == b:
					bl = level + 1
					c += 1
					bp = i
			if c == 2:
				break
		if c == 2:
			break
		l = r
		level += 1
	if ap != bp and al == bl:
		return True
	else:
		return False


def fun1(root, level, l1, temp, a, l1p):
	if root == None:
		return
	if root.data == a:
		l1[0] = level
		l1p[0] = [temp]
	temp = root
	fun1(root.left, level + 1, l1, temp, a, l1p)
	fun1(root.right, level + 1, l1, temp, a, l1p)

def fun2(root, level, l2, temp2, b, l2p):
	if root == None:
		return
	if root.data == b:
		l2[0] = level
		l2p[0] = [temp2]
	temp2 = root
	fun2(root.left, level + 1, l2, temp2, b, l2p)
	fun2(root.right, level + 1, l2, temp2, b, l2p)

def isCousin(root, a, b):
	l1 = [0]
	l1p = [0]
	temp = None
	fun1(root, 0, l1, temp, a, l1p)
	l2 = [0]
	l2p = [0]
	temp2 = None
	fun2(root, 0, l2, temp2, b, l2p)
	if l1[0] == l2[0] and l1p[0] != l2p[0]:
		return 1
	else:
		return 0


def getPath(currNode, currPath, target):
	if not currNode:
		return False
	currPath.append(currNode.data)
	if currNode.data == target:
		return True
	if getPath(currNode.left, currPath, target):
		return True
	if getPath(currNode.right, currPath, target):
		return True
	currPath.pop()

def isCousin(root, a, b):
	path_a = []
	path_b = []
	getPath(root, path_a, a)
	getPath(root, path_b, b)
	if len(path_a) == len(path_b):
		t = 0
		for (item_a, item_b) in zip(path_a, path_b):
			if item_a != item_b:
				return 1 < len(path_a) - t
			else:
				t += 1
	return False


def isCousin(root, a, b):
	hash = {}

	def fun(root, level):
		if root == None:
			return
		if root.left:
			if root.left.data == a:
				hash[a] = [root.data, level + 1]
			if root.left.data == b:
				hash[b] = [root.data, level + 1]
		if root.right:
			if root.right.data == a:
				hash[a] = [root.data, level + 1]
			if root.right.data == b:
				hash[b] = [root.data, level + 1]
		fun(root.left, level + 1)
		fun(root.right, level + 1)
	fun(root, 0)
	if a not in hash or b not in hash:
		return False
	if hash[a][0] != hash[b][0] and hash[a][1] == hash[b][1]:
		return True
	return False


def isCousin(root, a, b):
	(depth_a, par_a) = get_depth(root, a, 0, None)
	(depth_b, par_b) = get_depth(root, b, 0, None)
	return depth_a == depth_b and par_a is not par_b

def get_depth(root, node, d, par):
	if root.data == node:
		return (d, par)
	depth_left = depth_right = -1
	if root.left is not None:
		(depth_left, parent) = get_depth(root.left, node, d + 1, root)
		if depth_left != -1:
			return (depth_left, parent)
	if root.right is not None:
		(depth_right, parent) = get_depth(root.right, node, d + 1, root)
		if depth_right != -1:
			return (depth_right, parent)
	return (-1, None)


def level(root, height, value, parent, k):
	if root == None:
		return
	if root.data == value:
		k[0] = height
		k[1] = parent
	level(root.left, height + 1, value, root.data, k)
	level(root.right, height + 1, value, root.data, k)

def isCousin(root, a, b):
	k = [0, 0]
	level(root, 0, a, None, k)
	height_a = k[0]
	parent_a = k[1]
	k = [0, 0]
	level(root, 0, b, None, k)
	height_b = k[0]
	parent_b = k[1]
	if height_a != height_b:
		return False
	elif parent_a == parent_b:
		return False
	else:
		return True


from collections import deque

def Preorder(root, a, b, dict, level, parent):
	if root == None:
		return
	if root.data == a:
		dict[a] = [level, parent]
	if root.data == b:
		dict[b] = [level, parent]
	Preorder(root.left, a, b, dict, level + 1, root.data)
	Preorder(root.right, a, b, dict, level + 1, root.data)

def isCousin(root, a, b):
	if root.data == a or root.data == b:
		return 0
	dict = {}
	Preorder(root, a, b, dict, 0, -1)
	if a in dict and b in dict:
		if dict[a][0] == dict[b][0] and dict[a][1] != dict[b][1]:
			return 1
	return 0


def isCousin(root, a, b):
	if (level(root, a) == level(root, b) and (not isSibling(root, a, b))) and a != b:
		return 1
	else:
		return 0

def isSibling(root, a, b):
	if root is None or root.left is None or root.right is None:
		return 0
	return root.left.data == a and root.right.data == b or (root.left.data == b and root.right.data == a) or isSibling(root.left, a, b) or isSibling(root.right, a, b)

def level(root, ptr):
	if root is None:
		return 0
	if root.data == ptr:
		return 1
	level_node = max(level(root.left, ptr), level(root.right, ptr))
	if level_node != 0:
		return level_node + 1
	return 0


def isCousin(root, a, b):
	d = {}
	l = []
	level = 1
	d1 = {}
	helper(root, level, d)
	n1 = 0
	n2 = 0
	for i in d:
		if a in d[i]:
			n1 = i
		if b in d[i]:
			n2 = i
	if n1 == n2:
		helper1(root, d1)
		if d1[a] != d1[b]:
			return True
		else:
			return False
	return False

def helper(root, level, d):
	if root:
		if root == 'N':
			return
		else:
			if level not in d:
				d[level] = [root.data]
			else:
				d[level].append(root.data)
			helper(root.left, level + 1, d)
			helper(root.right, level + 1, d)

def helper1(root, d):
	if not root:
		return
	if root.left:
		d[root.left.data] = root.data
		helper1(root.left, d)
	if root.right:
		d[root.right.data] = root.data
		helper1(root.right, d)


def isCousin(root, a, b):
	if root is None:
		return 0
	q = []
	q.append(root)
	ans = set()
	while len(q) > 0:
		t = []
		while len(q) != 0:
			x = q.pop(0)
			if x.left is not None:
				if x.left.data == a or x.left.data == b:
					ans.add(x.data)
				t.append(x.left)
			if x.right is not None:
				if x.right.data == a or x.right.data == b:
					ans.add(x.data)
				t.append(x.right)
		q = t
		if len(ans) == 1:
			return False
	return True


def checkHeight(root, parent, a):
	if root == None:
		return -1
	if root.data == a:
		return 1
	lheight = checkHeight(root.left, parent, a)
	if lheight > 0:
		if lheight == 1:
			parent[0] = root
		return lheight + 1
	rheight = checkHeight(root.right, parent, a)
	if rheight > 0:
		if rheight == 1:
			parent[0] = root
		return rheight + 1
	return -1

def isCousin(root, a, b):
	if root == None:
		return False
	(parent1, parent2) = ([None], [None])
	height1 = checkHeight(root, parent1, a)
	height2 = checkHeight(root, parent2, b)
	if height1 != height2:
		return False
	if parent1 != parent2:
		return True
	else:
		return False


def isCousin(root, a, b):
	(parentA, parentB) = ([-1], [-1])
	(levelA, levelB) = ([-1], [-1])

	def dfs(root, parentNode, level):
		if root is None:
			return
		if root.data == a:
			parentA[0] = parentNode
			levelA[0] = level
		if root.data == b:
			parentB[0] = parentNode
			levelB[0] = level
		dfs(root.left, root.data, level + 1)
		dfs(root.right, root.data, level + 1)
	dfs(root, -1, 0)
	if parentA == parentB or levelA != levelB:
		return 0
	return 1


def isCousin(root, a, b):
	q = deque()
	q.appendleft(root)
	flag1 = False
	flag2 = False
	while len(q):
		n = len(q)
		for i in range(1, n + 1):
			el = q.pop()
			if el.left != None and el.left.data == a or (el.right != None and el.right.data == a):
				if el.left != None and el.left.data == b or (el.right != None and el.right.data == b):
					return False
				else:
					flag1 = True
			if el.left != None and el.left.data == b or (el.right != None and el.right.data == b):
				if el.left != None and el.left.data == a or (el.right != None and el.right.data == a):
					return False
				else:
					flag2 = True
			if el.left:
				q.appendleft(el.left)
			if el.right:
				q.appendleft(el.right)
		if not flag1 and (not flag2):
			continue
		return flag1 and flag2


def isCousin(root, a, b):
	q = [root]
	dic = {}
	l = 0
	leev = {}
	while q:
		for i in range(len(q)):
			node = q.pop(0)
			if node.left:
				q.append(node.left)
				dic[node.left.data] = node.data
			if node.right:
				q.append(node.right)
				dic[node.right.data] = node.data
			leev[node.data] = l
		l += 1
	if a not in dic:
		return 0
	if b not in dic:
		return 0
	if leev[a] == leev[b]:
		if dic[a] != dic[b]:
			return 1
	return 0


class extra:

	def __init__(self, x, l):
		self.node = x
		self.level = l

def isCousin(root, a, b):
	l = {}
	q = []
	p = {}
	q.append(root)
	q.append('$')
	level = 0
	while len(q) > 0:
		t = q.pop(0)
		if t == '$':
			if len(q) > 0:
				q.append('$')
				level += 1
		else:
			if t.data == a or t.data == b:
				l[t.data] = level
			if t.left is not None:
				if t.left.data == a or t.left.data == b:
					p[t.left.data] = t
				q.append(t.left)
			if t.right is not None:
				if t.right.data == a or t.right.data == b:
					p[t.right.data] = t
				q.append(t.right)
	if len(l) != 2:
		return False
	if l[a] != l[b]:
		return False
	if l[a] == l[b]:
		if p[a] != p[b]:
			return True
	return False


xx = 0

def size(root, e):
	global xx
	if root is None:
		return
	size(root.left, e)
	if root.data > xx:
		xx = root.data
	size(root.right, e)

def isCousin(root, a, b):
	return kthAncestor(root, a, b)

def kthAncestor(root, a, b):
	global xx
	e = []
	size(root, e)
	n = xx
	if root is None:
		return -1
	A = []
	C = []
	B = []
	D = []
	A.append(root)
	ancestors = [0] * (n + 1)
	ancestors[root.data] = -1
	while len(A) > 0:
		while len(A) > 0:
			node = A.pop(0)
			B.append(node.data)
			if node.left is not None:
				ancestors[node.left.data] = node.data
				D.append(node.left)
			if node.right is not None:
				ancestors[node.right.data] = node.data
				D.append(node.right)
		A.extend(D)
		D = []
		C.append(B)
		B = []
	for i in range(len(C)):
		if a in C[i] and b in C[i] and (ancestors[a] != ancestors[b]):
			return 1
	return 0


def isCousin(root, a, b):

	def traversal(root, level):
		nonlocal parent_a, parent_b, level_a, level_b
		if root == None:
			return None
		if root.left:
			if root.left.data == a:
				parent_a = root.data
				level_a = level
			elif root.left.data == b:
				parent_b = root.data
				level_b = level
		if root.right:
			if root.right.data == a:
				parent_a = root.data
				level_a = level
			elif root.right.data == b:
				parent_b = root.data
				level_b = level
		if root.left:
			traversal(root.left, level + 1)
		if root.right:
			traversal(root.right, level + 1)
	(parent_a, parent_b) = (None, None)
	(level_a, level_b) = (None, None)
	traversal(root, 0)
	if parent_a != None and parent_b != None:
		if level_a == level_b and parent_a != parent_b:
			return 1
	return 0


def isCousin(root, a, b):
	global c, d
	(c, d) = ([], [])

	def S(root, a, b, level):
		global c, d
		if not root:
			return 0
		if root.left and (root.left.data == a or root.left.data == b):
			c.append(root)
			d.append(level)
		if root.right and (root.right.data == a or root.right.data == b):
			c.append(root)
			d.append(level)
		S(root.left, a, b, level + 1)
		S(root.right, a, b, level + 1)
	S(root, a, b, 0)
	if len(d) > 1 and d[0] == d[1] and (c[0] != c[1]):
		return 1
	else:
		return 0


def isCousin(root, a, b):
	list = [1000, 1000]

	def isSibling(root, a, b):
		if not root:
			return 0
		if not root.left or not root.right:
			return 0
		return root.left.data == a and root.right.data == b or (root.left.data == b and root.right.data == a) or isSibling(root.left, a, b) or isSibling(root.right, a, b)

	def help(root, a, b, lvl):
		if not root:
			return 0
		if root.left:
			help(root.left, a, b, lvl + 1)
		if root.right:
			help(root.right, a, b, lvl + 1)
		if root.data == a:
			list[0] = lvl
		elif root.data == b:
			list[1] = lvl
		if not isSibling(root, a, b) and list[0] == list[1]:
			return 1
		else:
			return 0
	return help(root, a, b, 0)


def isCousin(root, a, b):
	result = myFunc(root, a, b, 0)
	return len(result) == 2 and result[0][0] == result[1][0] and (result[0][1] is not result[1][1])

def myFunc(root, a, b, level):
	if not root:
		return []
	level += 1
	result = []
	if root.left:
		if root.left.data == a or root.left.data == b:
			result.append((level, root))
	if root.right:
		if root.right.data == a or root.right.data == b:
			result.append((level, root))
	result += myFunc(root.left, a, b, level)
	result += myFunc(root.right, a, b, level)
	return result


def isSibling(root, a, b):
	if not root:
		return 0
	if not root.left or not root.right:
		return 0
	return root.left.data == a and root.right.data == b or (root.left.data == b and root.right.data == a) or isSibling(root.left, a, b) or isSibling(root.right, a, b)

def getDepth(root, node, level):
	if not root:
		return 0
	if root.data == node:
		return level
	l = getDepth(root.left, node, level + 1)
	if l != 0:
		return l
	return getDepth(root.right, node, level + 1)

def isCousin(root, a, b):
	if a == b:
		return False
	if not isSibling(root, a, b) and getDepth(root, a, 1) == getDepth(root, b, 1):
		return True
	return False


def isCousin(root, a, b):

	def traversal(root, level):
		nonlocal parent1, parent2, level1, level2
		if root == None:
			return None
		if root.left and root.left.data == a or (root.right and root.right.data == a):
			parent1 = root.data
			level1 = level
		elif root.left and root.left.data == b or (root.right and root.right.data == b):
			parent2 = root.data
			level2 = level
		if root.left:
			traversal(root.left, level + 1)
		if root.right:
			traversal(root.right, level + 1)
	(parent1, parent2, level1, level2) = (None, None, None, None)
	traversal(root, 0)
	if level1 != None and level1 == level2 and (parent1 != parent2):
		return 1
	return 0


def isCousin(root, a, b):
	d = {}
	q = [root]
	while q:
		n = len(q)
		for i in range(n):
			node = q[0]
			del q[0]
			if node:
				if node.left:
					d[node.left.data] = node
					q.append(node.left)
				if node.right:
					d[node.right.data] = node
					q.append(node.right)
	q = [root]
	while q:
		n = len(q)
		curr = []
		for i in range(n):
			node = q[0]
			del q[0]
			if node:
				curr.append(node.data)
				q.append(node.left)
				q.append(node.right)
		if a in curr and b in curr:
			return d[a] != d[b]
	return 0


import collections

def isCousin(root, a, b):
	[d1, p1] = dfs(root, a) or [None, None]
	[d2, p2] = dfs(root, b) or [None, None]
	return d1 == d2 and p1 != p2

def dfs(n, a, p=None, d=0):
	if not n:
		return None
	if n.data == a:
		return [d, p]
	return dfs(n.left, a, n, d + 1) or dfs(n.right, a, n, d + 1)


def isCousin(root, a, b):
	import collections
	q = collections.deque()
	q.append((root, None))
	while q:
		n = len(q)
		s = {}
		for _ in range(n):
			(curr, par) = q.popleft()
			s[curr.data] = par
			if curr.left:
				q.append((curr.left, curr))
			if curr.right:
				q.append((curr.right, curr))
		if a in s and b in s and (s[a] != s[b]):
			return True
	return False


def isCousin(root, a, b):

	def traversal(root, level):
		if root == None:
			return None
		if root.left:
			if root.left.data == a:
				dict1[a] = [root.data, level + 1]
			elif root.left.data == b:
				dict1[b] = [root.data, level + 1]
		if root.right:
			if root.right.data == a:
				dict1[a] = [root.data, level + 1]
			elif root.right.data == b:
				dict1[b] = [root.data, level + 1]
		if root.left:
			traversal(root.left, level + 1)
		if root.right:
			traversal(root.right, level + 1)
	dict1 = dict()
	(arr1, arr2) = ([], [])
	traversal(root, 0)
	if a in dict1:
		arr1 = dict1[a]
	if b in dict1:
		arr2 = dict1[b]
	if arr1 == [] or arr2 == []:
		return False
	if arr1[0] != arr2[0] and arr1[1] == arr2[1]:
		return True
	return False


def solve(root, level, a, b, prev, map_):
	if root == None:
		return None
	else:
		if root.data == a or root.data == b:
			map_.update({root.data: (prev, level)})
		l = solve(root.left, level + 1, a, b, root, map_)
		r = solve(root.right, level + 1, a, b, root, map_)
		return None

def isCousin(root, a, b):
	map_ = {}
	solve(root, 0, a, b, None, map_)
	if map_.get(a) == None or map_.get(b) == None:
		return False
	elif map_[a][0] != map_[b][0] and map_[a][1] == map_[b][1]:
		return True
	else:
		return False


def level(root, x, l):
	if not root:
		return 0
	if root.data == x:
		return l
	p = level(root.left, x, l + 1)
	if p > 1:
		return p
	q = level(root.right, x, l + 1)
	return q

def sibling(root, a, b):
	if not root:
		return False
	one = root.left and root.left.data == a and root.right and (root.right.data == b)
	two = root.right and root.right.data == a and root.left and (root.left.data == b)
	return one or two or sibling(root.left, a, b) or sibling(root.right, a, b)

def isCousin(root, a, b):
	if not root:
		return 0
	l1 = level(root, a, 1)
	l2 = level(root, b, 1)
	if l1 != l2 or l1 == 1 or l2 == 1 or (a == b):
		return 0
	if sibling(root, a, b):
		return 0
	return 1


def isCousin(root, a, b):
	resultOne = findParentAndLevel(root, None, a, 0, None)
	resultTwo = findParentAndLevel(root, None, b, 0, None)
	if None in (resultOne, resultTwo):
		return 0
	(parentOne, levelOne) = resultOne
	(parentTwo, levelTwo) = resultTwo
	return parentOne != parentTwo and levelOne == levelTwo

def findParentAndLevel(node, parent, target, level, result):
	if node is None:
		return None
	if node.data == target:
		return (parent, level)
	result = findParentAndLevel(node.left, node, target, level + 1, result)
	if not result:
		result = findParentAndLevel(node.right, node, target, level + 1, result)
	return result


def isCousin(root, a, b):

	def getParent(root, a, b):
		if root == None or root.data == a or root.data == b:
			return root
		l = getParent(root.left, a, b)
		r = getParent(root.right, a, b)
		if l == None:
			return r
		elif r == None:
			return l
		elif l != None and r != None:
			return root

	def getHeight(root, x):
		if root == None:
			return 0
		if root.data == x:
			return 1
		l = getHeight(root.left, x)
		r = getHeight(root.right, x)
		if l != 0 or r != 0:
			return 1 + max(l, r)
		return 0
	x = getHeight(root, a)
	y = getHeight(root, b)
	if x == y:
		parent = getParent(root, a, b)
		if parent.data == a or parent.data == b or parent.left.data == a or (parent.right.data == a):
			return False
		return True
	return False


def isCousin(root, a, b):

	def traversal(root, level):
		nonlocal parent_a, parent_b, level_a, level_b
		if root == None:
			return None
		if root.left and root.left.data == a or (root.right and root.right.data == a):
			parent_a = root
			level_a = level
		if root.left and root.left.data == b or (root.right and root.right.data == b):
			parent_b = root
			level_b = level
		if root.left:
			traversal(root.left, level + 1)
		if root.right:
			traversal(root.right, level + 1)
	(parent_a, parent_b) = (None, None)
	(level_a, level_b) = (-1, -1)
	traversal(root, 0)
	if parent_a == parent_b or level_a != level_b:
		return False
	return True


def isCousin(root, a, b):
	q = [(root, None, 0)]
	res = []
	while q:
		(x, parent, lvl) = q.pop(0)
		if x.data in (a, b):
			res.append((x.data, parent, lvl))
		if x.left:
			q.append((x.left, x, lvl + 1))
		if x.right:
			q.append((x.right, x, lvl + 1))
	if len(res) == 2:
		(x, y) = res
		if x[1] != y[1] and x[2] == y[2]:
			return 1
	return 0


def isCousin(root, a, b):
	parent_a = None
	level_a = -1
	parent_b = None
	level_b = -1

	def dfs(root, prev=None, count=0):
		nonlocal parent_a, parent_b, level_a, level_b
		if root is None:
			return
		if root.data == a:
			level_a = count
			parent_a = prev
		if root.data == b:
			level_b = count
			parent_b = prev
		dfs(root.left, root, count + 1)
		dfs(root.right, root, count + 1)
	dfs(root)
	if parent_a is None or parent_b is None:
		return 0
	return int(level_a == level_b and parent_a.data != parent_b.data)


def isCousin(root, a, b):
	if root == None:
		return None
	hd = 0
	q = [[root, hd]]
	dict1 = dict()
	while q != []:
		node = q.pop(0)
		hd = node[-1]
		if node[0].left:
			q.append([node[0].left, hd + 1])
			if node[0].left.data == a:
				dict1[node[0].left] = [node[0].data, hd + 1]
			elif node[0].left.data == b:
				dict1[node[0].left] = [node[0].data, hd + 1]
		if node[0].right:
			q.append([node[0].right, hd + 1])
			if node[0].right.data == a:
				dict1[node[0].right] = [node[0].data, hd + 1]
			elif node[0].right.data == b:
				dict1[node[0].right] = [node[0].data, hd + 1]
	list1 = list(dict1.values())
	length = len(list1)
	if length < 2:
		return False
	(p, q) = dict1.values()
	if p[0] != q[0] and p[1] == q[1]:
		return True
	return False


def isCousin(root, a, b):
	if root is None:
		return False
	que = deque()
	que.append(root)
	while len(que) > 0:
		asParent = None
		bsParent = None
		length = len(que)
		for i in range(length):
			elem = que.popleft()
			if elem.left:
				if elem.left.data == a:
					asParent = elem
				elif elem.left.data == b:
					bsParent = elem
				que.append(elem.left)
			if elem.right:
				if elem.right.data == a:
					asParent = elem
				elif elem.right.data == b:
					bsParent = elem
				que.append(elem.right)
		if asParent and bsParent and (asParent != bsParent):
			return True
	return False


class Pair:

	def __init__(self, level, parent):
		self.level = level
		self.parent = parent

def isCousin(root, a, b):
	if root is None:
		return False
	if isLeaf(root):
		return False
	queue = []
	findParentandLevel(root, a, b, 0, None, queue)
	if len(queue) < 2:
		return False
	p1 = queue[0]
	p2 = queue[1]
	if p1.level == p2.level and p1.parent != p2.parent:
		return True
	return False

def findParentandLevel(root, a, b, level, parent, queue):
	if root is None:
		return
	if root.data == a:
		queue.append(Pair(level, parent))
	if root.data == b:
		queue.append(Pair(level, parent))
	findParentandLevel(root.left, a, b, level + 1, root, queue)
	findParentandLevel(root.right, a, b, level + 1, root, queue)

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


def isCousin(root, a, b):
	if a == b:
		return False
	x = [True]

	def helper(root, a, b):
		if not root:
			return True
		if root.left and root.right:
			if root.left.data == a and root.right.data == b or (root.left.data == b and root.right.data == a):
				x[0] = False
				return False
		l = helper(root.left, a, b)
		r = helper(root.right, a, b)
		return l + r
	helper(root, a, b)
	if x[0] == False:
		return False

	def level(root):
		ans = []
		q = []
		if not root:
			return ans
		q.append(root)
		while q:
			t = []
			for i in range(len(q)):
				a = q.pop(0)
				if a.left:
					q.append(a.left)
				if a.right:
					q.append(a.right)
				t.append(a.data)
			ans.append(t)
		return ans
	aa = level(root)
	for i in aa:
		if a in i and b in i:
			return True
	return False


def isCousin(root, a, b):
	parent = [a, b]
	levels = [a, b]
	findParentandLevels(root, Node(-1), 0, a, b, parent, levels)
	if parent[0] != parent[1] and levels[0] == levels[1]:
		return 1
	else:
		return 0

def findParentandLevels(root, currentParent, currentLevel, x, y, parent, levels):
	if root is None:
		return
	if root.data == x:
		parent[0] = currentParent.data
		levels[0] = currentLevel
	if root.data == y:
		parent[1] = currentParent.data
		levels[1] = currentLevel
	findParentandLevels(root.left, root, currentLevel + 1, x, y, parent, levels)
	findParentandLevels(root.right, root, currentLevel + 1, x, y, parent, levels)
	return (parent, levels)


def isCousin(root, a, b):
	(l[0], l[1], p[0], p[1]) = (None, None, None, None)
	if root is None:
		return False
	util(root, a, b, 0)
	if l[0] is not None and l[0] == l[1] and (p[0] != p[1]):
		return True
	return False

def util(root, a, b, level):
	if root is None:
		return
	if root.left and root.left.data == a:
		l[0] = level
		p[0] = root.data
	elif root.left and root.left.data == b:
		l[1] = level
		p[1] = root.data
	if root.right and root.right.data == a:
		l[0] = level
		p[0] = root.data
	elif root.right and root.right.data == b:
		l[1] = level
		p[1] = root.data
	util(root.left, a, b, level + 1)
	util(root.right, a, b, level + 1)
l = [None] * 2
p = [None] * 2


LEV_A = None
SIB_A = None
LEV_A = None
SIB_B = None
CURR_LEV = 0

def getData(root, value1, value2):
	global LEV_A, SIB_A, LEV_B, SIB_B, CURR_LEV
	if not root:
		return
	CURR_LEV += 1
	if root.left:
		if root.left.data == value1:
			LEV_A = CURR_LEV
			if root.right:
				SIB_A = root.right.data
		if root.left.data == value2:
			LEV_B = CURR_LEV
			if root.right:
				SIB_B = root.right.data
	if root.right:
		if root.right.data == value1:
			LEV_A = CURR_LEV
			if root.left:
				SIB_A = root.left.data
		if root.right.data == value2:
			LEV_B = CURR_LEV
			if root.left:
				SIB_B = root.left.data
	getData(root.left, value1, value2)
	getData(root.right, value1, value2)
	CURR_LEV -= 1

def isCousin(root, a, b):
	if a == b:
		return False
	global LEV_A, SIB_A, LEV_B, SIB_B, CURR_LEV
	LEV_A = None
	SIB_A = None
	LEV_A = None
	SIB_B = None
	CURR_LEV = 0
	getData(root, a, b)
	if LEV_A is None or LEV_B is None:
		return False
	elif LEV_A != LEV_B:
		return False
	elif SIB_A == b and SIB_B == a:
		return False
	else:
		return True


def isCousin(root, a, b):
	res = []
	process(root, a, b, res, 0, None)
	if len(res) != 2:
		return False
	elif res[0][0] != res[1][0] and res[0][1] == res[1][1]:
		return True
	else:
		return False

def process(root, a, b, res, lev, par):
	if root is None:
		return
	if len(res) == 2:
		return
	if root.data == a or root.data == b:
		res.append((par, lev))
	process(root.left, a, b, res, lev + 1, root)
	process(root.right, a, b, res, lev + 1, root)


def isCousin(root, a, b):
	tracker = {}

	def dfs(nd, par, dep, x, y):
		if not nd:
			return
		dfs(nd.left, nd, dep + 1, x, y)
		dfs(nd.right, nd, dep + 1, x, y)
		if nd.data in (x, y):
			tracker[nd.data] = (par, dep)
	dfs(root, None, 0, a, b)
	cousin = tracker.get(a) and tracker.get(b) and (tracker[a][1] == tracker[b][1]) and (tracker[a][0] != tracker[b][0])
	return cousin


def isCousin(root, a, b):
	queue = [root]
	level = []
	while queue != [] and root is not None:
		l = {}
		i = 0
		k = m = 0
		for node in queue:
			if node.left:
				level.append(node.left)
				if node.left.data == a:
					k = 1
					l[a] = i
				if node.left.data == b:
					m = 1
					l[b] = i
			if node.right:
				level.append(node.right)
				if node.right.data == b:
					m = 1
					l[b] = i
				if node.right.data == a:
					k = 1
					l[a] = i
			if k == 1 and m == 1:
				index1 = l[a]
				index2 = l[b]
				if index1 == index2:
					return 0
				elif index1 != index2:
					return 1
			i += 1
		queue = level
		level = []


def isCousin(root, a, b):
	info = {}

	def rec(root, parent, lvl):
		if not root:
			return
		if root.data in [a, b]:
			info[root.data] = (parent, lvl)
			return
		rec(root.left, root, lvl + 1)
		rec(root.right, root, lvl + 1)
	rec(root, None, 0)
	if a not in info or b not in info:
		return False
	(a_parent, b_parent) = (info[a][0], info[b][0])
	(a_lvl, b_lvl) = (info[a][1], info[b][1])
	return a_parent != b_parent and a_lvl == b_lvl


def isCousin(root, a, b):
	from collections import deque
	q = deque()
	q.append(root)
	ans = {}
	ans[root.data] = [0, -1]
	c = 1
	while q:
		size = len(q)
		for i in range(size):
			node = q.popleft()
			if node.left:
				ans[node.left.data] = [c, node.data]
				q.append(node.left)
			if node.right:
				ans[node.right.data] = [c, node.data]
				q.append(node.right)
		c += 1
	if a in ans and b in ans and (ans[a][0] == ans[b][0]) and (ans[a][1] != ans[b][1]):
		return True
	return False


def isSibling(root, a, b):
	if root is None:
		return 0
	if not root.left or not root.right:
		return
	return root.left.data == a and root.right.data == b or (root.left.data == b and root.right.data == a) or isSibling(root.left, a, b) or isSibling(root.right, a, b)

def level(root, ptr, lev):
	if root is None:
		return
	if root.data == ptr:
		return lev
	return level(root.right, ptr, lev + 1) or level(root.left, ptr, lev + 1)

def isCousin(root, a, b):
	if a == b:
		return
	if level(root, a, 1) == level(root, b, 1) and (not isSibling(root, a, b)):
		return True
	else:
		return


def isCousin(root, a, b):
	if root == None:
		return False
	queue = []
	queue.append([root, root])
	(fa, fb) = (False, False)
	while queue:
		n = len(queue)
		while n > 0:
			(node, parent) = queue.pop(0)
			if node.data == a:
				fa = True
				pa = parent
			if node.data == b:
				fb = True
				pb = parent
			if (fa is True and fb is True) and pa != pb:
				return True
			if node.left:
				queue.append([node.left, node])
			if node.right:
				queue.append([node.right, node])
			n -= 1
		fa = False
		fb = False
	return False


def isCousin(root, x, y):
	if root == None:
		return False
	q = deque()
	q.append([root, root])
	(foundx, foundy) = (False, False)
	(parentx, parenty) = (None, None)
	while len(q):
		for _ in range(len(q)):
			(node, parent) = q.popleft()
			if node.data == x:
				foundx = True
				parentx = parent
			if node.data == y:
				foundy = True
				parenty = parent
			if (foundx is True and foundy is True) and parentx != parenty:
				return True
			if node.left:
				q.append([node.left, node])
			if node.right:
				q.append([node.right, node])
		foundx = False
		foundy = False
	return False


def find_Parent_Level(root, n, parent, level, res):
	if root == None:
		return False
	if root.data == n:
		res.append([parent, level])
		return True
	lh = find_Parent_Level(root.left, n, root, level + 1, res)
	if lh == True:
		return True
	rh = find_Parent_Level(root.right, n, root, level + 1, res)
	if rh == True:
		return True

def isCousin(root, a, b):
	res = []
	res1 = find_Parent_Level(root, a, None, 0, res)
	res2 = find_Parent_Level(root, b, None, 0, res)
	if len(res) != 2:
		return 0
	res1 = res[0]
	res2 = res[1]
	if res1[0] != res2[0] and res1[1] == res2[1]:
		return 1
	return 0


from collections import deque

def isCousin(root, a, b):
	queue = deque()
	queue.append([root, None])
	x = y = False
	parentx = parenty = None
	while queue:
		k = len(queue)
		while k:
			(node, parent) = queue.popleft()
			if node.data == a:
				x = True
				parentx = parent
			if node.data == b:
				y = True
				parenty = parent
			if x and y and (parentx != parenty):
				return True
			if node.left:
				queue.append([node.left, node])
			if node.right:
				queue.append([node.right, node])
			k -= 1
		x = y = False
	return False


def isCousin(root, a, b):
	q = [root, None]
	arr = [1, None]
	level = 1
	t1 = -1
	t2 = -2
	while q:
		t = q.pop(0)
		p = arr.pop(0)
		if not t and q:
			level += 1
			q.append(None)
			arr.append(None)
		elif not t and (not q):
			break
		else:
			if t.left:
				q.append(t.left)
				arr.append(2 * p)
			if t.right:
				q.append(t.right)
				arr.append(2 * p + 1)
			if t.data == a:
				t1 = level
				k1 = p
			if t.data == b:
				t2 = level
				k2 = p
	if t1 == -1 or t2 == -2:
		return False
	if t1 == t2:
		if k1 // 2 != k2 // 2:
			return True
	return False


from collections import deque

def isCousin(root, a, b):
	if root is None:
		return False
	queue = deque()
	queue.append(root)
	while len(queue):
		temp = []
		for i in range(len(queue)):
			node = queue.popleft()
			if (node.left and node.right) and (node.left.data == a and node.right.data == b or (node.left.data == b and node.right.data == a)):
				return False
			temp.append(node.data)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
		if a in temp and b not in temp or (a not in temp and b in temp):
			return False
		if a != b and a in temp and (b in temp):
			return True


def isCousin(root, a, b):

	def _findLevelAndParent(root, node, parent=None, level=0):
		if root == None:
			return (None, None)
		if root.data == node:
			return (level, parent)
		(level1, parent1) = _findLevelAndParent(root.left, node, root, level + 1)
		(level2, parent2) = _findLevelAndParent(root.right, node, root, level + 1)
		if parent1:
			return (level1, parent1)
		if parent2:
			return (level2, parent2)
		return (None, None)
	(level1, parent1) = _findLevelAndParent(root, a)
	(level2, parent2) = _findLevelAndParent(root, b)
	if level1 == level2 and parent1 != parent2:
		return True
	return False


def isCousin(root, a, b):
	l = []
	q = [[root, 0, None]]
	c = 0
	while c != len(q):
		t = q[c][0]
		g = q[c][1]
		if t.data == a or t.data == b:
			l.append(q[c])
		if len(l) == 2:
			break
		if t.left:
			q.append([t.left, g + 1, t])
		if t.right:
			q.append([t.right, g + 1, t])
		c += 1
	if len(l) == 2 and l[0][0] != l[1][0] and (l[0][1] == l[1][1]) and (l[0][2] != l[1][2]):
		return True
	return False


def isCousin(root, a, b):

	def f(root, l, par):
		if root == None:
			return
		if root.data == a or root.data == b:
			d[root.data] = (l, par)
		f(root.left, l + 1, root.data)
		f(root.right, l + 1, root.data)
	d = {}
	f(root, 0, None)
	if a in d.keys() and b in d.keys() and (d[a][0] == d[b][0]) and (d[a][1] != d[b][1]):
		return True
	return False


def isCousin(root, a, b):
	q = deque()
	q.append(root)
	(f1, f2, p1, p2) = (0, 0, 0, 0)
	level = 1
	while q:
		l = len(q)
		for _ in range(l):
			node = q.popleft()
			if node.left:
				if node.left.data == a:
					f1 = level
					p1 = node
				if node.left.data == b:
					f2 = level
					p2 = node
				q.append(node.left)
			if node.right:
				if node.right.data == a:
					f1 = level
					p1 = node
				if node.right.data == b:
					f2 = level
					p2 = node
				q.append(node.right)
		level += 1
	return f1 == f2 and p1 != p2


def isCousin(root, x, y):
	if x == y:
		return False
	if root == None or root.data == x or root.data == y:
		return False
	q = []
	ans = []
	q.append(root)
	while len(q) > 0:
		l = []
		n = len(q)
		for i in range(n):
			curr = q.pop(0)
			a = curr.left
			b = curr.right
			if (a and b) and (curr.left.data == x and curr.right.data == y or (curr.left.data == y and curr.right.data == x)):
				return False
			l.append(curr.data)
			if curr.left:
				q.append(curr.left)
			if curr.right:
				q.append(curr.right)
			if x in l and y in l:
				return True
		ans.append(l)


def isCousin(root, a, b):
	if a == root.data or b == root.data:
		return False
	result = []
	parent = {}
	l = 0
	(A, B) = (None, None)
	queue = deque()
	queue.append(root)
	while queue:
		for _ in range(len(queue)):
			t = queue.popleft()
			if t.left:
				if t.left.data == a:
					A = t.left
				if t.left.data == b:
					B = t.left
				parent[t.left] = [t, l]
				queue.append(t.left)
			if t.right:
				if t.right.data == a:
					A = t.right
				if t.right.data == b:
					B = t.right
				parent[t.right] = [t, l]
				queue.append(t.right)
		l += 1
	if A in parent and B in parent and (parent[A][0] == parent[B][0]):
		return False
	elif A in parent and B in parent and (parent[A][1] == parent[B][1]):
		return True
	else:
		return False


from collections import defaultdict

def isCousin(root, a, b):
	p1 = -1
	p2 = -1
	q = deque()
	q.append(root)
	while q:
		n = len(q)
		for i in range(n):
			temp = q.popleft()
			if temp.left:
				if temp.left.data == a or temp.left.data == b:
					if p1 == -1:
						p1 = temp.data
					else:
						p2 = temp.data
				q.append(temp.left)
			if temp.right:
				if temp.right.data == a or temp.right.data == b:
					if p1 == -1:
						p1 = temp.data
					else:
						p2 = temp.data
				q.append(temp.right)
		if p1 != p2 and p1 != -1 and (p2 != -1):
			return True
		p1 = -1
		p2 = -1
	return False


def isCousin(root, a, b):
	levela = -1
	levelb = -1
	parenta = None
	parentb = None
	queue = []
	queue.append(root)
	lvl = -1
	while queue:
		count = len(queue)
		lvl += 1
		for i in range(count):
			curr = queue.pop(0)
			if curr.left:
				if curr.left.data == a:
					parenta = curr
					levela = lvl + 1
				elif curr.left.data == b:
					parentb = curr
					levelb = lvl + 1
				queue.append(curr.left)
			if curr.right:
				if curr.right.data == a:
					parenta = curr
					levela = lvl + 1
				elif curr.right.data == b:
					parentb = curr
					levelb = lvl + 1
				queue.append(curr.right)
	if parenta != parentb and levela == levelb:
		return True
	return False


def isCousin(root, a, b):
	if root == None:
		return False
	if root.data == a or root.data == b:
		return False
	if a == b:
		return False
	q1 = [root]
	q2 = []
	x = False
	y = False
	while q1 != [] or q2 != []:
		x = False
		y = False
		while q1 != []:
			t = q1[0]
			q1.pop(0)
			if t.left:
				q2.append(t.left)
			if t.right:
				q2.append(t.right)
			if t.left and t.right:
				if t.left.data == a and t.right.data == b or (t.left.data == b and t.right.data == a):
					return False
			if t.data == a:
				x = True
			if t.data == b:
				y = True
		if x and y:
			return True
		x = False
		y = False
		while q2 != []:
			t = q2[0]
			q2.pop(0)
			if t.left:
				q1.append(t.left)
			if t.right:
				q1.append(t.right)
			if t.left and t.right:
				if t.left.data == a and t.right.data == b or (t.left.data == b and t.right.data == a):
					return False
			if t.data == a:
				x = True
			if t.data == b:
				y = True
		if x and y:
			return True
	return False


def isCousin(root, a, b):
	arr = [[None, -1], [None, -1]]
	parentCheck(root, a, b, arr, None, 0)
	return True if arr[0][0] != arr[1][0] and arr[0][1] == arr[1][1] else False

def parentCheck(root, a, b, arr, parent, level):
	if not root:
		return
	if root.data == a:
		arr[0][0] = parent
		arr[0][1] = level
	if root.data == b:
		arr[1][0] = parent
		arr[1][1] = level
	parentCheck(root.left, a, b, arr, root, level + 1)
	parentCheck(root.right, a, b, arr, root, level + 1)


from collections import deque

def isCousin(root, a, b):
	ta = None
	tb = None
	q = deque()
	temp = Node(-1)
	q.append((root, temp))
	while q:
		n = len(q)
		while n > 0:
			n -= 1
			t = q.popleft()
			if t[0].data == a:
				ta = t[1]
			if t[0].data == b:
				tb = t[1]
			if t[0].left:
				q.append((t[0].left, t[0]))
			if t[0].right:
				q.append((t[0].right, t[0]))
			if ta and tb:
				break
		if ta and tb:
			return ta != tb
		if ta and tb is None or (tb and ta is None):
			return False
	return False


def isCousin(root, a, b):
	parent = [[None], [None]]
	isCousinUtil(root, a, b, parent, 1)
	if parent[0][0] is None or parent[1][0] is None:
		return False
	if parent[0][0] != parent[1][0] and parent[0][1] == parent[1][1]:
		return True
	else:
		return False

def isCousinUtil(root, a, b, parent, level):
	if root is None or (parent[0][0] != None and parent[1][0] != None):
		return
	if root.left is not None and (root.left.data == a or root.left.data == b):
		if root.left.data == a:
			parent[0] = [root, level]
		else:
			parent[1] = [root, level]
	if root.right is not None and (root.right.data == a or root.right.data == b):
		if root.right.data == a:
			parent[0] = [root, level]
		else:
			parent[1] = [root, level]
	isCousinUtil(root.left, a, b, parent, level + 1)
	isCousinUtil(root.right, a, b, parent, level + 1)


from collections import *

def isCousin(root, a, b):
	if not root or not root.left or (not root.right):
		return False
	q = deque([root])
	foundAOrB = False
	nextToFind = -1
	while len(q) > 0:
		qLen = len(q)
		nextLevel = []
		for _ in range(qLen):
			top = q.popleft()
			if top.left and (top.left.data == a or top.left.data == b) and (not foundAOrB):
				foundAOrB = True
				if top.left.data == a:
					nextToFind = b
				elif top.left.data == b:
					nextToFind = a
				continue
			if top.right and (top.right.data == a or top.right.data == b) and (not foundAOrB):
				foundAOrB = True
				if top.right.data == a:
					nextToFind = b
				elif top.right.data == b:
					nextToFind = a
				continue
			if top.left:
				nextLevel.append(top.left)
			if top.right:
				nextLevel.append(top.right)
		if foundAOrB:
			for node in nextLevel:
				if node.data == nextToFind:
					return True
			return False
		q.extend(nextLevel)
	return False


def isCousin(root, a, b):
	if root is None or a is None or b is None:
		return False
	queue = []
	queue.append([root, root])
	(foundA, foundB, parentA, parentB) = (False, False, None, None)
	while queue:
		size = len(queue)
		for i in range(size):
			(rootNode, parent) = queue.pop(0)
			if rootNode.data == a:
				foundA = True
				parentA = parent
			if rootNode.data == b:
				foundB = True
				parentB = parent
			if foundA and foundB and (parentA != parentB):
				return True
			if rootNode.left:
				queue.append([rootNode.left, rootNode])
			if rootNode.right:
				queue.append([rootNode.right, rootNode])
		foundA = False
		foundB = False
	return False


from collections import deque

def isCousin(root, a, b):
	ta = None
	tb = None
	q = deque()
	temp = Node(-1)
	q.append((root, temp))
	while len(q) > 0:
		size = len(q)
		while size:
			t = q.popleft()
			if t[0].data == a:
				ta = t[1]
			if t[0].data == b:
				tb = t[1]
			if t[0].left:
				q.append((t[0].left, t[0]))
			if t[0].right:
				q.append((t[0].right, t[0]))
			size -= 1
			if ta and tb:
				break
		if ta and tb:
			return ta != tb
		if ta and (not tb) or (tb and (not ta)):
			return False
	return False
from collections import deque

class Node:

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

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


def isCousin(root, x, y):
	if root == None:
		return False
	q = deque()
	q.append([root, root])
	(foundx, foundy) = (False, False)
	(parentx, parenty) = (None, None)
	while len(q):
		for _ in range(len(q)):
			(node, parent) = q.popleft()
			if node.data == x:
				foundx = True
				parentx = parent
			if node.data == y:
				foundy = True
				parenty = parent
			if (foundx is True and foundy is True) and parentx != parenty:
				return True
			if node.left:
				q.append([node.left, node])
			if node.right:
				q.append([node.right, node])
		foundx = False
		foundy = False
	return False
from collections import deque

class Node:

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

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


def isCousin(root, a, b):
	q = deque([[root, -1, 0]])
	p_a = None
	l_a = None
	p_b = None
	l_b = None
	while q:
		(node, p, lv) = q.popleft()
		if node.data == a:
			p_a = p
			l_a = lv
		elif node.data == b:
			p_b = p
			l_b = lv
		if p_a and p_b:
			break
		if node.left:
			q.append([node.left, node.data, lv + 1])
		if node.right:
			q.append([node.right, node.data, lv + 1])
	if l_a == l_b:
		if p_a != p_b:
			return True
	return False
from collections import deque

class Node:

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

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