Given a BST and a number X, find Ceil of X.
Note: Ceil(X) is a number that is either equal to X or is immediately greater than X.
Example 1:
Input:
      5
    /   \
   1     7
    \
     2 
      \
       3
X = 3
Output: 3
Explanation: We find 3 in BST, so ceil
of 3 is 3.
Example 2:
Input:
     10
    /  \
   5    11
  / \ 
 4   7
      \
       8
X = 6
Output: 7
Explanation: We find 7 in BST, so ceil
of 6 is 7.
Your task:
You don't need to read input or print anything. Just complete the function findCeil() to implement ceil in BST which returns the ceil of X in the given BST.
Expected Time Complexity: O(Height of the BST)
Expected Auxiliary Space: O(Height of the BST).
Constraints:
1 <= Number of nodes <= 10^{5}
1 <= Value of nodes<= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Range queries

Starter code: #Function to return the ceil of given number in BST.



class Solution:

    def findCeil(self,root, inp):

        # code here

Solutions:
class Solution:

	def findCeil(self, root, x):
		ceil = -1
		while root:
			if root.key == x:
				return x
			if root.key < x:
				root = root.right
			elif root.key > x:
				ceil = root.key
				root = root.left
		return ceil


class Solution:

	def findCeil(self, root, inp):
		if root is None:
			return None
		value = -1
		while root is not None:
			if inp == root.key:
				return root.key
			elif inp < root.key:
				value = root.key
				root = root.left
			else:
				root = root.right
		return value


class Solution:

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


class Solution:

	def findCeil(self, root, inp):
		if root == None:
			return root
		ceil = -1
		while root:
			if root.key < inp:
				root = root.right
			else:
				ceil = root.key
				root = root.left
		return ceil


class Solution:

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

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


class Solution:

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

	def findCeil(self, root, inp):
		if root is None:
			return self.prev
		if root.key == inp:
			return root.key
		if root.key > inp:
			self.prev = root.key
			return self.findCeil(root.left, inp)
		if root.key < inp:
			return self.findCeil(root.right, inp)


class Solution:

	def findCeil(self, root, inp):

		def inorder(root):
			nonlocal ans, inp
			if not root:
				return
			inorder(root.left)
			if root.key >= inp:
				if ans == -1:
					ans = root.key
				elif ans > root.key:
					ans = root.key
			inorder(root.right)
		ans = -1
		inorder(root)
		return ans


class Solution:

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


class Solution:

	def findCeil(self, node, inp):
		c = -1
		while node:
			if node.key == inp:
				return node.key
			elif node.key > inp:
				c = node.key
				node = node.left
			else:
				node = node.right
		return c


class Solution:

	def inorder(self, root, arr, inp):
		if root is not None:
			self.inorder(root.left, arr, inp)
			arr.append(root.key)
			self.inorder(root.right, arr, inp)

	def findCeil(self, root, inp):
		arr = []
		self.inorder(root, arr, inp)
		z = []
		for ele in arr:
			if ele == inp:
				return ele
			else:
				z.append(ele)
		for ele in z:
			if ele > inp:
				return ele
		return -1


import sys

class Solution:

	def util(self, root, inp):
		global ans
		if root == None:
			return
		if root.key == inp:
			if ans[0] > inp - root.key:
				ans = [0, root.key]
			return
		elif root.key > inp:
			if ans[0] > root.key - inp:
				ans = [root.key - inp, root.key]
			self.util(root.left, inp)
		else:
			self.util(root.right, inp)

	def findCeil(self, root, inp):
		global ans
		ans = [sys.maxsize, -1]
		self.util(root, inp)
		return ans[1]


class Solution:

	def findCeil(self, root, inp):
		curr = root
		prevmax = None
		while curr is not None:
			if curr.key == inp:
				return curr.key
			if curr.key < inp:
				curr = curr.right
			else:
				prevmax = curr
				curr = curr.left
		return prevmax.key if prevmax is not None else -1


class Solution:

	def findCeil(self, node, x):
		val = -1
		while node:
			if node.key == x:
				return node.key
			elif node.key > x:
				val = node.key
				node = node.left
			elif node.key < x:
				node = node.right
		return val


class Solution:

	def findCeil(self, root, x):
		if root == None:
			return -1
		if x < root.key:
			tmp = self.findCeil(root.left, x)
			return min(root.key, tmp) if tmp != -1 else root.key
		elif x > root.key:
			return self.findCeil(root.right, x)
		return root.key


class Solution:

	def dfs(self, node, target, prev):
		if not node:
			return
		if node.key == target:
			return target
		if node.key > target:
			if node.left:
				return self.dfs(node.left, target, node)
			else:
				return node.key
		elif node.right:
			return self.dfs(node.right, target, prev)
		else:
			return prev.key

	def findCeil(self, root, inp):
		return self.dfs(root, inp, Node(-1))


