Given a binary tree and a node, print all cousins of given node in order of their appearance. Note that siblings should not be printed.
Example 1:
Input : 
             1
           /   \
          2     3
        /   \  /  \
       4    5  6   7
Given node : 5
Output : 6 7
Explanation :
Nodes 6 and 7 are on the same level 
as 5 and have different parents.
Example 2 :
Input :
         9
        /
       5
Given node : 5
Output : -1
Explanation :
There no other nodes than 5 in the same level.
Your task :
You don't have to read input or print anything. Your task is to complete the function printCousins() which takes the root node of the tree and the node whose cousins need to be found, as input and returns a list containing the cousins of the given node in order of their appearance in the tree. If there is no cousin of the given node, return -1 as the first element of the list.
 
Expected Time Complexity : O(n)
Expected Auxiliary Space : O(n)
 
Constraints :
1 <= n <=10^5

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3



'''

# Tree Node

class Node:

    def __init__(self, val):

        self.right = None

        self.data = val

        self.left = None

'''

class Solution:

    def printCousins(self, root, node_to_find):

        #code here



Solutions:
class Solution:

	def printCousins(self, root, node_to_find):
		q = [root]
		flag = 0
		while len(q) > 0:
			l = len(q)
			for i in range(l):
				temp = q[0]
				q.pop(0)
				if temp.left != None and temp.left == node_to_find:
					flag = 1
					continue
				elif temp.right != None and temp.right == node_to_find:
					flag = 1
					continue
				if temp.left != None:
					q.append(temp.left)
				if temp.right != None:
					q.append(temp.right)
			if flag == 1:
				break
		for i in range(len(q)):
			q[i] = q[i].data
		if len(q) == 0:
			return [-1]
		return q


class Solution:

	def printCousins(self, root, node_to_find):
		q = [root]
		while q:
			(flag, tmp) = (False, [])
			while q:
				x = q.pop(0)
				if x.left:
					if x.left == node_to_find:
						flag = True
						continue
					tmp.append(x.left)
				if x.right:
					if x.right == node_to_find:
						flag = True
						if x.left:
							tmp.pop()
							continue
					tmp.append(x.right)
			if flag == 1:
				ans = []
				for i in range(len(tmp)):
					if tmp[i] != node_to_find:
						ans.append(tmp[i].data)
				return ans if ans != [] else [-1]
			q = tmp
		return [-1]


class Solution:

	def cousins(self, root, dic, l, poor, k):
		if root == None:
			return
		if l not in poor:
			poor[l] = [root.data]
		else:
			poor[l].append(root.data)
		if root.data == k.data:
			self.lev = l
		if root.left:
			dic[root.left.data] = root.data
		if root.right:
			dic[root.right.data] = root.data
		l += 1
		self.cousins(root.left, dic, l, poor, k)
		self.cousins(root.right, dic, l, poor, k)
		l -= 1

	def printCousins(self, root, node_to_find):
		poor = {}
		self.lev = 0
		dic = {}
		self.cousins(root, dic, 0, poor, node_to_find)
		lis = poor[self.lev]
		ans = []
		if len(lis) == 1:
			return [-1]
		for i in lis:
			if dic[i] != dic[node_to_find.data]:
				ans.append(i)
		if len(ans) == 0:
			return [-1]
		return ans


class Solution:

	def printCousins(self, root, node_to_find):
		if root == node_to_find:
			return [-1]
		(level, sibling) = (0, [None])

		def traverse(root, parent):
			if not root:
				return float('inf')
			if root == node_to_find:
				sibling[0] = parent
				return 0
			return 1 + min(traverse(root.left, root), traverse(root.right, root))
		level = traverse(root, None)
		(temp, count) = ([root, '\n'], 0)
		while level > 0:
			if temp[0] == '\n':
				level -= 1
				temp += ['\n']
				temp.pop(0)
				continue
			if temp[0] == sibling[0]:
				temp.pop(0)
				continue
			if temp[0].left:
				temp += [temp[0].left]
			if temp[0].right:
				temp += [temp[0].right]
			temp.pop(0)
		temp.pop()
		for i in range(len(temp)):
			temp[i] = temp[i].data
		return temp if temp != [] else [-1]


from collections import deque

class Solution:

	def printCousins(self, root, node_to_find):
		q = deque()
		q.append(root)
		parent = {root: None}
		level = {root: 0}
		found = -1
		node = None
		while len(q) > 0:
			curr = q.popleft()
			if curr == node_to_find:
				found = level[curr]
				node = curr
			if curr.left:
				parent[curr.left] = curr
				q.append(curr.left)
				level[curr.left] = level[curr] + 1
			if curr.right:
				parent[curr.right] = curr
				q.append(curr.right)
				level[curr.right] = level[curr] + 1
		if not node:
			return [-1]
		ans = []
		for (k, v) in level.items():
			if v == found and parent[k] != parent[node]:
				ans.append(k.data)
		if len(ans) == 0:
			return [-1]
		ans.sort()
		return ans


class Solution:

	def printCousins(self, root, node_to_find):

		def findNode(node, q_node, h, parent):
			if node == None:
				return (None, None)
			if node.data == q_node:
				return (parent, h)
			(parent2, h2) = findNode(node.left, q_node, h + 1, node.data)
			if parent2 == None:
				(parent2, h2) = findNode(node.right, q_node, h + 1, node.data)
			return (parent2, h2)
		(parent, h) = findNode(root, node_to_find.data, 0, None)
		res = []

		def findCousins(node, h1):
			if node == None:
				return
			if h1 == 1 and node.data == parent:
				return
			if h1 == 0:
				res.append(node.data)
				return
			if h1 < 0:
				return
			findCousins(node.left, h1 - 1)
			findCousins(node.right, h1 - 1)
		if root.data != node_to_find.data:
			findCousins(root, h)
		return res if len(res) else [-1]


class Solution:

	def printCousins(self, root, node_to_find):
		q = [root]
		black_list = []
		ans_list = []
		level = 1
		ans_level = 0
		while q:
			for _ in range(len(q)):
				node = q.pop(0)
				if ans_level + 1 == level:
					ans_list.append(node)
				if node.left == node_to_find or node.right == node_to_find:
					if node.left:
						black_list.append(node.left)
					if node.right:
						black_list.append(node.right)
					ans_level = level
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			level += 1
		ans_list = [item for item in ans_list if item not in black_list]
		ans = []
		for val in ans_list:
			ans.append(val.data)
		ans.pop(0)
		if len(ans) < 1:
			ans = [-1]
		return ans


class Solution:

	def Preorder(self, root, lvl, parent, level, val):
		if root == None:
			return
		if root.data == val:
			parent[0] = Node(-1)
			level[0] = [0]
			return
		if root.left != None:
			if root.left.data == val:
				parent[0] = root
				level[0] = lvl + 1
				return
		if root.right != None:
			if root.right.data == val:
				parent[0] = root
				level[0] = lvl + 1
				return
		self.Preorder(root.left, lvl + 1, parent, level, val)
		self.Preorder(root.right, lvl + 1, parent, level, val)

	def Preorder2(self, root, lvl, par, ans, parent, level):
		if root == None:
			return
		if lvl == level[0] and par.data != parent[0].data:
			ans.append(root.data)
		self.Preorder2(root.left, lvl + 1, root, ans, parent, level)
		self.Preorder2(root.right, lvl + 1, root, ans, parent, level)

	def printCousins(self, root, node_to_find):
		ans = []
		parent = [Node(-1)]
		level = [0]
		self.Preorder(root, 0, parent, level, node_to_find.data)
		self.Preorder2(root, 0, Node(-1), ans, parent, level)
		if len(ans) == 0:
			return [-1]
		return ans


