Given a Binary tree and a key in the binary tree, find the node right to the given key. If there is no node on right side, then return a node with value -1.
Example 1:
Input:
       10
     /    \
    2      6
   / \      \
  8   4      5
and key = 2
Output: 6
Explanation: We can see in the above tree
that the next right node of 2 is 6.
Example 2:
Input:
      10
    /     \
   2       6
  / \       \
 8   4       5
and key = 5
Output: -1
Explanation: We can see in the above tree 
that there's No next right node of 5.
So, the output is -1.
Your Task:
You don't need to read input or print anything. Your task is to complete the function nextRight() which takes root node of the tree and an integer key as input parameters and returns the next right node of the node with value key. 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1<=N<=10^{3}
1<=data of node<=10^{3}
1<=key<=10^{3}

Difficulty: EASY
Tags: Tree algorithms

Data structures

Graph traversal
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3



'''

class Node:

    def __init__(self,val):

        self.data=val

        self.left=None

        self.right=None

'''

from collections import deque

class Solution:

    def nextRight(self, root, key):

        #code here

Solutions:
from collections import deque

class Solution:

	def nextRight(self, root, key):
		x = []
		q = deque()
		q.append(root)
		while q:
			for i in range(len(q)):
				a = q.popleft()
				x.append(a.data)
				if a.left:
					q.append(a.left)
				if a.right:
					q.append(a.right)
			x.append('l')
		for i in range(len(x) - 1):
			if x[i] == key:
				if x[i + 1] == 'l':
					return Node(-1)
				return Node(x[i + 1])


from collections import deque

class Solution:

	def nextRight(self, root, key):
		l = [root]
		temp = Node(-1)
		while l:
			r = []
			size = len(l)
			for i in range(size):
				if l[i].data == key:
					if i < size - 1:
						curr = Node(l[i + 1].data)
						return curr
					else:
						return temp
				if l[i].left:
					r.append(l[i].left)
				if l[i].right:
					r.append(l[i].right)
			l = r
		return temp


from collections import deque

class Solution:

	def fun(self, root, level, l, res, key, t):
		if root == None:
			return
		if level >= len(l):
			l.append([])
			t.append([])
		if root.data == key:
			res[0] = level
		l[level].append(root)
		t[level].append(root.data)
		self.fun(root.left, level + 1, l, res, key, t)
		self.fun(root.right, level + 1, l, res, key, t)

	def nextRight(self, root, key):
		r = root
		(l, res) = ([], [0])
		t = []
		self.fun(root, 0, l, res, key, t)
		ind = res[0]
		t1 = l[ind]
		t2 = t[ind]
		v = t2.index(key)
		if v == len(t2) - 1:
			r.data = -1
			res[0] = r
		else:
			res[0] = t1[v + 1]
		return res[0]


from collections import deque

class Solution:

	def nextRight(self, root, key):
		if root is None:
			return Node(-1)
		qn = []
		q1 = []
		level = 0
		qn.append(root)
		q1.append(level)
		while len(qn) > 0:
			node = qn.pop(0)
			level = q1.pop(0)
			if node.data == key:
				if len(q1) == 0 or q1[0] != level:
					return Node(-1)
				return qn[0]
			if node.left is not None:
				qn.append(node.left)
				q1.append(level + 1)
			if node.right is not None:
				qn.append(node.right)
				q1.append(level + 1)
		return Node(-1)


class Solution:

	def nextRight(self, root, key):
		q = [root]
		ans = Node(-1)
		while q:
			lis = []
			for i in range(len(q)):
				node = q.pop(0)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
				if lis:
					if lis[-1] == key:
						return node
				lis.append(node.data)
		return ans


from collections import deque

class Solution:

	def nextRight(self, root, key):
		if key == root.data:
			return Node(-1)
		queue = deque()
		queue.append([root, 0])
		while queue:
			(node, level) = queue.popleft()
			if node.data == key:
				if not queue or queue[0][1] > level:
					return Node(-1)
				return queue[0][0]
			if node.left:
				queue.append([node.left, level + 1])
			if node.right:
				queue.append([node.right, level + 1])
		return Node(-1)