class Solution:

	def findCeil(self, root, inp):
		ans = -1
		curr = root
		while curr:
			while curr and curr.key < inp:
				curr = curr.right
			if curr and curr.key == inp:
				return inp
			while curr and curr.key > inp:
				ans = curr.key
				curr = curr.left

		def helper(root, inp):
			if root is None:
				return 100001
			if root.key == inp:
				return inp
			if root.key > inp:
				return min(root.key, helper(root.left, inp))
			else:
				return helper(root.right, inp)
		return ans


class Solution:

	def findCeil(self, root, inp):

		def walk(node):
			if not node:
				return -1
			if node.key == inp:
				return inp
			if node.key < inp:
				return walk(node.right)
			x = walk(node.left)
			return node.key if x == -1 else x
		return walk(root)


class Solution:

	def findCeil(self, root, inp):
		if root is None:
			return -1
		if root.key == inp:
			return inp
		elif root.key < inp:
			return self.findCeil(root.right, inp)
		val = self.findCeil(root.left, inp)
		if val >= inp and val != -1:
			return val
		else:
			return root.key


class Solution:

	def calculate(self, root, inp, ans):
		if not root:
			return ans
		if inp <= root.key:
			ans = root.key
			return self.calculate(root.left, inp, ans)
		elif inp > root.key:
			return self.calculate(root.right, inp, ans)

	def findCeil(self, root, inp):
		ans = -1
		return self.calculate(root, inp, ans)


class Solution:

	def findCeil(self, root, inp):
		m = 10 ** 9
		while root:
			if root.key >= inp:
				m = min(m, root.key)
				root = root.left
			else:
				root = root.right
		return m if m != 10 ** 9 else -1


class Solution:

	def findCeil(self, root, inp):
		li = self.inorder(root, [])
		if inp in li:
			return inp
		else:
			li.append(inp)
			li.sort()
			x = li.index(inp)
			try:
				return li[x + 1]
			except IndexError:
				return -1

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


class Solution:

	def findCeil(self, root, inp):
		if root == None:
			return -1
		if root.key == inp:
			return root.key
		if root.key < inp:
			return self.findCeil(root.right, inp)
		val = self.findCeil(root.left, inp)
		return val if val >= inp else root.key


class Solution:
	maxi = 99999

	def findCeil(self, root, inp):
		if root == None:
			if self.maxi == 99999:
				return -1
			return self.maxi
		if root.key >= inp and root.key < self.maxi:
			self.maxi = root.key
		if root.key == inp:
			return root.key
		if inp < root.key:
			return self.findCeil(root.left, inp)
		elif inp > root.key:
			return self.findCeil(root.right, inp)


class Solution:

	def findCeil(self, root, inp):
		ceil = -1

		def helper(node):
			nonlocal ceil
			if not node:
				return
			if node.key >= inp:
				ceil = node.key
				return helper(node.left)
			else:
				return helper(node.right)
		helper(root)
		return ceil


class Solution:

	def answer(self, root, x, ans):
		if root.key == x:
			ans[0] = x
			return
		elif root.key > x:
			ans[0] = root.key
			if root.left:
				self.answer(root.left, x, ans)
		elif root.key < x:
			if root.right:
				self.answer(root.right, x, ans)

	def findCeil(self, root, inp):
		if not root:
			return -1
		ans = [root.key]
		self.answer(root, inp, ans)
		if ans[0] < inp:
			return -1
		return ans[0]


class Solution:

	def findCeil(self, root, x):
		(cur, res) = (root, -1)
		while cur:
			if x < cur.key:
				res = cur.key
				cur = cur.left
			elif x > cur.key:
				cur = cur.right
			else:
				return x
		return res


class Solution:

	def findCeil(self, root, inp):
		ceil_val = -1
		while root:
			if root.key == inp:
				ceil_val = root.key
				break
			elif root.key < inp:
				root = root.right
			else:
				ceil_val = root.key
				root = root.left
		return ceil_val


class Solution:

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

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


class Solution:

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

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

	def findCeil(self, root, inp):
		self.inorder(root, inp)
		return self.res


class Solution:

	def find(self, root, inp, res):
		if not root:
			return
		if root.key >= inp:
			res[0] = min(res[0], root.key)
		if inp < root.key:
			self.find(root.left, inp, res)
		else:
			self.find(root.right, inp, res)

	def findCeil(self, root, inp):
		res = [float('inf')]
		self.find(root, inp, res)
		return -1 if res[0] == float('inf') else res[0]


class Solution:

	def findCeil(self, root, inp):
		temp = root
		lt = -1
		while temp:
			if temp.key >= inp:
				lt = temp.key
				temp = temp.left
			elif temp.key < inp:
				temp = temp.right
			else:
				temp = temp.left
		return lt


class Solution:

	def findCeil(self, root, imp):
		ceil = -1
		while root is not None:
			if root.key == imp:
				return root.key
			if root.key > imp:
				ceil = root.key
				root = root.left
			else:
				root = root.right
		return ceil


class Solution:

	def helper(self, node, ceil, imp):
		if node is None:
			return ceil
		if node.key == imp:
			return node.key
		if node.key > imp:
			ceil = node.key
			return self.helper(node.left, ceil, imp)
		else:
			return self.helper(node.right, ceil, imp)

	def findCeil(self, root, imp):
		return self.helper(root, -1, imp)