class Solution:

	def printCousins(self, root, node_to_find):
		que = [root]
		while que:
			size = len(que)
			tmp = False
			for i in range(size):
				node = que.pop(0)
				if node.left == node_to_find or node.right == node_to_find:
					tmp = True
				else:
					if node.left is not None:
						que.append(node.left)
					if node.right is not None:
						que.append(node.right)
			if tmp == True:
				if que:
					out = [n.data for n in que]
					return out
				else:
					return [-1]
		return [-1]


class Solution:

	def printCousins(self, root, node_to_find):
		if root is None:
			return [-1]
		q = []
		q.append(root)
		ans = []
		check = None
		while len(q) > 0:
			t = []
			arr = []
			while len(q) != 0:
				x = q.pop(0)
				if x.left is not None:
					t.append(x.left)
					if x.left.data == node_to_find.data:
						check = x
				if x.right is not None:
					t.append(x.right)
					if x.right.data == node_to_find.data:
						check = x
				if check != x:
					arr.append(x)
			if check is not None:
				for i in arr:
					if i.left is not None:
						ans.append(i.left.data)
					if i.right is not None:
						ans.append(i.right.data)
				if len(ans) == 0:
					return [-1]
				else:
					return ans
			q = t
		return [-1]


class Solution:

	def printCousins(self, root, node_to_find):
		q = [root]
		l = []
		while q:
			s = len(q)
			temp = False
			for i in range(s):
				t = q.pop(0)
				if t.left == node_to_find or t.right == node_to_find:
					temp = True
				else:
					if t.left:
						q.append(t.left)
					if t.right:
						q.append(t.right)
			if temp == True:
				if q:
					for i in q:
						l.append(i.data)
					return l
				else:
					return [-1]
		return [-1]


class Solution:

	def printCousins(self, root, x):
		q = list()
		q.append(root)
		flag = False
		while len(q) and (not flag):
			size = len(q)
			while size:
				cur = q.pop(0)
				if cur.left == x or cur.right == x:
					flag = True
				else:
					if cur.left:
						q.append(cur.left)
					if cur.right:
						q.append(cur.right)
				size -= 1
		if len(q) == 0:
			return [-1]
		else:
			ans = list()
			while len(q) > 0:
				cur = q.pop(0)
				ans.append(cur.data)
		return ans if len(ans) > 0 else [-1]


from collections import deque

class Solution:

	def printCousins(self, root, node_to_find):
		level = self.findLevel(root, node_to_find, 0)
		output = []
		queue = deque()
		queue.append((root, level - 1))
		while queue:
			(root, level) = queue.popleft()
			if root is None:
				continue
			if level == 0:
				if root.left != node_to_find and root.right != node_to_find:
					if root.left:
						output.append(root.left.data)
					if root.right:
						output.append(root.right.data)
			else:
				queue.append((root.left, level - 1))
				queue.append((root.right, level - 1))
		return output if output else [-1]

	def findLevel(self, root, target, level):
		if root is None:
			return 0
		if root == target:
			return level
		left = self.findLevel(root.left, target, level + 1)
		right = self.findLevel(root.right, target, level + 1)
		return left + right


class Solution:

	def printCousins(self, root, node_to_find):
		q = [root]
		lis = []
		dic = {}
		l = 0
		lev = {}
		diss = {}
		while q:
			res = []
			for i in range(len(q)):
				node = q.pop(0)
				if node.left:
					q.append(node.left)
					lev[node.left.data] = node.data
				if node.right:
					q.append(node.right)
					lev[node.right.data] = node.data
				dic[node.data] = l
				res.append(node.data)
			diss[l] = res
			l += 1
		k = dic[node_to_find.data]
		if len(diss[k]) == 1:
			return [-1]
		for i in diss[k]:
			if lev[node_to_find.data] != lev[i]:
				lis.append(i)
		if len(lis) == 0:
			lis.append(-1)
		return lis


class Solution:

	def printCousins(self, root, node_to_find):
		queue = [root]
		marker = True
		while queue and marker:
			size = len(queue)
			for i in range(size):
				node = queue.pop(0)
				if node.left == node_to_find or node.right == node_to_find:
					marker = False
				else:
					if node.left:
						queue.append(node.left)
					if node.right:
						queue.append(node.right)
		ans = []
		if len(queue) == 0:
			return [-1]
		else:
			while queue:
				node = queue.pop(0)
				ans.append(node.data)
		return ans


from collections import defaultdict

class Solution:

	def printCousins(self, root, node_to_find):
		if not root:
			return
		ans = []
		mp = defaultdict()

		def parent(root):
			if not root:
				return
			mp[root.left] = root
			mp[root.right] = root
			parent(root.left)
			parent(root.right)
		parent(root)
		q = deque()
		q.append(root)
		flag = False
		while q:
			size = len(q)
			v = []
			for i in range(size):
				node = q.popleft()
				if node == node_to_find:
					flag = True
				else:
					v.append(node)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			if flag:
				break
		for i in range(len(v)):
			if mp[v[i]] == mp[node_to_find]:
				continue
			else:
				ans.append(v[i].data)
		if len(ans) == 0:
			return [-1]
		else:
			return ans


from collections import deque

class Solution:

	def makrparent(self, node):
		if node.left:
			self.parent[node.left] = node
			self.makrparent(node.left)
		if node.right:
			self.parent[node.right] = node
			self.makrparent(node.right)

	def printCousins(self, root, node_to_find):
		if root.data == node_to_find:
			return -1
		self.parent = {root: None}
		self.makrparent(root)
		(flag, node) = (True, None)
		q = deque()
		q.append(root)
		while q:
			nq = deque()
			while q:
				top = q.popleft()
				if top.left:
					if top.left == node_to_find:
						(flag, parent) = (False, self.parent[top.left])
					nq.append(top.left)
				if top.right:
					if top.right == node_to_find:
						(flag, parent) = (False, self.parent[top.right])
					nq.append(top.right)
			if not flag:
				break
			else:
				q = nq
		res = []
		empty = True
		for i in nq:
			if self.parent[i] != parent:
				empty = False
				res.append(i.data)
		return [-1] if empty else res


class Solution:

	def printCousins(self, root, node_to_find):
		if root.data == node_to_find.data:
			return [-1]
		l = root
		global a, k
		k = []

		def sol(root, k, level):
			global a
			if root:
				if root.left or root.right:
					if root.left == k:
						a = [root, level + 1]
					if root.right == k:
						a = [root, level + 1]
				sol(root.left, k, level + 1)
				sol(root.right, k, level + 1)
		sol(root, node_to_find, 0)

		def sols(l, level):
			global k
			if l:
				if level == a[1] - 1:
					if l != a[0]:
						if l.left:
							k.append(l.left.data)
						if l.right:
							k.append(l.right.data)
				sols(l.left, level + 1)
				sols(l.right, level + 1)
		sols(l, 0)
		if k:
			return k
		return [-1]