from collections import defaultdict
from collections import deque
from sys import stdin, stdout

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__':
	test_cases = int(input())
	for cases in range(test_cases):
		s = input()
		key = int(input())
		root = buildTree(s)
		ob = Solution()
		res = ob.nextRight(root, key)
		print(res.data)


from collections import deque

class Solution:

	def nextRight(self, root, key):
		queue = [root]
		while queue:
			l = len(queue)
			for i in range(1, l + 1):
				x = queue.pop(0)
				if x.data == key:
					if i != l:
						return queue[0]
					return Node(-1)
				if x.left:
					queue.append(x.left)
				if x.right:
					queue.append(x.right)


from collections import deque

class Solution:

	def nextRight(self, root, key):
		dq = deque()
		dq.append(root)
		while len(dq) > 0:
			currsize = len(dq)
			for i in range(currsize):
				temp = dq.popleft()
				if temp.data == key:
					if i == currsize - 1:
						return Node(-1)
					else:
						return dq.popleft()
				if temp.left != None:
					dq.append(temp.left)
				if temp.right != None:
					dq.append(temp.right)
		return Node(-1)


from collections import deque

class Solution:

	def nextRight(self, root, key):
		elements = deque()
		level = deque()
		elements.append(root)
		level.append(0)
		while len(elements) != 0:
			front = elements.popleft()
			curr_level = level.popleft()
			if front.data == key:
				if len(elements) == 0:
					return Node(-1)
				next_ele = elements.popleft()
				next_level = level.popleft()
				if next_level != curr_level:
					return Node(-1)
				else:
					return next_ele
			if front.left != None:
				elements.append(front.left)
				level.append(curr_level + 1)
			if front.right != None:
				elements.append(front.right)
				level.append(curr_level + 1)
		return Node(-1)


from collections import deque

class Solution:

	def nextRight(self, root, key):
		f = [root]
		s = []
		while len(f) > 0:
			node = f[0]
			f.pop(0)
			if node.data == key:
				if len(f) == 0:
					return Node(-1)
				return f[0]
			if node.left != None:
				s.append(node.left)
			if node.right != None:
				s.append(node.right)
			if len(f) == 0:
				f = s
				s = []


from collections import deque

class Solution:

	def nextRight(self, root, key):
		q = []
		q.append(root)
		q.append(-1)
		while q:
			l = len(q)
			for i in range(l):
				temp = q.pop(0)
				if temp == -1:
					continue
				else:
					if temp.data == key:
						if len(q):
							if q[0] == -1:
								root.data = -1
								return root
							else:
								return q[0]
						else:
							root.data = -1
							return root
					if temp.left:
						q.append(temp.left)
					if temp.right:
						q.append(temp.right)
			q.append(-1)


from collections import deque

class Solution:

	def nextRight(self, root, key):
		queue = [root]
		ans = Node(-1)
		while queue:
			n = len(queue)
			for i in range(n):
				curr = queue.pop(0)
				if curr.data == key and i != n - 1:
					return queue[0]
				if curr.left:
					queue.append(curr.left)
				if curr.right:
					queue.append(curr.right)
		return ans


from collections import deque

class Solution:

	def nextRight(self, root, key):
		queue = [root]
		while queue != []:
			t2 = []
			for i in range(len(queue)):
				curr = queue[0]
				if curr.left != None:
					queue.append(curr.left)
					t2.append(curr.left)
				if curr.right != None:
					queue.append(curr.right)
					t2.append(curr.right)
				queue.pop(0)
			for i in range(len(t2)):
				if t2[i].data == key:
					try:
						return t2[i + 1]
					except IndexError:
						return Node(-1)
		return Node(-1)


from collections import deque

class Solution:

	def nextRight(self, root, key):
		q = deque()
		q.append(root)
		q.append(None)
		while q:
			dq = q.popleft()
			if dq is None:
				q.append(None)
				continue
			if dq.data == key:
				r = q.popleft()
				if r is None:
					return Node(-1)
				else:
					return r
			if dq.left:
				q.append(dq.left)
			if dq.right:
				q.append(dq.right)


from collections import deque

