You are given a BST(Binary Search Tree) with n number of nodes and value x. your task is to find the greatest value node of the BST which is smaller than or equal to x.
Note: when x is smaller than the smallest node of BST then returns -1.
Example:
Input:
n = 7               2
                     \
                      81
                    /     \
                 42       87
                   \       \
                    66      90
                   /
                 45
x = 87
Output:
87
Explanation:
87 is present in tree so floor will be 87.
Example 2:
Input:
n = 4                     6
                           \
                            8
                          /   \
                        7       9
x = 11
Output:
9
Your Task:
You don't need to read input or print anything. Complete the function floor() which takes the integer n and BST and integer x returns the floor value.
Constraint:
1 <= n <= 10^{5}
Expected Time Complexity: O(n)
Expected Space Complexity: O(1)

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Range queries

Starter code: #User function Template for python3



class Solution:

    def floor(self, root, x):

        # Code here

Solutions:
class Solution:

	def floor(self, root, x):
		c = -1
		while root:
			if x > root.data:
				c = root.data
				root = root.right
			elif x < root.data:
				root = root.left
			else:
				return x
		return c


class Solution:

	def floor(self, root, x):
		flor = -1
		while root:
			if root.data == x:
				return x
			if root.data < x:
				flor = root.data
				root = root.right
			else:
				root = root.left
		return flor


class Solution:

	def floor(self, root, x):

		def findPreSuc(root, pre, suc, key):
			if root == None:
				return
			findPreSuc(root.left, pre, suc, key)
			if root.data <= key:
				pre[0] = root.data
			if root.data > key:
				if suc[0] == None or root.data < suc[0]:
					suc[0] = root.data
			findPreSuc(root.right, pre, suc, key)
		pre = [-1]
		suc = [-1]
		findPreSuc(root, pre, suc, x)
		return pre[0]


class Solution:

	def __init__(self):
		self.prev = -1

	def floor(self, root, x):
		if root is None:
			return self.prev
		if root.data == x:
			return root.data
		if root.data > x:
			return self.floor(root.left, x)
		if root.data < x:
			self.prev = root.data
			return self.floor(root.right, x)


class Solution:

	def floor(self, root, x):

		def inorder(root):
			nonlocal ans, x
			if not root:
				return
			inorder(root.left)
			if root.data <= x:
				if ans == -1:
					ans = root.data
				elif ans < root.data:
					ans = root.data
			inorder(root.right)
		ans = -1
		inorder(root)
		return ans


class Solution:

	def floor(self, root, x):
		s = [root]
		res = [root.data]
		while s:
			node = s.pop(0)
			if node.left:
				s.append(node.left)
				res.append(node.left.data)
			if node.right:
				s.append(node.right)
				res.append(node.right.data)
		res.sort()
		ans = []
		for i in res:
			if i <= x:
				ans.append(i)
		if len(ans) == 0:
			return -1
		return max(ans)


class Solution:

	def floor(self, root, x):
		curr = root
		prevmin = -1
		while curr is not None:
			if curr.data == x:
				return curr.data
			if curr.data < x:
				prevmin = curr.data
				curr = curr.right
			else:
				curr = curr.left
		return prevmin


class Solution:

	def floor(self, root, x):
		ans = -1
		curr = root
		while curr:
			while curr and curr.data < x:
				ans = curr.data
				curr = curr.right
			if curr and curr.data == x:
				return x
			if curr:
				curr = curr.left

		def recur(root, x):
			if root is None:
				return -1
			if root.data == x:
				return x
			if root.data > x:
				return recur(root.left, x)
			else:
				return max(root.data, recur(root.right, x))
		return recur(root, x)


class Solution:

	def floor(self, root, x):
		ans = -1
		curr = root
		while curr:
			while curr and curr.data < x:
				ans = curr.data
				curr = curr.right
			if curr and curr.data == x:
				return x
			if curr:
				curr = curr.left
		return ans


class Solution:

	def floor(self, root, x):
		if root is None:
			return -1
		if root.data == x:
			return x
		if root.data > x:
			return self.floor(root.left, x)
		val = self.floor(root.right, x)
		if val <= x and val != -1:
			return val
		else:
			return root.data


class Solution:

	def floor(self, root, x):
		if not root:
			return -1
		prev = None
		p = root
		while p:
			if p.data == x:
				return x
			elif p.data < x:
				prev = p
				p = p.right
			else:
				p = p.left
		return -1 if not prev else prev.data


class Solution:

	def floor(self, root, x):
		if not root:
			return -1
		s = []
		p = root
		while p:
			if p.data == x:
				return x
			elif p.data < x:
				s.append(p)
				p = p.right
			else:
				p = p.left
		return -1 if len(s) == 0 else s[-1].data


class Solution:

	def floor(self, root, x):
		a = None
		while root is not None:
			if root.data == x:
				return root.data
			elif root.data > x:
				root = root.left
			else:
				a = root
				root = root.right
		if a is None:
			return -1
		else:
			return a.data