class Solution:

	def printCousins(self, root, node_to_find):
		(parent, level) = ({}, {})
		level[root.data] = 0
		parent[root.data] = -1
		curr = root
		st = []
		st.append(curr)
		while len(st) > 0 or curr != None:
			while curr.left != None:
				parent[curr.left.data] = curr.data
				level[curr.left.data] = level[curr.data] + 1
				curr = curr.left
				st.append(curr)
			while len(st) > 0 and st[-1].right == None:
				st.pop()
			if len(st) > 0:
				curr = st.pop()
				parent[curr.right.data] = curr.data
				level[curr.right.data] = level[curr.data] + 1
				curr = curr.right
				st.append(curr)
			else:
				curr = None
		ans = []
		(l, p) = (level[node_to_find.data], parent[node_to_find.data])
		k = list(level.keys())
		k.sort()
		for i in k:
			if level[i] == l and parent[i] != p:
				ans.append(i)
		if len(ans) == 0:
			ans = [-1]
		return ans


class Solution:

	def printCousins(self, root, node_to_find):
		downlevel = self.findLevel(root, node_to_find, 0)
		_list = []
		if downlevel > 1:
			self.nodes(root.left, downlevel, 1, _list, node_to_find)
			self.nodes(root.right, downlevel, 1, _list, node_to_find)
		if not _list:
			_list = _list + [-1]
		return _list

	def nodes(self, root, downlevel, level, _list, node_to_find):
		if not root:
			return
		if downlevel - level > 1:
			self.nodes(root.left, downlevel, 1 + level, _list, node_to_find)
			self.nodes(root.right, downlevel, 1 + level, _list, node_to_find)
		elif root.left and root.left == node_to_find or (root.right and root.right == node_to_find):
			return
		else:
			if root.left:
				_list.append(root.left.data)
			if root.right:
				_list.append(root.right.data)

	def findLevel(self, root, node_to_find, level):
		if root == None:
			return 0
		if root == node_to_find:
			return level
		downlevel = self.findLevel(root.left, node_to_find, level + 1)
		if downlevel != 0:
			return downlevel
		return self.findLevel(root.right, node_to_find, level + 1)


class Solution:

	def printCousins(self, root, node_to_find):
		if root is None:
			return [-1]
		queue_list = []
		queue_list.append(root)
		ans = []
		flag_var = 0
		while len(queue_list) > 0:
			size = len(queue_list)
			while size > 0:
				size -= 1
				node_o = queue_list.pop(0)
				if node_o.left is not None and node_o.left == node_to_find or (node_o.right is not None and node_o.right == node_to_find):
					flag_var = 1
				else:
					if node_o.left is not None:
						queue_list.append(node_o.left)
					if node_o.right is not None:
						queue_list.append(node_o.right)
			if flag_var == 1:
				break
		for i in queue_list:
			ans.append(i.data)
		if len(ans) == 0:
			return [-1]
		return ans


class Solution:

	def printCousins(self, root, node_to_find):

		def helper(x):
			ans = []
			q = []
			t = []
			if not x:
				return ans
			q.append(x)
			while q:
				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)
				ans.append(t)
				t = []
			return ans
		a = helper(root)
		level = 0
		for i in range(len(a)):
			b = a[i]
			for j in b:
				if j == node_to_find:
					level = i
					break
		c = a[level - 1]
		ans = []
		for i in c:
			if i.left != node_to_find and i.right != node_to_find:
				if i.left:
					ans.append(i.left.data)
				if i.right:
					ans.append(i.right.data)
		if not ans:
			return [-1]
		return ans


class queue:

	def __init__(self):
		self.lists = deque()
		self.size = 0

	def enqueue(self, data):
		self.lists.append(data)
		self.size += 1

	def dequeue(self):
		if self.size == 0:
			return -1
		else:
			temp = self.lists.popleft()
			self.size -= 1
			return temp

	def isempty(self):
		return self.size == 0

class Solution:

	def getData(self, root, data):
		q = queue()
		q.enqueue(root)
		currentNode = None
		nextLevel = 0
		result = []
		while q.isempty() != True:
			count = q.size
			if currentNode:
				nextLevel += 1
			while count != 0:
				temp = q.dequeue()
				if nextLevel == 2:
					result.append(temp.data)
				if temp.left:
					if temp.left.data == data:
						currentNode = temp
						nextLevel += 1
					q.enqueue(temp.left)
				if temp.right:
					if temp.right.data == data:
						currentNode = temp
						nextLevel += 1
					q.enqueue(temp.right)
				count -= 1
			if len(result) >= 1:
				break
		if currentNode and len(result) > 0:
			siblings = []
			mainResult = []
			if currentNode.left:
				siblings.append(currentNode.left.data)
			if currentNode.right:
				siblings.append(currentNode.right.data)
			for i in result:
				if i not in siblings:
					mainResult.append(i)
			return mainResult
		return []

	def printCousins(self, root, node_to_find):
		data = node_to_find.data
		result = self.getData(root, data)
		if len(result) == 0:
			return [-1]
		return result


from collections import deque

class Solution:

	def printCousins(self, root, node_to_find):
		if root == node_to_find:
			return [-1]
		q = deque([root])
		while q:
			Len = len(q)
			thisLevel = 0
			for _ in range(Len):
				node = q.popleft()
				if node.left and node.left == node_to_find or (node.right and node.right == node_to_find):
					thisLevel = 1
					continue
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			if thisLevel:
				if not q:
					return [-1]
				return [node.data for node in q]
		return [-1]


class Solution:

	def makeParentMappings(self, root, mappings):
		queue = [root]
		while len(queue) != 0:
			node = queue.pop(0)
			if node.left is not None:
				queue.append(node.left)
				mappings[node.left] = node
			if node.right is not None:
				queue.append(node.right)
				mappings[node.right] = node

	def printCousins(self, root, node_to_find):
		ans = []
		mappings = {}
		self.makeParentMappings(root, mappings)
		levels = []
		level = -1
		found = False
		queue = [root]
		while len(queue) != 0:
			size = len(queue)
			if level != -1 and found:
				break
			res = []
			for i in range(size):
				node = queue.pop(0)
				if node == node_to_find:
					found = True
				if node.left is not None:
					queue.append(node.left)
				if node.right is not None:
					queue.append(node.right)
				res.append(node)
			levels.append(res)
			level += 1
		nodes = levels[level]
		for i in nodes:
			if i != node_to_find:
				if mappings[node_to_find] != mappings[i]:
					ans.append(i.data)
		if not len(ans) > 0:
			ans.append(-1)
		return ans


import ctypes

class Solution:

	def printCousins(self, root, node_to_find):
		if not root:
			return
		q = []
		q.append(root)
		ans = []
		while q:
			n = len(q)
			flag = False
			for i in range(n):
				temp = q.pop(0)
				if temp.left == node_to_find or temp.right == node_to_find:
					flag = True
				else:
					if temp.left:
						q.append(temp.left)
					if temp.right:
						q.append(temp.right)
			if flag == True:
				if q:
					res = [n.data for n in q]
					return res
				else:
					return [-1]
		return [-1]


class Solution:

	def printCousins(self, root, node_to_find):
		ans = []
		if root == node_to_find:
			ans.append(-1)
			return ans
		q = [root]
		f = False
		while q and (not f):
			c = len(q)
			while c > 0:
				node = q.pop(0)
				if node.left == node_to_find or node.right == node_to_find:
					f = 1
				else:
					if node.left:
						q.append(node.left)
					if node.right:
						q.append(node.right)
				c -= 1
		if f:
			c = len(q)
			if c == 0:
				ans.append(-1)
				return ans
			for i in range(c):
				ans.append(q.pop(0).data)
		else:
			ans.append(-1)
		return ans