class Solution:

	def __init__(self):
		self.dp = dict()
		self.ans = -1

	def tr(self, root, l, key):
		if root == None:
			return None
		elif self.dp.get(l) == key:
			self.ans = root.data
		self.dp[l] = root.data
		self.tr(root.left, l + 1, key)
		self.tr(root.right, l + 1, key)

	def nextRight(self, root, key):
		self.tr(root, 0, key)
		return Node(self.ans)


from collections import deque

class Solution:

	def nextRight(self, root, key):
		result = self.myFunc(root, key, [], 0)
		return result[-1] if result else Node(-1)

	def myFunc(self, root, key, path, level):
		if not root:
			return []
		if len(path) == level:
			path.append([])
		if root.data == key:
			return path[level].copy()
		path[level].append(root)
		level += 1
		result = []
		result += self.myFunc(root.right, key, path, level)
		result += self.myFunc(root.left, key, path, level)
		return result


from collections import deque

class Solution:

	def nextRight(self, root, key):
		if root == None or root.data == key:
			return Node(-1)
		que = deque()
		que.append(root)
		while que:
			n = len(que)
			for i in range(n):
				cur = que.popleft()
				if cur.data == key:
					if i < n - 1:
						return que.popleft()
					else:
						return Node(-1)
				if cur.left:
					que.append(cur.left)
				if cur.right:
					que.append(cur.right)
		return Node(-1)


from collections import deque

class Solution:

	def nextRight(self, root, key):
		if not root:
			return []
		curr = [root]
		while curr:
			next_level = []
			while curr:
				v = curr.pop(0)
				if key == v.data:
					if curr:
						return curr.pop(0)
					else:
						return Node(-1)
				if v.left:
					next_level.append(v.left)
				if v.right:
					next_level.append(v.right)
			curr = next_level
		return Node(-1)


from collections import deque

class Node:

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

class Solution:

	def nextRight(self, root, key):
		d = {}
		level = 0
		self.helper(root, level, d)
		a = 0
		b = 0
		l = []
		for i in d:
			for j in d[i]:
				if key == j.data:
					a = len(d[i])
					b = d[i].index(j)
					l = d[i]
		if a - 1 == b:
			n = Node(-1)
			return n
		else:
			return l[b + 1]

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


class Node:

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

class Solution:

	def nextRight(self, root, key):
		queue = []
		queue.append(root)
		while queue:
			l = len(queue)
			for i in range(l):
				p = queue.pop(0)
				if p.data == key:
					if i < l - 1:
						q = queue.pop(0)
						return q
					if i == l - 1:
						return Node(-1)
				if p.left != None:
					queue.append(p.left)
				if p.right != None:
					queue.append(p.right)
		return -1


from collections import deque

class Solution:

	def nextRight(self, root, key):

		def traversal(root, level):
			nonlocal f
			if root == None:
				return None
			if root.data == key:
				f = level
				return
			if root.left:
				traversal(root.left, level + 1)
			if root.right:
				traversal(root.right, level + 1)
		f = 0
		traversal(root, 0)

		def traversal2(root, level):
			if root == None:
				return None
			if level == 0:
				list1.append(root)
			else:
				traversal2(root.left, level - 1)
				traversal2(root.right, level - 1)
		list1 = []
		traversal2(root, f)
		length = len(list1)
		for i in range(length):
			if list1[i].data == key and i + 1 < length:
				return list1[i + 1]
		return Node(-1)


from collections import deque

class Solution:

	def nextRight(self, root, key):
		q = deque()
		q.append(root)
		found = False
		ans = Node(-1)
		while True:
			nc = len(q)
			if nc == 0:
				return ans
			if found == True:
				return ans
			while nc > 0:
				node = q.popleft()
				if node.data == key:
					found = True
					nc -= 1
					continue
				elif found == True:
					return node
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
				nc -= 1


from collections import deque

class Solution:

	def nextRight(self, root, key):

		def helper(root, mp, k):
			if root:
				if k in mp:
					mp[k].append(root.data)
				else:
					mp[k] = [root.data]
				helper(root.left, mp, k + 1)
				helper(root.right, mp, k + 1)
			return mp
		mp = {}
		helper(root, mp, 0)
		for k in mp:
			for i in range(len(mp[k])):
				if mp[k][i] == key:
					try:
						return Node(mp[k][i + 1])
					except:
						return Node(-1)
		return Node(-1)


