Given a binary search tree and a number N, find the greatest number in the binary search tree that is less than or equal to N. 
Example 1 :
Input : N = 24
Output : 21
Explanation : The greatest element in the tree which 
              is less than or equal to 24, is 21. 
              (Searching will be like 5->12->21)
 
Example 2 :
Input : N = 4
Output : 3
Explanation : The greatest element in the tree which 
              is less than or equal to 4, is 3. 
              (Searching will be like 5->2->3)
Your task : 
You don't need to read input or print anything. Your task is to complete the function findMaxForN() which takes the root of the BST, and the integer N as input paramters and returns the greatest element less than or equal to N in the given BST.
 
Expected Time Complexity: O(Height of the BST)
Expected Auxiliary Space: O(Height of the BST).
Constraints:
1<=N<=10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Range queries

Starter code: #User function Template for python3





'''

class Node:

    """ Class Node """

    def __init__(self, value):

        self.left = None

        self.key = value

        self.right = None

'''

def findMaxForN(root,N):

    #Print the value of the element if it exists otherwise print -1.

    

    #code here

Solutions:
def inorder(node, a):
	if node is None:
		return
	inorder(node.left, a)
	a.append(node.key)
	inorder(node.right, a)
	return a

def findMaxForN(root, N):
	li = []
	x = inorder(root, [])
	if N in x:
		return N
	else:
		for i in x:
			if i <= N:
				li.append(i)
	if len(li) != 0:
		return max(li)
	else:
		return -1


def fun(root, l):
	if root == None:
		return
	fun(root.left, l)
	l.append(root.key)
	fun(root.right, l)

def findMaxForN(root, n):
	l = []
	fun(root, l)
	t = -1
	for i in l:
		if i <= n:
			t = i
		else:
			break
	return t


def solve(root, N, ans):
	if root == None:
		return
	if root.key > N:
		solve(root.left, N, ans)
	if root.key < N:
		ans[0] = max(ans[0], root.key)
		solve(root.right, N, ans)
	if root.key == N:
		ans[0] = N
		return

def findMaxForN(root, N):
	ans = [-100]
	solve(root, N, ans)
	return ans[0]


def findMaxForN(root, N):
	a = []

	def ino(root, a):
		if root:
			ino(root.left, a)
			a.append(root.key)
			ino(root.right, a)
		return a
	ino(root, a)
	a.sort()
	x = []
	for i in a:
		if i <= N:
			x.append(i)
	return max(x)


import bisect

def solve(root, ans):
	if root is None:
		return
	else:
		solve(root.left, ans)
		ans.append(root.key)
		solve(root.right, ans)

def findMaxForN(root, N):
	ans = []
	solve(root, ans)
	i = bisect.bisect_right(ans, N)
	if i:
		return ans[i - 1]


def solve(root, N, min1):
	if root is None:
		return
	solve(root.left, N, min1)
	if root.key <= N:
		min1.append(max(root.key, min1[-1]))
	solve(root.right, N, min1)

def findMaxForN(root, N):
	min1 = [-1]
	solve(root, N, min1)
	return min1[-1]


def findMaxForN(root, N):
	if root is None:
		return -1
	current_node = root
	best_so_far = None
	while current_node is not None:
		if current_node.key <= N:
			best_so_far = current_node
			current_node = current_node.right
		else:
			current_node = current_node.left
	if best_so_far is not None:
		return best_so_far.key
	else:
		return -1


class Queue:

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

	def __str__(self):
		values = []
		values = [str(x) for x in self.l]
		return ' '.join(values)

	def isEmpty(self):
		if self.l == []:
			return True
		else:
			return False

	def Enqueue(self, val):
		self.l.append(val)
		return 'Insertion is completed'

	def Dequeue(self):
		if self.isEmpty():
			return 'Queue is empty'
		else:
			return self.l.pop(0)

def leveltrav(Node, N):
	l = []
	if not Node:
		return
	else:
		customQueue = Queue()
		customQueue.Enqueue(Node)
		while not customQueue.isEmpty():
			root = customQueue.Dequeue()
			if root.key <= N:
				l.append(root.key)
			if root.left is not None:
				customQueue.Enqueue(root.left)
			if root.right is not None:
				customQueue.Enqueue(root.right)
		return l

def findMaxForN(root, N):
	l = []
	if not root:
		return -1
	a = leveltrav(root, N)
	if a:
		a.sort()
		return a[-1]
	return -1


def findMaxForN(root, N):
	b = []
	bst(root, b)
	b.sort()
	for i in range(len(b) - 1):
		if b[i] == N:
			return N
		if b[i + 1] > N:
			return b[i]
	return b[-1]