class Node:

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

class Solution:

	def printCousins(self, root, node_to_find):
		if root is None:
			return root
		elif root == node_to_find:
			return [-1]
		else:
			import collections
			q = collections.deque()
			q.append(root)
			sibiling = []
			d = {}
			count = 0
			req = 0
			while q:
				level = []
				for i in range(len(q)):
					node = q.popleft()
					if node:
						level.append(node.data)
					if node.left == node_to_find or node.right == node_to_find:
						req = req + count
						if node.left:
							sibiling.append(node.left.data)
						if node.right:
							sibiling.append(node.right.data)
					if node.left:
						q.append(node.left)
					if node.right:
						q.append(node.right)
				count = count + 1
				d[count] = level
			ans = []
			cousins = []
			for key in list(d.keys()):
				if key == req + 2:
					ans = d[key]
			for element in ans:
				if element not in sibiling:
					cousins.append(element)
			if len(cousins) != 0:
				return cousins
			else:
				return [-1]


class Solution:

	def printCousins(self, root, node):
		l = []
		q = [[root, None, 0]]
		c = 0
		m = -1
		while c != len(q):
			t = q[c][0]
			g = q[c][1]
			p = q[c][2]
			if t == node:
				m = p
				k = c
			if t.left:
				q.append([t.left, t, p + 1])
			if t.right:
				q.append([t.right, t, p + 1])
			c += 1
		l = []
		for i in q:
			if i[2] == m:
				if i[0] != node and i[1] != q[k][1]:
					l.append(i[0].data)
		if len(l) == 0:
			return [-1]
		return l


class Solution:

	def printCousins(self, root, node_to_find):
		ans = []
		queue = [root]
		flag = 1
		while queue and flag:
			for i in range(len(queue)):
				cur = queue.pop(0)
				if cur.left == node_to_find or cur.right == node_to_find:
					flag = 0
				else:
					if cur.left:
						queue.append(cur.left)
					if cur.right:
						queue.append(cur.right)
		for i in queue:
			ans.append(i.data)
		return ans if ans else [-1]


class Solution:

	def printCousins(self, root, node_to_find):
		ans = []
		mp = {}
		queue = [root]
		while queue:
			temp = []
			for i in range(len(queue)):
				cur = queue.pop(0)
				temp.append(cur)
				if cur.left:
					mp[cur.left] = cur
					queue.append(cur.left)
				if cur.right:
					queue.append(cur.right)
					mp[cur.right] = cur
			if node_to_find in temp:
				for i in temp:
					if mp.get(i) != mp.get(node_to_find, None):
						ans.append(i.data)
				break
		if ans:
			return ans
		return [-1]


class Solution:

	def printCousins(self, root, n):
		info = {}
		q = [(root, -1)]
		depth = 0
		ans = []
		while q:
			x = len(q)
			info = {}
			found = False
			masterParent = None
			while x:
				x -= 1
				(node, parent) = q.pop(0)
				info[parent] = info.get(parent, []) + [node.data]
				if node.data == n.data:
					masterParent = parent
					found = True
				if node.left:
					q.append((node.left, node.data))
				if node.right:
					q.append((node.right, node.data))
			if found:
				del info[masterParent]
				for val in info.values():
					ans.extend(val)
				break
		return sorted(ans) if len(ans) else [-1]


class Solution:

	def printCousins(self, root, node_to_find):
		if node_to_find == root:
			return [-1]
		q = []
		q.append([root, 0])
		ignore = set()
		temp = 0
		while q:
			p = q.pop(0)
			node = p[0]
			level = p[1]
			if node.left == node_to_find or node.right == node_to_find:
				temp = level + 1
				if node.left:
					ignore.add(node.left)
				if node.right:
					ignore.add(node.right)
				break
			if node.left:
				q.append([node.left, level + 1])
			if node.right:
				q.append([node.right, level + 1])
		q1 = []
		q1.append([root, 0])
		ans = []
		while q1:
			p = q1.pop(0)
			node = p[0]
			level = p[1]
			if level == temp:
				if node not in ignore:
					ans.append(node.data)
			if node.left:
				q1.append([node.left, level + 1])
			if node.right:
				q1.append([node.right, level + 1])
		if len(ans) == 0:
			return [-1]
		return ans


class Solution:

	def printCousins(self, root, node_to_find):
		que = deque([(root, None)])
		ans = []
		while que:
			n = len(que)
			(level, found) = ([], False)
			node_to_find_parent = None
			for i in range(n):
				(curr, parent) = que.popleft()
				if curr == node_to_find:
					node_to_find_parent = parent
					found = True
				level.append((curr, parent))
				if curr.left:
					que.append((curr.left, curr))
				if curr.right:
					que.append((curr.right, curr))
			if found:
				for (node, par) in level:
					if par != node_to_find_parent:
						ans.append(node.data)
		return ans if ans else [-1]


class Solution:

	def printCousins(self, root, node_to_find):
		q = []
		a = {}
		x = 0
		count = 0
		final = []
		q.append(root)
		while q != []:
			cq = len(q)
			level = []
			count += 1
			for i in range(cq):
				d = q.pop(0)
				level.append(d.data)
				if d == node_to_find:
					x = count - 1
				if d.left != None:
					q.append(d.left)
					if a.get(d.left.data) == None:
						a[d.left.data] = d.data
				if d.right != None:
					q.append(d.right)
					if a.get(d.right.data) == None:
						a[d.right.data] = d.data
			final.append(level)
		if a.get(node_to_find.data) == None:
			return [-1]
		z = a[node_to_find.data]
		fin = []
		for i in final[x]:
			if a[i] != z:
				fin.append(i)
		if fin == []:
			return [-1]
		return fin


from collections import *

class Solution:

	def printCousins(self, root, node_to_find):
		if not root:
			return [-1]
		if root == node_to_find:
			return [-1]
		if not node_to_find:
			return [-1]
		q = deque([root])
		while len(q) > 0:
			qLen = len(q)
			nextLevelNodes = []
			found = False
			for _ in range(qLen):
				top = q.popleft()
				if top.left == node_to_find or top.right == node_to_find:
					found = True
					continue
				if top.left:
					nextLevelNodes.append(top.left)
				if top.right:
					nextLevelNodes.append(top.right)
			if found:
				if len(nextLevelNodes) == 0:
					return [-1]
				return list(map(lambda x: x.data, nextLevelNodes))
			q.extend(nextLevelNodes)
		return [-1]


class Solution:

	def printCousins(self, root, node_to_find):
		if root is None:
			return None
		queue = [root]
		marker = True
		while queue and marker:
			size = len(queue)
			for i in range(size):
				rootNode = queue.pop(0)
				if rootNode.left == node_to_find or rootNode.right == node_to_find:
					marker = False
				else:
					if rootNode.left:
						queue.append(rootNode.left)
					if rootNode.right:
						queue.append(rootNode.right)
		if not queue:
			return [-1]
		else:
			result = []
			while queue:
				node = queue.pop(0)
				result.append(node.data)
			return result