from collections import deque

class Solution:

	def nextRight(self, root, key):

		def helper(root, key):
			x = []
			t = []
			q = []
			count = 0
			if not root:
				return x
			q.append(root)
			while q and count == 0:
				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)
					if a.data == key:
						count += 1
				if count == 1:
					x = t
			return x
		a = helper(root, key)
		ans = Node
		ans.data = -1
		if not a:
			return ans
		for i in range(len(a) - 1):
			if a[i] == key:
				ans.data = a[i + 1]
				return ans
		return ans


from collections import deque

class Solution:

	def nextRight(self, root, key):
		queue = [root]
		while queue:
			temp = queue.copy()
			if temp[-1].data == key:
				return Node(-1)
			for i in range(len(temp)):
				if temp[i].data == key:
					return temp[i + 1]
			queue.clear()
			for e in temp:
				if e.left:
					queue.append(e.left)
				if e.right:
					queue.append(e.right)
		return -1


from collections import deque

class Solution:

	def nextRight(self, root, key):
		node = root
		q = [node]
		while q:
			c = len(q)
			temp = []
			for i in range(c):
				nd = q.pop(0)
				if nd.data == key:
					if q:
						return q[0]
					else:
						return Node(-1)
				else:
					if nd.left:
						temp.append(nd.left)
					if nd.right:
						temp.append(nd.right)
			while temp:
				q.append(temp.pop(0))
		return Node(-1)


class Node:

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

class Solution:

	def nextRight(self, root, key):
		if root is None:
			return None
		else:
			d = {}
			count = 0
			target_level = 0
			import collections
			q = collections.deque()
			q.append(root)
			while q:
				level = []
				for i in range(len(q)):
					node = q.popleft()
					if node:
						level.append(node.data)
					if node.data == key:
						target_level = count
					if node.left:
						q.append(node.left)
					if node.right:
						q.append(node.right)
				d[count] = level
				count += 1
			for keys in list(d.keys()):
				if keys == target_level:
					index = d[keys].index(key)
					if index + 1 < len(d[keys]):
						val = d[keys][index + 1]
						return Node(val)
					else:
						return Node(-1)
from collections import defaultdict
from collections import deque
from sys import stdin, stdout

class Node:

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


from collections import deque

class Solution:

	def nextRight(self, root, key):
		l = []
		q = []
		q.append(root)
		while q:
			t = len(q)
			temp = []
			for i in range(t):
				s = q.pop(0)
				if s.left:
					q.append(s.left)
				if s.right:
					q.append(s.right)
				temp.append(s.data)
			l.append(temp)
		for i in range(len(l)):
			if key in l[i]:
				a = l[i].index(key)
				if a == 0 and i == 0:
					return Node(-1)
				elif a == len(l[i]) - 1:
					return Node(-1)
				else:
					return Node(l[i][a + 1])


from collections import deque

class Solution:

	def nextRight(self, root, key):
		q = [root]
		while q:
			arr = q[0:]
			q = []
			for i in range(len(arr)):
				t = arr.pop(0)
				if t.data == key:
					if not arr:
						return Node(-1)
					return arr[0]
				if t.left:
					q.append(t.left)
				if t.right:
					q.append(t.right)


from collections import deque

class Solution:

	def nextRight(self, root, key):
		q = deque()
		q.append(root)
		prev = -1
		while q:
			ll = len(q)
			prev = -1
			for _ in range(ll):
				node = q.popleft()
				if prev == -1:
					pass
				elif prev.data == key:
					return node
				prev = node
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
		return Node(-1)


from collections import deque

class Solution:

	def nextRight(self, root, key):
		if root is None:
			return Node(-1)
		q = [root]
		while q:
			temp = []
			while q:
				node = q.pop(0)
				if node.data == key:
					if q:
						return q[0]
					else:
						return Node(-1)
				if node.left:
					temp.append(node.left)
				if node.right:
					temp.append(node.right)
			q = temp
		return Node(-1)


from collections import defaultdict