class Solution:

	def helper(self, node, prev, x):
		if node is None:
			return -1 if prev is None else prev.key
		if node.key == x:
			return node.key
		if node.key > x:
			prev = node
			return self.helper(node.left, prev, x)
		else:
			return self.helper(node.right, prev, x)

	def findCeil(self, root, x):
		return self.helper(root, None, x)


class Solution:

	def findCeil(self, root, inp):

		def find(root, inp):
			if root:
				if root.key == inp:
					ans[0] = root.key
					return
				elif root.key >= inp:
					ans[0] = root.key
					return find(root.left, inp)
				else:
					return find(root.right, inp)
			return
		ans = [-1]
		find(root, inp)
		return ans[0]


class Solution:

	def findCeil(self, root, inp):
		left = 0
		right = 0
		if root.left is not None:
			left = self.findCeil(root.left, inp)
		if root.right is not None:
			right = self.findCeil(root.right, inp)
		ans = root.key
		if inp <= left <= ans or inp > ans:
			ans = left
		if inp <= right <= ans or inp > ans:
			ans = right
		if ans < inp:
			ans = -1
		return ans


class Solution:

	def findCeil(self, root, inp):
		return self.findRec(root, inp, -1)

	def findRec(self, root, inp, prev):
		if not root:
			return -1
		if root.key == inp:
			return root.key
		elif root.key < inp:
			if root.right:
				return self.findRec(root.right, inp, prev)
			else:
				return prev
		elif root.left:
			return self.findRec(root.left, inp, root.key)
		else:
			return root.key


class Solution:

	def findCeil(self, root, inp):
		ceil = -1
		if not root:
			return
		while root:
			if root.key == inp:
				return inp
			elif root.key < inp:
				root = root.right
			else:
				ceil = root.key
				root = root.left
		return ceil


class Solution:

	def findCeil(self, root, inp):

		def ino(root):
			if root is None:
				return
			if root.key >= inp:
				l.append(root.key)
			ino(root.left)
			ino(root.right)
		l = []
		ino(root)
		if len(l) == 0:
			return -1
		return min(l)


import math

class Solution:

	def findCeil(self, root, inp):
		ceil = -1
		while root:
			if root.key == inp:
				ceil = inp
				return ceil
			if root.key < inp:
				root = root.right
			else:
				ceil = root.key
				root = root.left
		return ceil


import math

class Solution:

	def findCeil(self, root, inp):
		if not root:
			return -1
		if root.key == inp:
			return root.key
		if root.key < inp:
			return self.findCeil(root.right, inp)
		ceil_val = self.findCeil(root.left, inp)
		if ceil_val == -1:
			return root.key
		else:
			return ceil_val


class Solution:

	def check(self, root, minval, maxval):
		if root is None:
			return root
		if minval == root.key:
			maxval[0] = root.key
			return root
		if minval < root.key:
			maxval[0] = root.key
			return self.check(root.left, minval, maxval)
		else:
			return self.check(root.right, minval, maxval)

	def findCeil(self, root, inp):
		maxval = [-1]
		self.check(root, inp, maxval)
		return maxval[0]


class Solution:

	def findCeil(self, root, inp):
		self.ans = root.key

		def help(root):
			if not root:
				return None
			if root.key == inp:
				self.ans = root.key
				return
			elif root.key > inp:
				if root.key >= inp:
					self.ans = root.key
				help(root.left)
			elif root.key < inp:
				help(root.right)
		help(root)
		if self.ans >= inp:
			return self.ans
		else:
			return -1


class Solution:

	def findCeil(self, root, k):
		re = []

		def trav(r):
			re.append(r.key)
			if r.left is not None:
				trav(r.left)
			if r.right is not None:
				trav(r.right)
		trav(root)
		re = sorted(re)
		pr = 0
		if k in re:
			return k
		for i in re:
			if i > k:
				return i
		return -1


class Solution:

	def findCeil(self, root, inp):
		if root == None:
			return -1
		res = -1
		return self.hel(root, inp, res)

	def hel(self, root, inp, res):
		if root == None:
			return res
		elif root.key == inp:
			res = inp
			return res
		elif root.key > inp:
			res = root.key
			return self.hel(root.left, inp, res)
		elif root.key < inp:
			return self.hel(root.right, inp, res)


class Solution:

	def findCeil(self, root, x):
		ceil = 999989
		curr = root
		while curr:
			if curr.key > x:
				ceil = min(ceil, curr.key)
				curr = curr.left
			elif curr.key < x:
				curr = curr.right
			else:
				return curr.key
		if ceil == 999989:
			return -1
		else:
			return ceil


import math

class Solution:

	def findCeil(self, root, inp):
		self.ceil = math.inf

		def helper(root, inp):
			if root is None:
				return
			if root.key == inp:
				self.ceil = root.key
				return
			if inp < root.key:
				self.ceil = root.key
				helper(root.left, inp)
			else:
				helper(root.right, inp)
		helper(root, inp)
		if self.ceil == math.inf:
			return -1
		return self.ceil