class Solution:

	def printCousins(self, root, node_to_find):

		def find_level_parent(root, x, level):
			if root:
				if root == x:
					return level
				return find_level_parent(root.left, x, level + 1) or find_level_parent(root.right, x, level + 1)
			return 0

		def find_sibling(root, node):
			if root:
				if root.left == node:
					return root.right
				if root.right == node:
					return root.left
				return find_sibling(root.left, node) or find_sibling(root.right, node)
			return None
		l = find_level_parent(root, node_to_find, 0)
		q = deque()
		q.append(root)
		level = 0
		res = []
		while len(q):
			x = len(q)
			for _ in range(x):
				node = q.popleft()
				if level == l:
					res.append(node)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			level += 1
			if level > l:
				break
		sibling = find_sibling(root, node_to_find)
		ans = []
		for i in res:
			if i != sibling and i != node_to_find:
				ans.append(i.data)
		if len(ans) == 0:
			return [-1]
		return ans
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

def pointer(root, n):
	if root == None:
		return None
	if root.data == n:
		return root
	l = pointer(root.left, n)
	if l != None and l.data == n:
		return l
	r = pointer(root.right, n)
	return r
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		n = int(input())
		s = input()
		root = buildTree(s)
		p = pointer(root, n)
		ob = Solution()
		ans = ob.printCousins(root, p)
		for i in range(len(ans)):
			print(ans[i], end=' ')
		print()


class Solution:

	def printCousins(self, root, node_to_find):
		que = [root]
		while que:
			size = len(que)
			tmp = False
			for i in range(size):
				node = que.pop(0)
				if node.left == node_to_find or node.right == node_to_find:
					tmp = True
				else:
					if node.left is not None:
						que.append(node.left)
					if node.right is not None:
						que.append(node.right)
			if tmp == True:
				if que:
					out = [n.data for n in que]
					return out
				else:
					return [-1]
		return [-1]
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

def pointer(root, n):
	if root == None:
		return None
	if root.data == n:
		return root
	l = pointer(root.left, n)
	if l != None and l.data == n:
		return l
	r = pointer(root.right, n)
	return r
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		n = int(input())
		s = input()
		root = buildTree(s)
		p = pointer(root, n)
		ob = Solution()
		ans = ob.printCousins(root, p)
		for i in range(len(ans)):
			print(ans[i], end=' ')
		print()


class Solution:

	def makeParentMappings(self, root, mappings):
		queue = [root]
		while len(queue) != 0:
			node = queue.pop(0)
			if node.left is not None:
				queue.append(node.left)
				mappings[node.left] = node
			if node.right is not None:
				queue.append(node.right)
				mappings[node.right] = node

	def printCousins(self, root, node_to_find):
		ans = []
		mappings = {}
		self.makeParentMappings(root, mappings)
		levels = []
		level = -1
		found = False
		queue = [root]
		while len(queue) != 0:
			size = len(queue)
			if level != -1 and found:
				break
			res = []
			for i in range(size):
				node = queue.pop(0)
				if node == node_to_find:
					found = True
				if node.left is not None:
					queue.append(node.left)
				if node.right is not None:
					queue.append(node.right)
				res.append(node)
			levels.append(res)
			level += 1
		nodes = levels[level]
		for i in nodes:
			if i != node_to_find:
				if mappings[node_to_find] != mappings[i]:
					ans.append(i.data)
		if not len(ans) > 0:
			ans.append(-1)
		return ans
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

def pointer(root, n):
	if root == None:
		return None
	if root.data == n:
		return root
	l = pointer(root.left, n)
	if l != None and l.data == n:
		return l
	r = pointer(root.right, n)
	return r
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		n = int(input())
		s = input()
		root = buildTree(s)
		p = pointer(root, n)
		ob = Solution()
		ans = ob.printCousins(root, p)
		for i in range(len(ans)):
			print(ans[i], end=' ')
		print()


from collections import deque

class Solution:

	def printCousins(self, root, node_to_find):
		q = deque()
		if root.data == node_to_find.data:
			return [-1]
		flag = 0
		q.append(root)
		while q:
			n = len(q)
			for i in range(n):
				nod = q.popleft()
				if nod.left and nod.left.data == node_to_find.data or (nod.right and nod.right.data == node_to_find.data):
					flag = 1
					continue
				if nod.left:
					q.append(nod.left)
				if nod.right:
					q.append(nod.right)
			if flag:
				break
		if len(q) == 0:
			return [-1]
		for i in range(len(q)):
			q[i] = q[i].data
		return q
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

def pointer(root, n):
	if root == None:
		return None
	if root.data == n:
		return root
	l = pointer(root.left, n)
	if l != None and l.data == n:
		return l
	r = pointer(root.right, n)
	return r
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		n = int(input())
		s = input()
		root = buildTree(s)
		p = pointer(root, n)
		ob = Solution()
		ans = ob.printCousins(root, p)
		for i in range(len(ans)):
			print(ans[i], end=' ')
		print()


class Solution:

	def printCousins(self, root, node_to_find):
		q = [(None, root, 0)]
		a = []
		p = None
		found = 0
		while q:
			(z, c, v) = q.pop(0)
			if found and v > found:
				break
			for b in (c.left, c.right):
				if b:
					if b == node_to_find:
						found = v + 1
						p = c
					q.append((c, b, v + 1))
			a.append((z, c, v))
		l = [c.data for (z, c, v) in a if v == found and z != p]
		if not l:
			return [-1]
		return l
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

def pointer(root, n):
	if root == None:
		return None
	if root.data == n:
		return root
	l = pointer(root.left, n)
	if l != None and l.data == n:
		return l
	r = pointer(root.right, n)
	return r
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		n = int(input())
		s = input()
		root = buildTree(s)
		p = pointer(root, n)
		ob = Solution()
		ans = ob.printCousins(root, p)
		for i in range(len(ans)):
			print(ans[i], end=' ')
		print()


from collections import deque

class Solution:

	def printCousins(self, root, node_to_find):
		q = deque()
		q.append((root, 1))
		ans = []
		while q:
			flag = False
			for (node, idx) in q:
				if node == node_to_find:
					idx1 = idx
					flag = True
					break
			if flag:
				if idx1 & 1:
					idx2 = idx1 - 1
				else:
					idx2 = idx1 + 1
				for (node, idx) in q:
					if idx != idx1 and idx != idx2:
						ans.append(node.data)
				break
			else:
				size = len(q)
				for _ in range(size):
					(node, idx) = q.popleft()
					if node.left:
						q.append((node.left, 2 * idx))
					if node.right:
						q.append((node.right, 2 * idx + 1))
		if len(ans) == 0:
			return [-1]
		return ans
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

def pointer(root, n):
	if root == None:
		return None
	if root.data == n:
		return root
	l = pointer(root.left, n)
	if l != None and l.data == n:
		return l
	r = pointer(root.right, n)
	return r
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		n = int(input())
		s = input()
		root = buildTree(s)
		p = pointer(root, n)
		ob = Solution()
		ans = ob.printCousins(root, p)
		for i in range(len(ans)):
			print(ans[i], end=' ')
		print()


class Solution:

	def printCousins(self, root, x):
		if root is None:
			return [-1]
		q = [root]
		flag = 0
		while len(q) > 0:
			for i in range(len(q)):
				curr = q.pop(0)
				if curr.left == x or curr.right == x:
					flag = 1
				else:
					if curr.left is not None:
						q.append(curr.left)
					if curr.right is not None:
						q.append(curr.right)
			if flag == 1:
				break
		n = len(q)
		if n == 0:
			return [-1]
		ans = []
		for i in range(n):
			ans.append(q.pop(0).data)
		return ans