class Solution:

	def nextRight(self, root, key):
		arr = defaultdict(list)

		def solve(root, level):
			if not root:
				return
			arr[level].append(root.data)
			solve(root.left, level + 1)
			solve(root.right, level + 1)
		solve(root, 0)
		for (k, value) in arr.items():
			for val in value:
				if val == key and value.index(val) < len(value) - 1:
					return Node(value[value.index(val) + 1])
					break
		return Node(-1)


from collections import deque

class Solution:

	def nextRight(self, root, key):
		q = deque([root])
		while q:
			t = len(q)
			for i in range(t):
				node = q.popleft()
				if node:
					if node.data == key and i < t - 1:
						return q[0]
					if node.left:
						q.append(node.left)
					if node.right:
						q.append(node.right)
		return Node(-1)


from collections import deque

class Solution:

	def nextRight(self, root, key):
		lis = list()
		lis.append([root, 0])
		level = 0
		di = dict()
		ans = -1
		while len(lis):
			(cur_node, level) = lis.pop(0)
			if cur_node.data == key:
				ans = level
			if level in di:
				di[level].append(cur_node)
			else:
				di[level] = list()
				di[level].append(cur_node)
			if cur_node.left:
				lis.append([cur_node.left, level + 1])
			if cur_node.right:
				lis.append([cur_node.right, level + 1])
		n = len(di[ans])
		for i in range(n):
			if i == n - 1 and key == di[ans][i].data:
				return Node(-1)
			elif key == di[ans][i].data:
				return di[ans][i + 1]


import collections
from collections import deque

class Solution:

	def nextRight(self, root, key):
		if not root:
			return -1
		q = collections.deque()
		q.append(root)
		res = []
		while q:
			qLen = len(q)
			temp = []
			for i in range(qLen):
				node = q.popleft()
				temp.append(node)
				if node.left:
					q.append(node.left)
				if node.right:
					q.append(node.right)
			res.append(temp)
		for i in range(len(res)):
			for j in range(len(res[i])):
				if res[i][j].data == key:
					if j + 1 < len(res[i]):
						return res[i][j + 1]
		temp = Node(-1)
		return temp


from collections import deque

class Solution:

	def nextRight(self, root, key):
		queue = [root]
		while 1:
			nodes = len(queue)
			if nodes == 0:
				return Node(-1)
			for i in range(nodes):
				if queue[i].data == key and i != len(queue) - 1:
					return queue[i + 1]
				elif queue[i].data == key and i == len(queue) - 1:
					return Node(-1)
			while nodes > 0:
				node = queue.pop(0)
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
				nodes -= 1
		return Node(-1)


from collections import deque

class Solution:

	def nextRight(self, root, key):
		q = list()
		q.append(root)
		q_levels = list()
		level = 0
		q_levels.append(level)
		while q:
			n = len(q)
			for i in range(n):
				node = q.pop(0)
				level = q_levels.pop(0)
				if node.data == key:
					if q and level == q_levels[0]:
						return q.pop(0)
				if node.left:
					q.append(node.left)
					q_levels.append(level + 1)
				if node.right:
					q.append(node.right)
					q_levels.append(level + 1)
		return Node(-1)
from collections import defaultdict
from collections import deque
from sys import stdin, stdout

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()


import collections
from collections import deque

class Solution:

	def nextRight(self, root, key):
		q = collections.deque()
		q.append(root)
		while q:
			qLen = len(q)
			for i in range(qLen):
				cur = q.popleft()
				if not cur:
					continue
				if cur.data == key:
					return q[0] if i < qLen - 1 else Node(-1)
				if cur.left:
					q.append(cur.left)
				if cur.right:
					q.append(cur.right)
		return Node(-1)


from collections import deque

class Solution:

	def nextRight(self, root, key):
		q = [(root, 0)]
		while q:
			(x, l) = q.pop(0)
			if x.data == key:
				if q and q[0][1] == l:
					return q[0][0]
				return Node(-1)
			if x.left:
				q.append((x.left, l + 1))
			if x.right:
				q.append((x.right, l + 1))


from collections import deque