def bst(root, b):
	if root.left:
		bst(root.left, b)
	if root:
		b.append(root.key)
	if root.right:
		bst(root.right, b)


def findMaxForN(root, N):
	key_node = 0
	while root:
		if N >= root.key:
			key_node = root.key
			root = root.right
		else:
			root = root.left
	return key_node


def findMaxForN(root, N):
	if root is None:
		return -1
	if root.key > N:
		return findMaxForN(root.left, N)
	if root.key == N:
		return N
	return max(root.key, findMaxForN(root.right, N))


def findMaxForN(root, N):
	pre = [-1]
	flag = 0
	flag = traverse(root, N, flag, pre)
	if flag == 0:
		return pre[0]
	return N

def traverse(root, N, flag, pre):
	if root is None:
		return 0
	if root.key == N:
		return 1
	if root.key < N:
		pre[0] = root.key
	if root.key > N:
		flag = traverse(root.left, N, flag, pre)
		if flag == 1:
			return 1
	if root.key < N:
		flag = traverse(root.right, N, flag, pre)
		if flag == 1:
			return 1
	return 0


def findMaxForN(root, N):
	g = []

	def ans(root):
		if root != None:
			ans(root.left)
			g.append(root.key)
			ans(root.right)
		else:
			return
	ans(root)
	for i in range(0, len(g)):
		if g[i] > N:
			return g[i - 1]
		elif g[i] == N:
			return g[i]


import math

def findMaxForN(root, N):
	ans = -math.inf
	cur = root
	while cur:
		if cur.key == N:
			return N
		elif cur.key < N:
			ans = max(ans, cur.key)
			cur = cur.right
		else:
			cur = cur.left
	return ans


def findMaxForN(root, N):
	if root.key == N:
		return root.key
	else:
		nodes_list = []
		if root.key > N:
			_in_order_traversal(root.left, nodes_list)
			nodes_list.append(root.key)
		else:
			_in_order_traversal(root.right, nodes_list)
			nodes_list.insert(0, root.key)
		_index = _bs(nodes_list, N, 0, len(nodes_list) - 1)
		return nodes_list[_index]

def _bs(nodes_list, N, low, high):
	while low <= high:
		_middle = (low + high) // 2
		if nodes_list[_middle] == N:
			return _middle
		elif nodes_list[_middle] < N:
			low = _middle + 1
		elif nodes_list[_middle] > N:
			high = _middle - 1
	return high

def _in_order_traversal(root, nodes_list):
	if root:
		_in_order_traversal(root.left, nodes_list)
		nodes_list.append(root.key)
		_in_order_traversal(root.right, nodes_list)


def findMaxForN(root, N):
	M = -1
	while 1:
		if root == None:
			break
		elif root.key == N:
			M = N
			break
		elif root.key < N:
			M = root.key
			root = root.right
		elif root.key > N:
			root = root.left
	return M


def findMaxForN(root, N):
	prev = -1
	while root:
		if root.key == N:
			prev = root.key
			break
		elif N < root.key:
			root = root.left
		else:
			prev = root.key
			root = root.right
	return prev


def LV(root, l):
	if root == None:
		return l
	l.append(root.key)
	LV(root.right, l)
	LV(root.left, l)
	return l

def findMaxForN(root, N):
	l = []
	x = LV(root, l)
	m = 10000000000000000
	for i in x:
		if i <= N and abs(N - i) < m:
			m = min(abs(N - i), m)
			c = i
	return c


def findMaxForN(root, N):
	res = None
	while root != None:
		if root.key == N:
			return root.key
		elif root.key > N:
			root = root.left
		else:
			res = root
			root = root.right
	if res == None:
		return -1
	return res.key


def findMaxForN(root, N):
	curr = -1
	while root:
		if root.key == N:
			return root.key
		elif root.key > N:
			root = root.left
		else:
			curr = root.key
			root = root.right
	return curr


def inorder(root):
	res = []
	if root is None:
		return res
	q = []
	cur = root
	while True:
		if cur is not None:
			q.append(cur)
			cur = cur.left
		elif q:
			cur = q.pop()
			res.append(cur.key)
			cur = cur.right
		else:
			break
	return res

def findMaxForN(root, N):
	ino = inorder(root)
	j = -1
	for i in range(len(ino)):
		if ino[i] == N:
			j = i
			break
		elif ino[i] > N:
			j = i
			break
	if ino[j] == N:
		return ino[j]
	else:
		return ino[j - 1]