class Solution:

	def printCousins(self, root, node_to_find):
		q = []
		q.append(root)
		m = True
		while q and m:
			s = len(q)
			for i in range(s):
				e = q[0]
				q.pop(0)
				if e.left == node_to_find or e.right == node_to_find:
					m = False
				else:
					if e.left != None:
						q.append(e.left)
					if e.right != None:
						q.append(e.right)
		if len(q) == 0:
			return [-1]
		else:
			r = []
			while q:
				r.append(q[0].data)
				q.pop(0)
			return r


from collections import deque

class Solution:

	def printCousins(self, root, node_to_find):

		def lvl_search(lvl_wise):
			ind = -1
			for i in range(len(lvl_wise)):
				(node, parent) = lvl_wise[i]
				if node == node_to_find:
					ind = i
					break
			if ind > -1:
				par = lvl_wise[ind][1]
				res = []
				for (node, parent) in lvl_wise:
					if parent != par:
						res.append(node.data)
				return res
			return []
		lvl_wise = []
		cur_height = 0
		trav = deque([(root, 0, None)])
		while trav:
			(cur, height, parent) = trav.popleft()
			if cur.left:
				trav.append((cur.left, height + 1, cur))
			if cur.right:
				trav.append((cur.right, height + 1, cur))
			if height == cur_height:
				lvl_wise.append((cur, parent))
			else:
				search = lvl_search(lvl_wise)
				if search:
					return search
				cur_height = height
				lvl_wise = [(cur, parent)]
		search = lvl_search(lvl_wise)
		if search:
			return search
		return [-1]


class Solution:

	def __init__(self):
		self.h = 0
		self.l = {}

	def printCousins(self, root, node_to_find):

		def dfs(root, h):
			if root == None:
				return
			if h in self.l:
				arr = self.l[h]
				arr.append(root.data)
				self.l[h] = arr
			else:
				self.l[h] = [root.data]
			if root.left != None:
				if root.left.data == node_to_find.data:
					self.h = h + 1
					return
			if root.right != None:
				if root.right.data == node_to_find.data:
					self.h = h + 1
					return
			a = dfs(root.left, h + 1)
			b = dfs(root.right, h + 1)
			return
		dfs(root, 1)
		if self.h in self.l:
			if self.l[self.h] != []:
				return self.l[self.h]
			else:
				return [-1]
		return [-1]


class Solution:

	def printCousins(self, root, node_to_find):
		hm = {}
		arr = []
		q = [root, None]
		k = 0
		if root == node_to_find:
			return [-1]
		while q:
			t = q.pop(0)
			if not t and q:
				q.append(None)
			elif not t and (not q):
				break
			else:
				if t.left:
					q.append(t.left)
					hm[t.left] = t
				if t.right:
					q.append(t.right)
					hm[t.right] = t
				arr.append(t)
				if t == node_to_find:
					k = 1
				if not q[0]:
					if k == 1:
						break
					arr = []
		brr = []
		if len(arr) == 1:
			return [-1]
		if len(arr) == 2:
			if hm[arr[0]] == hm[arr[1]]:
				return [-1]
		for i in range(len(arr)):
			if hm[arr[i]] != hm[node_to_find]:
				brr.append(arr[i].data)
		return brr


class Solution:

	def printCousins(self, root, node_to_find):
		q = []
		q.append(root)
		flag = True
		while len(q) and flag:
			n = len(q)
			for i in range(n):
				node = q.pop(0)
				if node.left == node_to_find or node.right == node_to_find:
					flag = False
				else:
					if node.left:
						q.append(node.left)
					if node.right:
						q.append(node.right)
		ans = []
		if len(q) == 0:
			return [-1]
		while len(q):
			node = q.pop(0)
			ans.append(node.data)
		return ans


class Solution:

	def printCousins(self, root, node_to_find):
		if not root:
			return -1
		found = False
		queue = [root]
		while queue and (not found):
			(i, l) = (0, len(queue))
			while i < l:
				q = queue.pop(0)
				if q.left == node_to_find or q.right == node_to_find:
					found = True
				else:
					if q.left:
						queue.append(q.left)
					if q.right:
						queue.append(q.right)
				i += 1
		res = []
		for ele in queue:
			res.append(ele.data)
		if res == []:
			return [-1]
		else:
			return res


class Solution:

	def printCousins(self, root, no):
		from collections import deque
		if root == no:
			return [-1]
		q = deque()
		q.append(root)
		ans = []
		while q:
			l = []
			t1 = False
			for i in range(len(q)):
				t = q.popleft()
				if t.left:
					q.append(t.left)
					l.append((t.left.data, t.data))
				if t.right:
					q.append(t.right)
					l.append((t.right.data, t.data))
			for val in l:
				if val[0] == no.data:
					t1 = True
					break
			if t1:
				break
		for val in l:
			if val[0] == no.data:
				t = val[1]
		for val in l:
			if val[1] != t:
				ans.append(val[0])
		if len(ans) == 0:
			return [-1]
		return ans


from collections import deque

class Solution:

	def printCousins(self, root, node_to_find):
		if not root:
			return [-1]
		q = deque()
		q.append(root)
		flag = False
		ans = []
		while q:
			s = len(q)
			while s > 0:
				i = q.popleft()
				if i.left == node_to_find or i.right == node_to_find:
					flag = True
				else:
					if i.left:
						q.append(i.left)
					if i.right:
						q.append(i.right)
				s -= 1
			if flag:
				break
		if flag:
			while q:
				cur = q.popleft()
				ans.append(cur.data)
		if ans:
			return ans
		return [-1]


class Solution:

	def printCousins(self, root, node_to_find):
		res = {}
		h = 0
		parent = None
		res[h, parent] = []
		self.helper(root, res, h, parent)
		arr = []
		(th, tp) = (0, None)
		for (k1, v1) in res.keys():
			if node_to_find.data in res[k1, v1]:
				(th, tp) = (k1, v1)
		for (k1, v1) in res.keys():
			if k1 == th and v1 != tp:
				arr.extend(res[k1, v1])
		if len(arr):
			arr.sort()
			return arr
		return [-1]

	def helper(self, root, res, h, parent):
		if root == None:
			return
		if (h, parent) in res.keys():
			res[h, parent].append(root.data)
		else:
			res[h, parent] = [root.data]
		self.helper(root.left, res, h + 1, root)
		self.helper(root.right, res, h + 1, root)


class Solution:

	def printCousins(self, root, node_to_find):
		target = node_to_find
		l1 = [root]
		l2 = []
		f = False
		sibling = None
		while len(l1) != 0:
			for node in l1:
				if node.left != None:
					l2.append(node.left)
				if node.right != None:
					l2.append(node.right)
				if node.left == target:
					sibling = node.right
					f = True
				if node.right == target:
					sibling = node.left
					f = True
			if f:
				break
			l1 = l2[:]
			l2 = []
		ans = []
		for node in l2:
			if node != sibling and node != target:
				ans.append(node.data)
		if len(ans) == 0:
			return [-1]
		return ans


class Solution:

	def printCousins(self, root, node_to_find):
		A = root
		B = node_to_find
		ans = []
		q = []
		q.append(A)
		while q:
			n = len(q)
			found = False
			for i in range(len(q)):
				cur = q[0]
				q.pop(0)
				l = cur.left
				r = cur.right
				if l and l == B or (r and r == B):
					found = True
					continue
				if l:
					q.append(l)
				if r:
					q.append(r)
			if found:
				break
		res = []
		if found:
			if q:
				while q:
					res.append(q.pop(0).data)
				return res
			else:
				return [-1]
		else:
			return [-1]