class Solution:

	def nextRight(self, root, key):
		dic = {}

		def levelOrder(node, level):
			if not node:
				return
			else:
				if node.data == key:
					dic[0] = level
				if level in dic:
					dic[level].append(node)
				else:
					dic[level] = [node]
				levelOrder(node.left, level + 1)
				levelOrder(node.right, level + 1)
		levelOrder(root, 1)
		givenLevel = dic[0]
		for i in range(len(dic[givenLevel])):
			if dic[givenLevel][i].data == key:
				if i == len(dic[givenLevel]) - 1:
					node = Node(-1)
					return node
				else:
					return dic[givenLevel][i + 1]
		return root


from collections import deque

class Solution:

	def nextRight(self, root, key):
		errorNode = Node(-1)
		inspectList = [root]
		while len(inspectList) > 0:
			tmp = []
			for (i, target) in enumerate(inspectList):
				if target.data == key:
					if i == len(inspectList) - 1:
						return errorNode
					else:
						return inspectList[i + 1]
				else:
					if target.left != None:
						tmp.append(target.left)
					if target.right != None:
						tmp.append(target.right)
			inspectList = tmp
		return errorNode


from collections import deque

class Solution:

	def nextRight(self, root, key):
		ret = Node(-1)
		if root == None:
			return ret
		q = deque()
		q.append(root)
		while len(q):
			l = len(q)
			for i in range(l):
				node = q.popleft()
				if node.data == key:
					if len(q) == 0:
						return ret
					if i + 1 < l:
						return q.popleft()
					return ret
				if node.left is not None:
					q.append(node.left)
				if node.right is not None:
					q.append(node.right)
		return ret


def printing(q):
	res = []
	for ele in q:
		if ele is None:
			res.append(None)
		else:
			res.append(ele.data)
	print(res)
from collections import deque

class Solution:

	def nextRight(self, root, key):
		ret = Node(-1)
		if root == None:
			return ret
		q = deque()
		q.append(root)
		while len(q):
			l = len(q)
			for i in range(l):
				node = q.popleft()
				if node == None:
					continue
				if node.data == key:
					if len(q) == 0:
						return ret
					while i < l - 1:
						next_element = q.popleft()
						if next_element != None:
							return next_element
						i += 1
					return ret
				q.append(node.left)
				q.append(node.right)
		return ret


from collections import deque

class Solution:

	def find(self, lt, k):
		if lt[-1].data == k:
			n = Node(-1)
			return n
		for i in range(len(lt)):
			if lt[i].data == k and i + 1 < len(lt):
				return lt[i + 1]

	def level(self, lt):
		lt1 = []
		for i in lt:
			if i.left != None:
				lt1.append(i.left)
			if i.right != None:
				lt1.append(i.right)
		return lt1

	def nextRight(self, root, key):
		lt = [root]
		while self.find(lt, key) == None:
			lt = self.level(lt)
		return self.find(lt, key)


from collections import deque

class Solution:

	def nextRight(self, root, key):
		if not root or root.data == key:
			return Node(-1)
		res = []
		q = [root]
		idx = -1
		while len(q) > 0:
			children = []
			nq = []
			while q:
				element = q.pop(0)
				if element.data == key:
					if len(q) > 0:
						return q[0]
					else:
						return Node(-1)
				if element.left:
					nq.append(element.left)
				if element.right:
					nq.append(element.right)
			q.extend(nq)
			res.append(children)
		return Node(-1)


from collections import deque

class Solution:

	def nextRight(self, root, key):
		nodeQueue = []
		nodeQueue.append({'node': root, 'level': 0})
		while len(nodeQueue) > 0:
			current = nodeQueue.pop(0)
			if current['node'].data == key:
				if len(nodeQueue) == 0:
					return Node(-1)
				if nodeQueue[0]['level'] != current['level']:
					return Node(-1)
				return nodeQueue[0]['node']
			currentLevel = current['level']
			if current['node'].left:
				nodeQueue.append({'node': current['node'].left, 'level': currentLevel + 1})
			if current['node'].right:
				nodeQueue.append({'node': current['node'].right, 'level': currentLevel + 1})


from collections import deque