def findMaxForN(root, N):

	def traversal(root):
		nonlocal count, f, temp
		if root == None:
			return None
		if root.left:
			traversal(root.left)
		if root.key == N:
			f = root.key
			return
		elif root.key > N and count == 0 and (f == None):
			f = temp
			count += 1
			return
		temp = root.key
		if root.right:
			traversal(root.right)
	count = 0
	f = None
	temp = None
	traversal(root)
	return f


def getMax(root, data, ans):
	if root == None:
		return ans
	elif root.key <= data:
		if ans[0] != -1 and root.key > ans[0]:
			ans[0] = root.key
		else:
			ans[0] = root.key
		getMax(root.right, data, ans)
	else:
		getMax(root.left, data, ans)

def findMaxForN(root, N):
	ans = []
	ans.append(-1)
	getMax(root, N, ans)
	return ans[0]


def findMaxForN(root, N):

	def helper(root):
		x = []
		if not root:
			return x
		x += helper(root.left)
		x.append(root.key)
		x += helper(root.right)
		return x
	a = helper(root)
	ans = -1
	for i in a:
		if i <= N:
			ans = i
		else:
			break
	return ans


def findMaxForN(root, N):
	l = [0]

	def ino(r):
		if r:
			ino(r.left)
			if r.key <= N:
				l[0] = r.key
			ino(r.right)
	ino(root)
	return l[0]


def findMaxForN(root, N):

	def solve(root, arr):
		if not root:
			return
		solve(root.left, arr)
		arr.append(root.key)
		solve(root.right, arr)
	arr = []
	solve(root, arr)
	for i in range(len(arr)):
		if arr[i] == N:
			return arr[i]
		if arr[i] > N:
			return arr[i - 1]


def findMaxForN(root, N):
	if root.key == N:
		return root.key
	prev = root
	if root.key > N:
		cur = root.left
		prev = None
	if root.key < N:
		cur = root.right
	while cur:
		if cur.key == N:
			return cur.key
		if cur.key > N:
			cur = cur.left
		else:
			prev = cur
			cur = cur.right
	return prev.key


def findMaxForN(root, N):
	arr = [-1]
	return ar(root, N, arr)

def ar(root, N, arr):
	if root == None:
		return 0
	if root.key <= N:
		arr.append(root.key)
	ar(root.left, N, arr)
	ar(root.right, N, arr)
	arr.sort()
	return arr[-1]


def findMaxForN(root, N):
	l = []
	if root == None:
		return 0
	else:
		while root:
			if root == None:
				return []
			elif root.key == N:
				return N
			elif root.key < N:
				l.append(root.key)
				root = root.right
			else:
				root = root.left
		return max(l)


def findMaxForN(root, N):
	mv = -100000000
	while root:
		if root.key > N:
			root = root.left
		elif root.key < N:
			mv = max(mv, root.key)
			root = root.right
		else:
			return N
	return mv


def io(self, root, arr):
	if root == None:
		return
	self.io(root.left, arr)
	arr.append(root.data)
	self.io(root.right, arr)
	return arr

def findMaxForN(root, N):
	mv = -100000000
	while root:
		if root.key > N:
			root = root.left
		elif root.key < N:
			mv = max(mv, root.key)
			root = root.right
		else:
			return N
	return mv


def findMaxForN(root, N):
	curr = root
	ans = None
	while curr:
		if curr.key <= N:
			ans = curr.key
			curr = curr.right
		else:
			curr = curr.left
	return ans


def findMaxForN(root, N):
	nodes = []
	inorder(root, nodes)
	for i in range(len(nodes) - 1, -1, -1):
		if nodes[i] <= N:
			return nodes[i]
	return -1

def inorder(root, nodes):
	if root is None:
		return
	inorder(root.left, nodes)
	nodes.append(root.key)
	inorder(root.right, nodes)


def solve(root, l):
	if root == None:
		return
	solve(root.left, l)
	l.append(root.key)
	solve(root.right, l)

def findMaxForN(root, N):
	l = []
	solve(root, l)
	for i in range(len(l) - 1, -1, -1):
		if l[i] <= N:
			return l[i]
	return -1


def findMaxForN(root, N):
	if root is None:
		return None
	if root.key == N:
		if root.left is not None:
			return root.key
	if N < root.key:
		node = findMaxForN(root.left, N)
	else:
		node = findMaxForN(root.right, N)
	if node is None:
		if root.key <= N:
			node = root.key
	return node

def findGreatest(root):
	if root is None:
		return
	else:
		temp = root
		while temp.right is not None:
			temp = temp.right
		return temp


psord = []