class Solution:

	def printCousins(self, root, x):
		q = []
		q.append(root)
		y = 0
		a = []
		while len(q) > 0:
			s = len(q)
			if y == 1:
				for i in range(len(q)):
					a.append(q[i].data)
				return a
			while s > 0:
				node = q[0]
				if node.left != x and node.right != x:
					if node.left != None:
						q.append(node.left)
					if node.right != None:
						q.append(node.right)
				else:
					y = 1
				q.pop(0)
				s -= 1
		a.append(-1)
		return a


class Solution:

	def printCousins(self, root, p):
		mp = dict()
		q = []
		q.append(root)
		mp[root] = None
		ans = []
		flag = False
		l1 = []
		while len(q) > 0:
			l = []
			flag = False
			for i in range(len(q)):
				c = q.pop(0)
				l.append(c)
				if c.data == p.data:
					flag = True
				if c.left:
					q.append(c.left)
					mp[c.left] = c
				if c.right:
					q.append(c.right)
					mp[c.right] = c
			if flag:
				l1 = l
				break
		for i in range(len(l1)):
			if mp[l1[i]] != mp[p]:
				ans.append(l1[i].data)
		return ans if ans != [] else [-1]


class Solution:

	def printCousins(self, root, node_to_find):
		if root is node_to_find:
			return [-1]
		queue = [root]
		while queue:
			newLevel = []
			(sibling, foundNode) = (None, False)
			for node in queue:
				if not sibling and node.left is node_to_find:
					foundNode = True
					sibling = node.right
				if not sibling and node.right is node_to_find:
					foundNode = True
					sibling = node.left
				if node.left:
					newLevel.append(node.left)
				if node.right:
					newLevel.append(node.right)
			queue.clear()
			if foundNode:
				newLevel.remove(node_to_find)
				if sibling:
					newLevel.remove(sibling)
				return [node.data for node in newLevel] if newLevel else [-1]
			elif newLevel:
				queue.extend(newLevel)
		return [-1]


from collections import deque

class Solution:

	def __init__(self):
		self.list1 = []

	def printCousins(self, root, node_to_find):

		def traversal(root):
			if root == None:
				return None
			q = deque([])
			q.append(root)
			output = 0
			while len(q) > 0:
				count = len(q)
				while count > 0:
					temp = q.popleft()
					if temp.left == node_to_find or temp.right == node_to_find:
						output = 1
					else:
						if temp.left:
							self.list1.append(temp.left.data)
						if temp.right:
							self.list1.append(temp.right.data)
					if temp.left:
						q.append(temp.left)
					if temp.right:
						q.append(temp.right)
					count -= 1
				if output == 1:
					if self.list1 != []:
						return self.list1
					else:
						return [-1]
				output = 0
				self.list1 = []
			return [-1]
		return traversal(root)


class Solution:

	def printCousins(self, root, node_to_find):
		queue = [root]
		flag = False
		while queue and flag == False:
			size = len(queue)
			while size:
				size -= 1
				node = queue.pop(0)
				if node.left == node_to_find or node.right == node_to_find:
					flag = True
				else:
					if node.left:
						queue.append(node.left)
					if node.right:
						queue.append(node.right)
		if not queue:
			return [-1]
		else:
			ans = []
			while queue:
				ans.append(queue.pop(0).data)
		return ans


class Solution:

	def printCousins(self, root, node_to_find):

		def parent(root, par=None):
			nonlocal l
			nonlocal lvl
			if root:
				root.par = par
				if root == node_to_find:
					lvl = l
				l += 1
				parent(root.left, root)
				parent(root.right, root)
				l -= 1
		lvl = 0
		l = 0
		parent(root)
		q = [root]
		l = 0
		while q:
			qsize = len(q)
			if l == lvl:
				break
			for i in range(qsize):
				node = q.pop(0)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			l += 1
		ans = []
		for i in q:
			if i.par != node_to_find.par:
				ans.append(i.data)
		return ans if len(ans) != 0 else [-1]


class Solution:

	def printCousins(self, root, node_to_find):
		q = []
		result = []
		marker = True
		q.append(root)
		while len(q) and marker:
			size = len(q)
			while size:
				element = q.pop(0)
				if element.left == node_to_find or element.right == node_to_find:
					marker = False
				else:
					if element.left:
						q.append(element.left)
					if element.right:
						q.append(element.right)
				size -= 1
		if not len(q):
			return [-1]
		while len(q):
			result.append(q.pop(0).data)
		return result


class Solution:

	def printCousins(self, root, x):

		def solve(root):
			if not root:
				return None
			q = [root]
			lis = []
			flag = 0
			while q:
				n = len(q)
				while n:
					curr = q.pop(0)
					if curr.left == x or curr.right == x:
						flag = 1
					else:
						if curr.left:
							lis.append(curr.left.data)
						if curr.right:
							lis.append(curr.right.data)
					if curr.left:
						q.append(curr.left)
					if curr.right:
						q.append(curr.right)
					n -= 1
				if flag == 1:
					if len(lis):
						return lis
					else:
						return [-1]
				flag = 0
				lis = []
			return [-1]
		return solve(root)


class Solution:

	def find_level(self, root, d, level, par, node_to_find):
		global lvl
		global parent
		if not root:
			return
		if root.data == node_to_find.data:
			lvl = level
			parent = par
		if not root.data == node_to_find.data:
			if level in d:
				d[level].append([root.data, par])
			else:
				d[level] = [[root.data, par]]
		self.find_level(root.left, d, level + 1, root, node_to_find)
		self.find_level(root.right, d, level + 1, root, node_to_find)

	def printCousins(self, root, node_to_find):
		d = {}
		global lvl
		global parent
		lvl = None
		self.find_level(root, d, 1, root, node_to_find)
		if not lvl or lvl not in d:
			return [-1]
		if len(d[lvl]) == 1:
			if d[lvl][0][1] == parent:
				return [-1]
			return [d[lvl][0][0]]
		ans = []
		for (x, y) in d[lvl]:
			if y != parent:
				ans.append(x)
		return ans


class Solution:

	def printCousins(self, root, node_to_find):
		q = [(root, -1)]
		l = []
		level = 0
		(x, y, par) = (0, 0, 0)
		while q:
			n = len(q)
			z = []
			for i in range(n):
				(node, p) = q.pop(0)
				if node == node_to_find:
					(x, y, par) = (level, i, p)
				z.append((node.data, p))
				if node.left:
					q.append((node.left, node))
				if node.right:
					q.append((node.right, node))
			l.append(z)
			level += 1
		ans = []
		for i in range(len(l[x])):
			if i != y and l[x][i][1] != par:
				ans.append(l[x][i][0])
		if not ans:
			return [-1]
		return ans


def bttravel(root, n):
	import collections
	q = collections.deque()
	q.append(root)
	flag = 1
	while len(q) != 0 and flag:
		for i in range(len(q)):
			node = q.popleft()
			if node.left == n or node.right == n:
				flag = 0
			else:
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
	if len(q) == 0:
		return [-1]
	else:
		rs = []
		while q:
			rs.append(q.popleft().data)
		return rs

class Solution:

	def printCousins(self, root, node_to_find):
		return bttravel(root, node_to_find)