class Solution:

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

	def findNext(self, root, key, level):
		if root is None:
			return
		if level not in self.d:
			self.d[level] = list()
		self.d[level].append(root)
		self.findNext(root.left, key, level + 1)
		self.findNext(root.right, key, level + 1)

	def nextRight(self, root, key):
		self.findNext(root, key, 0)
		for i in self.d:
			l = len(self.d[i])
			for j in range(l):
				if self.d[i][j].data == key:
					if j == l - 1:
						return Node(-1)
					else:
						return self.d[i][j + 1]


from collections import deque

class Solution:

	def __init__(self):
		self.levels = {}
		self.keyLevel = None

	def nextRight(self, root, key):
		self.traverse(root, 0, key)
		return self.findRight(key)

	def traverse(self, node, level, key):
		if node == None:
			return
		if node.data == key:
			self.keyLevel = level
		if level not in self.levels:
			self.levels[level] = []
		self.levels[level].append(node.data)
		self.traverse(node.left, level + 1, key)
		self.traverse(node.right, level + 1, key)

	def findRight(self, key):
		levelNodes = self.levels[self.keyLevel]
		rightNodeIndex = levelNodes.index(key) + 1
		if rightNodeIndex > len(levelNodes) - 1:
			return Node(-1)
		return Node(levelNodes[rightNodeIndex])


from collections import deque

class Solution:

	def nextRight(self, root, key):
		if not root:
			return root
		q = deque([])
		q.append(root)
		found = False
		node = Node(-1)
		while q:
			l = len(q)
			curr = []
			for i in range(l):
				t = q.popleft()
				if found:
					return t
				if t.data == key:
					found = True
				curr.append(t)
				if t.left:
					q.append(t.left)
				if t.right:
					q.append(t.right)
			found = False
		return node


from collections import deque

class Solution:

	def nextRight(self, root, key):
		queue1 = deque()
		queue2 = deque()
		queue1.append(root)
		while queue1:
			pr = queue1.popleft()
			if pr.data == key:
				if queue1:
					return queue1.popleft()
				else:
					return Node(-1)
			if pr.left:
				queue2.append(pr.left)
			if pr.right:
				queue2.append(pr.right)
			if not queue1:
				queue1 = queue2
				queue2 = deque()


class Solution:

	def nextRight(self, root, key):
		if root.data == key:
			return Node(-1)
		queue = [root]
		data_list = [[root]]
		while queue:
			found = False
			node_queue = []
			for node in queue:
				if node.left:
					if node.left.data == key:
						found = True
					node_queue.append(node.left)
				if node.right:
					if node.right.data == key:
						found = True
					node_queue.append(node.right)
			if found:
				for i in range(len(node_queue)):
					if node_queue[i].data == key:
						if i + 1 < len(node_queue):
							return node_queue[i + 1]
						else:
							return Node(-1)
			data_list.append(node_queue)
			queue = node_queue
		return Node(-1)


from collections import deque

class Solution:

	def levelBFS(self, root, key):
		queue = [root]
		data_list = [[root]]
		if queue[0].data == key:
			return Node(-1)
		while queue:
			found = False
			node_queue = []
			for node in queue:
				if node.left:
					if node.left.data == key:
						found = True
					node_queue.append(node.left)
				if node.right:
					if node.right.data == key:
						found = True
					node_queue.append(node.right)
			if found:
				for i in range(len(node_queue)):
					if node_queue[i].data == key:
						if i + 1 < len(node_queue):
							return node_queue[i + 1]
			data_list.append(node_queue)
			queue = node_queue
		return Node(-1)

	def nextRight(self, root, key):
		return self.levelBFS(root, key)


from collections import deque

class Solution:

	def levelBFS(self, root):
		queue = [root]
		data_list = [[root]]
		while queue:
			node_queue = []
			for node in queue:
				if node.left:
					node_queue.append(node.left)
				if node.right:
					node_queue.append(node.right)
			data_list.append(node_queue)
			queue = node_queue
		return data_list

	def nextRight(self, root, key):
		if root.data == key:
			return Node(-1)
		l = self.levelBFS(root)
		for i in l:
			for j in range(len(i)):
				if i[j].data == key:
					if j + 1 < len(i):
						return i[j + 1]
		return Node(-1)