def psorder(root, N, psord):
	if root is None:
		return None
	if len(psord) == 0:
		if root.right:
			psorder(root.right, N, psord)
	if len(psord) == 0:
		if root.key <= N:
			psord.append(root.key)
	if len(psord) == 0:
		if root.left:
			psorder(root.left, N, psord)
	return psord

def findMaxForN(root, N):
	psord = []
	psord = psorder(root, N, psord)
	if len(psord) > 0:
		rslt = psord[0]
	else:
		rslt = None
	return rslt


def recur(root, n, ans):
	if not root:
		return None
	if root.key <= n:
		ans[0] = root.key
		recur(root.right, n, ans)
	else:
		recur(root.left, n, ans)

def findMaxForN(root, N):
	ans = [-1]
	recur(root, N, ans)
	return ans[0]
from collections import deque

class Node:

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

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


def findMaxForN(r, N):
	if r is None:
		return -1
	elif r.key == N:
		return N
	elif r.key < N:
		return max(r.key, findMaxForN(r.right, N))
	else:
		return findMaxForN(r.left, N)


def findMaxForN(root, N):
	stack = []
	current = root
	an = -1
	while 1:
		if current is not None:
			stack.append(current)
			current = current.left
		elif stack:
			p = stack.pop()
			if p.key <= N:
				an = p.key
			else:
				break
			current = p.right
		else:
			break
	return an


def findMaxForN(root, N):
	ans = -1
	while root:
		if root.key > N:
			root = root.left
		else:
			ans = max(ans, root.key)
			root = root.right
	return ans


def findMaxForN(root, N):
	if root is None:
		return -1
	if root.key == N:
		return root.key
	elif root.key < N:
		k = findMaxForN(root.right, N)
		if k == -1:
			return root.key
		else:
			return k
	elif root.key > N:
		return findMaxForN(root.left, N)


def findMaxForN(root, N):

	def inorder(root):
		if root is None:
			return []
		l = []
		l = l + inorder(root.left)
		l.append(root.key)
		l = l + inorder(root.right)
		return l
	l = inorder(root)
	maxi = 0
	for i in l:
		if i <= N:
			maxi = max(maxi, i)
	return maxi


ans = 0

def findMaxForN(root, N):
	global ans
	if root == None:
		return None
	findMaxForN(root.left, N)
	if root.key <= N:
		if root.key == N:
			ans = root.key
			return ans
		ans = root.key
	findMaxForN(root.right, N)
	return ans


def solve(root, N, res):
	if root is None:
		return
	if root.key > N:
		solve(root.left, N, res)
	else:
		solve(root.right, N, res)
	if root.key <= N:
		res.append(root.key)
	return root

def findMaxForN(root, N):
	res = []
	solve(root, N, res)
	return res[0]


def findMaxForN(root, N):

	def myway(root, N):
		if root.key <= N:
			if root.right == None:
				return root.key
			elif root.right.key > N:
				check = myway(root.right, N)
				if check == -1:
					return root.key
				else:
					return check
			else:
				return myway(root.right, N)
		elif root.left == None:
			return -1
		else:
			return myway(root.left, N)
	return myway(root, N)


def solve(root, N):
	global MAX
	if root is None:
		return
	if root.right is not None:
		solve(root.right, N)
	if root.key <= N:
		MAX = max(MAX, root.key)
	if root.left is not None:
		solve(root.left, N)

def findMaxForN(root, N):
	global MAX
	MAX = -1
	solve(root, N)
	return MAX


def solve(root, N):
	global MAX
	if root is None:
		return
	if root.right is not None:
		solve(root.right, N)
	if root.key <= N:
		MAX = max(MAX, root.key)
	if root.left is not None:
		solve(root.left, N)

def findMaxForN(root, N):
	global MAX
	MAX = -100000000000.0
	solve(root, N)
	return MAX


def findMaxForN(root, N):
	res = []
	a = []

	def recurse(node):
		if node is None:
			return
		a.append(node.key)
		recurse(node.left)
		recurse(node.right)
	recurse(root)
	for i in range(len(a)):
		if a[i] <= N:
			res.append(a[i])
	res = sorted(res)
	return res[-1]


def recur(root, n, ans):
	if not root:
		return None
	if root.key <= n:
		ans[0] = max(ans[0], root.key)
		recur(root.right, n, ans)
	else:
		recur(root.left, n, ans)

def findMaxForN(root, N):
	ans = [-1]
	recur(root, N, ans)
	return ans[0]


def findMaxForN(root, N):
	global a
	a = []

	def sol(root):
		global a
		if root:
			sol(root.left)
			a.append(root.key)
			sol(root.right)
	sol(root)
	a = a[::-1]
	for i in a:
		if i <= N:
			return i