class Solution:

	def printCousins(self, root, node_to_find):
		k = []
		t = [root]

		def app(k, t, a):
			s = t
			t = []
			j = 0
			for i in s:
				if i.left is not None:
					t.append(i.left)
					if i.left == a:
						n = i
						j = 1
				if i.right is not None:
					t.append(i.right)
					if i.right == a:
						n = i
						j = 1
			if t == []:
				return
			if j == 1:
				for i in s:
					if i == n:
						continue
					else:
						if i.left is not None:
							k.append(i.left.data)
						if i.right is not None:
							k.append(i.right.data)
				return
			app(k, t, a)
		app(k, t, node_to_find)
		if k == []:
			return [-1]
		return k


class Solution:

	def printCousins(self, root, node_to_find):
		if root is None:
			return []
		result = []
		stack = [root]
		flag = False
		while len(stack) > 0:
			stack1 = stack
			stack = []
			if flag == False:
				while len(stack1) > 0:
					pop = stack1.pop(0)
					if pop.left == node_to_find or pop.right == node_to_find:
						flag = True
					else:
						if pop.left:
							stack.append(pop.left)
						if pop.right:
							stack.append(pop.right)
		while len(stack1) > 0:
			result.append(stack1.pop(0).data)
		if len(result) == 0:
			return [-1]
		return result


class Solution:

	def printCousins(self, root, node_to_find):
		if not root:
			return [-1]
		res = []
		q = []
		q.append(root)
		found = 0
		while q and found == 0:
			n = len(q)
			for i in range(n):
				curr = q.pop(0)
				if curr.left and curr.left == node_to_find or (curr.right and curr.right == node_to_find):
					found = 1
				else:
					if curr.left:
						q.append(curr.left)
					if curr.right:
						q.append(curr.right)
		if found:
			if not q:
				return [-1]
			for i in q:
				res.append(i.data)
			return res
		else:
			return [-1]


class Solution:

	def printCousins(self, root, node_to_find):
		if root == node_to_find:
			return [-1]
		ans = []
		f = False
		ans.append(root)
		while len(ans) != 0 and (not f):
			s = len(ans)
			while s != 0:
				p = ans.pop(0)
				if p.left == node_to_find or p.right == node_to_find:
					f = True
				else:
					if p.left:
						ans.append(p.left)
					if p.right:
						ans.append(p.right)
				s -= 1
		if f:
			if len(ans) == 0:
				return [-1]
			else:
				res = []
				for i in ans:
					res.append(i.data)
				return res
		else:
			return [-1]


class Solution:

	def __init__(self):
		self.level = 0
		self.parent = None

	def printCousins(self, root, node_to_find):
		self.find_level(root, node_to_find, 0, root)
		cousins = []
		self.helper(root, cousins, 0)
		if len(cousins) == 0:
			cousins.append(-1)
		return cousins

	def find_level(self, root, node, cur, par):
		if root is None:
			return
		if root == node:
			self.level = cur
			self.parent = par
			return
		self.find_level(root.left, node, cur + 1, root)
		self.find_level(root.right, node, cur + 1, root)

	def helper(self, root, cousins, cur_level):
		if root == self.parent:
			return
		if root is None:
			return
		if cur_level == self.level:
			cousins.append(root.data)
			return
		self.helper(root.left, cousins, cur_level + 1)
		self.helper(root.right, cousins, cur_level + 1)


class Solution:

	def printCousins(self, root, value):
		q = [(root, None, 0)]
		i = 0
		parent = -1
		level = -1
		while True:
			current = q[i][0]
			if current.left != None:
				if current.left.data == value.data:
					parent = current
					level = q[i][2] + 1
				q.append((current.left, current, q[i][2] + 1))
			if current.right != None:
				if current.right.data == value.data:
					parent = current
					level = q[i][2] + 1
				q.append((current.right, current, q[i][2] + 1))
			if i == len(q) - 1:
				break
			i += 1
		cousins = []
		for i in q:
			if i[2] == level and i[1].data != parent.data:
				cousins.append(i[0].data)
		if len(cousins) == 0:
			return [-1]
		else:
			return cousins


class Solution:

	def printCousins(self, root, node_to_find):
		k = [root]
		r = []
		t = 0
		x = 0
		while k != []:
			l = k.pop(0)
			if l.left != None:
				if l.left.data == node_to_find.data:
					t = 1
					r.append(l.left)
				else:
					r.append(l.left)
			if l.right != None:
				if l.right.data == node_to_find.data:
					t = 1
					r.append(l.right)
				else:
					r.append(l.right)
			if t == 1 and r:
				if l.right and r != []:
					r.pop()
				if l.left and r != []:
					r.pop()
				x = t
				t = 0
			if k == [] and x == 0:
				k = r
				r = []
			elif k == [] and x == 1:
				break
		m = []
		if r != []:
			for i in range(len(r)):
				m.append(r[i].data)
			return m
		else:
			return [-1]


from collections import deque

class Solution:

	def printCousins(self, root, node_to_find):
		queue = deque()
		queue.append((root, None))
		while len(queue) > 0:
			length = len(queue)
			index = 0
			level_nodes = []
			flag = False
			parent_node = None
			while index < length:
				(ele, parent) = queue.popleft()
				level_nodes.append((ele, parent))
				if ele == node_to_find:
					flag = True
					parent_node = parent
				if ele.left:
					queue.append((ele.left, ele))
				if ele.right:
					queue.append((ele.right, ele))
				index += 1
			if flag:
				result = [ele.data for (ele, parent) in level_nodes if parent != parent_node]
				if len(result) > 0:
					return result
				else:
					return [-1]
		return [-1]


class Solution:

	def __init__(self):
		self.result = []

	def printCousinsUtil(self, root, node_to_find, level):
		if level < 2 or root == None:
			return
		if level == 2:
			if root.left == node_to_find or root.right == node_to_find:
				return
			if root.left != None:
				self.result.append(root.left.data)
			if root.right != None:
				self.result.append(root.right.data)
		if level > 2:
			self.printCousinsUtil(root.left, node_to_find, level - 1)
			self.printCousinsUtil(root.right, node_to_find, level - 1)

	def getlevel(self, root, node_to_find, level):
		if root == None:
			return 0
		if root == node_to_find:
			return level
		if self.getlevel(root.left, node_to_find, level + 1) != 0:
			return self.getlevel(root.left, node_to_find, level + 1)
		return self.getlevel(root.right, node_to_find, level + 1)

	def printCousins(self, root, node_to_find):
		level = self.getlevel(root, node_to_find, 1)
		self.printCousinsUtil(root, node_to_find, level)
		if len(self.result) == 0:
			return [-1]
		return self.result


class Solution:

	def printCousins(self, root, node_to_find):
		res = []

		def getLevel(root, node, level):
			if root == None:
				return 0
			if root == node:
				return level
			l = getLevel(root.left, node, level + 1)
			if l != 0:
				return l
			l = getLevel(root.right, node, level + 1)
			return l

		def printC(root, node, level):
			if root == None or level < 2:
				return res
			if level == 2:
				if root.left == node or root.right == node:
					return res
				if root.left:
					res.append(root.left.data)
				if root.right:
					res.append(root.right.data)
				return res
			printC(root.left, node, level - 1)
			printC(root.right, node, level - 1)
			return res
		level = getLevel(root, node_to_find, 1)
		a = printC(root, node_to_find, level)
		if len(a) == 0:
			return [-1]
		else:
			return a