from collections import deque

class Solution:

	def nextRight(self, root, key):
		if root == None:
			return 0
		qn = deque()
		ql = deque()
		level = 0
		qn.append(root)
		ql.append(level)
		while len(qn) > 0:
			node = qn.popleft()
			level = ql.popleft()
			if node.data == key:
				if len(ql) == 0 or ql[0] != level:
					ret = Node(-1)
					return ret
				return qn[0]
			if node.left != None:
				qn.append(node.left)
				ql.append(level + 1)
			if node.right != None:
				qn.append(node.right)
				ql.append(level + 1)
		ret = Node(-1)
		return ret


from collections import deque

class Solution:

	def nextRight(self, root, key):
		if root == None:
			return Node(-1)
		q = []
		q.append(root)
		res = [root.data]
		while len(q) > 0:
			for i in range(len(res)):
				if res[i] == key:
					if i + 1 < len(res):
						return Node(res[i + 1])
					else:
						return Node(-1)
			res = []
			for i0 in range(len(q)):
				temp = q.pop(0)
				if temp.left:
					q.append(temp.left)
					res.append(temp.left.data)
				if temp.right:
					q.append(temp.right)
					res.append(temp.right.data)


from collections import deque

class Solution:

	def nextRight(self, root, key):
		if root is None:
			return Node(-1)
		queue = []
		queue.append(root)
		while queue:
			len_q = len(queue)
			for i in range(len_q):
				node = queue.pop(0)
				if node.data == key:
					if i + 1 < len_q:
						right_node = queue.pop(0)
						return right_node
					else:
						return Node(-1)
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
		return Node(-1)


from collections import deque
from collections import deque

class Solution:

	def nextRight(self, root, key):
		queue = deque()
		queue.append(root)
		length = len(queue)
		flag = False
		while queue:
			current = queue.popleft()
			length -= 1
			if current.left is not None:
				queue.append(current.left)
				if current.left.data == key:
					flag = True
				elif flag == True:
					return current.left
			if current.right is not None:
				queue.append(current.right)
				if current.right.data == key:
					flag = True
				elif flag == True:
					return current.right
			if length == 0:
				if flag == True:
					return Node(-1)
				length = len(queue)
		return Node(-1)


from collections import deque

class Solution:

	def findKeyParent(self, node, key):
		if node.left != None:
			if node.left.data == key:
				return node
		if node.right != None:
			if node.right.data == key:
				return node
		if not node.left == None:
			left = self.findKeyParent(node.left, key)
			if not left == None:
				return left
		if not node.right == None:
			left = self.findKeyParent(node.right, key)
			if not left == None:
				return left
		return None

	def getTree(self, node, tree=None, depth=0):
		if tree == None:
			tree = [[node.data]]
		else:
			tree[depth].append(node.data)
		if len(tree) == depth + 1:
			tree.append([])
		if node.left == None:
			tree[depth + 1].append('N')
		else:
			tree = self.getTree(node.left, tree, depth + 1)
		if node.right == None:
			tree[depth + 1].append('N')
		else:
			tree = self.getTree(node.right, tree, depth + 1)
		return tree

	def nextRight(self, root, key):
		tree = self.getTree(root)
		keyFound = False
		for depth in tree[1:]:
			if keyFound == True:
				return Node(-1)
			for element in depth:
				if keyFound == True:
					if element != 'N':
						return Node(element)
				elif element == key:
					keyFound = True
		return Node(-1)


from collections import deque

class Solution:

	def nextRight(self, root, key):
		if root == None or root.data == key:
			return Node(-1)
		nodes = [root]
		node = root
		found_key = False
		found_right = False
		while nodes != []:
			new_nodes = []
			for node in nodes:
				if node.left != None:
					new_nodes.append(node.left)
					if node.left.data == key:
						found_key = True
					elif found_key:
						found_right = True
						return node.left
				if node.right != None:
					new_nodes.append(node.right)
					if node.right.data == key:
						found_key = True
					elif found_key:
						found_right = True
						return node.right
			if found_key:
				break
			(nodes, new_nodes) = (new_nodes, [])
		return Node(-1)