class Solution:

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

	def floor(self, root, x):
		if root is None:
			return self.ans
		if x < root.data:
			return self.floor(root.left, x)
		elif x >= root.data:
			self.ans = root.data
			return self.floor(root.right, x)


class Solution:

	def floor(self, root, x):
		m = -1
		while root:
			if root.data <= x:
				m = max(m, root.data)
				root = root.right
			else:
				root = root.left
		return m


class Solution:

	def floor(self, root, x):
		li = self.inorder(root, [])
		if x in li:
			return x
		else:
			li.append(x)
			li.sort()
			x = li.index(x)
			if x == 0:
				return -1
			else:
				return li[x - 1]

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


class Solution:

	def find(self, root, tar, ans):
		if root == None:
			return ans
		if root.data == tar:
			ans = tar
			return ans
		if root.data < tar:
			ans = root.data
			return self.find(root.right, tar, ans)
		elif root.data > tar:
			return self.find(root.left, tar, ans)

	def floor(self, root, x):
		ans = -1
		if root == None:
			return -1
		return self.find(root, x, ans)


class Solution:
	mini = -999

	def floor(self, root, x):
		if root == None:
			if self.mini == -999:
				return -1
			return self.mini
		if root.data < x and root.data > self.mini:
			self.mini = root.data
		if root.data == x:
			return root.data
		if root.data < x:
			return self.floor(root.right, x)
		elif root.data > x:
			return self.floor(root.left, x)


class Solution:

	def floor(self, root, x):
		floor = -1

		def helper(node):
			nonlocal floor
			if not node:
				return
			if node.data <= x:
				floor = node.data
				return helper(node.right)
			else:
				return helper(node.left)
		helper(root)
		return floor


class Solution:

	def helper(self, root, inp, ans):
		if not root:
			return ans
		if root.data == inp:
			ans = inp
			return ans
		if root.data > inp:
			return self.helper(root.left, inp, ans)
		if root.data < inp:
			ans = root.data
			return self.helper(root.right, inp, ans)

	def floor(self, root, x):
		if not root:
			return -1
		ans = -1
		return self.helper(root, x, ans)


class Solution:

	def answer(self, root, ans):
		if root.left:
			self.answer(root.left, ans)
		ans.append(root.data)
		if root.right:
			self.answer(root.right, ans)

	def floor(self, root, x):
		if not root:
			return -1
		ans = []
		self.answer(root, ans)
		num = -1
		for i in ans:
			if i > x:
				return num
			if i == x:
				return i
			num = i
		if num > x:
			return -1
		return num


class Solution:

	def floor(self, root, x):
		queue = [root]
		ans = []
		while queue:
			node = queue.pop(0)
			ans.append(node.data)
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
		ans.sort()
		num = ans[0]
		if num > x:
			return -1
		for i in ans:
			if i > x:
				return num
			elif i == x:
				return i
			num = i
		return num


class Solution:

	def floor(self, root, inp):
		res = -1
		while root != None:
			if root.data > inp:
				root = root.left
			elif root.data < inp:
				res = root.data
				root = root.right
			else:
				res = root.data
				return res
		return res


class Solution:

	def __init__(self):
		self.res = -1

	def inorder(self, temp, key):
		if temp is None:
			return None
		self.inorder(temp.right, key)
		if key == temp.data or temp.data < key:
			if self.res == -1:
				self.res = temp.data
		self.inorder(temp.left, key)

	def floor(self, root, x):
		self.inorder(root, x)
		return self.res


class Solution:

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

	def floor(self, root, x):
		if not root:
			return -1
		if root.data == x:
			self.ans = x
			return x
		if root.data < x:
			self.ans = root.data
		if root.data > x:
			self.floor(root.left, x)
		else:
			self.floor(root.right, x)
		return self.ans


class Solution:

	def floor(self, root, key):
		floor = -1
		while root:
			if root.data == key:
				floor = root.data
				return floor
			if key > root.data:
				floor = root.data
				root = root.right
			else:
				root = root.left
		return floor


class Solution:

	def floor(self, root, x):
		temp = root
		lt = -1
		while temp:
			if temp.data <= x:
				lt = temp.data
				temp = temp.right
			else:
				temp = temp.left
		return lt


class Solution:

	def floor(self, root, x):
		result = -1
		while root is not None:
			if root.data == x:
				result = root.data
				break
			if root.data < x:
				result = root.data
				root = root.right
			else:
				root = root.left
		return result


class Solution:

	def floor(self, root, x):
		return self.floorHelper(root, x, -1)

	def floorHelper(self, root, x, prev):
		if not root:
			return prev
		if root.data == x:
			return x
		elif root.data > x:
			if root.left:
				return self.floorHelper(root.left, x, prev)
			else:
				return prev
		elif root.right:
			return self.floorHelper(root.right, x, root.data)
		else:
			return root.data


class Solution:

	def floor(self, root, inp):
		floor = -1
		if not root:
			return
		while root:
			if root.data == inp:
				return inp
			elif root.data > inp:
				root = root.left
			else:
				floor = root.data
				root = root.right
		return floor