def findMaxForN(root, N):
	if root is None:
		return
	ans = root.key

	def helper(root):
		nonlocal N, ans
		if root:
			helper(root.left)
			if root.key <= N and abs(N - root.key) < abs(N - ans):
				ans = root.key
			helper(root.right)
	helper(root)
	return ans


INT_MIN = -4444444444
maxi = INT_MIN

def Inorder(root, N):
	global maxi
	if root == None:
		return
	Inorder(root.left, N)
	if root.key <= N:
		maxi = root.key
	Inorder(root.right, N)
	if maxi == INT_MIN:
		return -1
	else:
		return maxi

def findMaxForN(root, N):
	return Inorder(root, N)


def findMaxForN(root, N):
	return_number = None

	def recursion(root, N):
		if root == None:
			return -1
		if root.key > N:
			return recursion(root.left, N)
		if root.key <= N:
			return max(root.key, recursion(root.right, N))
	return recursion(root, N)


def traversal(node, N):
	val = -1
	if node.right:
		val = traversal(node.right, N)
	if val < 0:
		if node.key <= N:
			val = node.key
		elif node.left:
			val = traversal(node.left, N)
	return val

def findMaxForN(root, N):
	return traversal(root, N)


def inorder(root, l):
	if root is None:
		return None
	else:
		inorder(root.left, l)
		l.append(root.key)
		inorder(root.right, l)
	return l

def findMaxForN(root, N):
	if root.key == N:
		return root.key
	l = []
	l = inorder(root, l)
	l.sort()
	m = 0
	for i in l:
		if i == N:
			return N
		elif i < N:
			m = max(i, m)
	return m


def inorder(root, l):
	if root:
		inorder(root.left, l)
		l.append(root.key)
		inorder(root.right, l)
	return l

def findMaxForN(root, N):
	l = []
	inorder(root, l)
	ans = -1
	l.sort()
	pre = -1
	for i in l:
		if i <= N and i > ans:
			ans = i
	return ans


def findMaxForN(root, N):
	arr = []

	def inorder(root):
		if root == None:
			return None
		if root.left:
			inorder(root.left)
		arr.append(root.key)
		if root.right:
			inorder(root.right)
	inorder(root)
	mn = 100000000
	up = 0
	for i in range(len(arr)):
		if abs(N - arr[i]) < mn and arr[i] <= N:
			mn = abs(N - arr[i])
			up = arr[i]
	return up


def findMaxForN(root, N):
	min = root.key
	if root is None:
		return -1
	if N < root.key and root.left is None:
		return -1
	while root is not None:
		if root.key <= N:
			min = root.key
			root = root.right
		elif root.key > N:
			root = root.left
	return min


def findMaxForN(root, N):
	sol = None
	diff = 2 ** 32 - 1
	while root is not None:
		if root.key > N:
			root = root.left
		else:
			res = N - root.key
			if res < diff:
				sol = root.key
				diff = res
			root = root.right
	return sol


def findMaxForN(root, N):
	pre = root.key
	while root:
		if root.key <= N:
			pre = root.key
			root = root.right
		elif root.key > N:
			root = root.left
	return pre


def findMaxForN(root, n):
	if not root:
		return
	elif root.key == n:
		return root.key
	elif root.key > n:
		return findMaxForN(root.left, n)
	elif root.key < n:
		R = findMaxForN(root.right, n)
		return R if R else root.key


def helper(root, N, num_list):
	if root is None:
		return
	if root.key == N:
		num_list[0] = N
		return
	if N < root.key:
		return helper(root.left, N, num_list)
	elif N > root.key:
		num_list[0] = root.key
		return helper(root.right, N, num_list)

def findMaxForN(root, N):
	num_list = [-1]
	helper(root, N, num_list)
	return num_list[0]


def findMaxForN(root, N):
	maxx = [float('-inf')]

	def inorder(root, maxx):
		if not root:
			return None
		if root.left:
			inorder(root.left, maxx)
		if root.key > maxx[0] and root.key <= N:
			maxx[0] = root.key
		if root.right:
			inorder(root.right, maxx)
	inorder(root, maxx)
	return maxx[0]


import sys

def max_util(root, N, m):
	if root is None:
		return
	if root.key == N:
		m[0] = 0
		m[1] = root.key
		return m
	elif N > root.key and N - root.key < m[0]:
		m[0] = abs(root.key - N)
		m[1] = root.key
	max_util(root.left, N, m)
	max_util(root.right, N, m)

def findMaxForN(root, N):
	m = []
	m.append(sys.maxsize)
	m.append(-1)
	max_util(root, N, m)
	return m[1]