Given a Binary Search Tree and a range [low, high]. Find all the numbers in the BST that lie in the given range.
Note: Element greater than or equal to root go to the right side.
Example 1:
Input:
       17
     /    \
    4     18
  /   \
 2     9 
l = 4, h = 24
Output: 4 9 17 18 
Example 2:
Input:
       16
     /    \
    7     20
  /   \
 1    10
l = 13, h = 23
Output: 16 20 
Your Task:
You don't need to read input or print anything. Your task is to complete the function printNearNodes() which takes the root Node of the BST and the range elements low and high as inputs and returns an array that contains the BST elements in the given range low to high (inclusive) in non-decreasing order.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the BST).
Constraints:
1 ≤ Number of nodes ≤ 10^{4}
1 ≤ l ≤ h ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Range queries

Starter code: #User function Template for python3

class Solution:
    def printNearNodes(self, root, low, high):
        #code here.

Solutions:
class Solution:

	def sample(self, list, root, low, high):
		if not root:
			return
		self.sample(list, root.left, low, high)
		if low <= root.data <= high:
			list.append(root.data)
		self.sample(list, root.right, low, high)
		return list

	def printNearNodes(self, root, low, high):
		list = []
		return self.sample(list, root, low, high)


class Solution:

	def printNearNodes(self, root, low, high):
		res = []

		def t(rt, low, high, res):
			if rt is None:
				return
			if rt.data >= low and rt.data <= high:
				res.append(rt.data)
			t(rt.left, low, high, res)
			t(rt.right, low, high, res)
		t(root, low, high, res)
		res.sort()
		return res


class Solution:

	def printNearNodes(self, root, low, high):
		l = []

		def fun(root, low, high):
			if root:
				if root.data >= low and root.data <= high:
					l.append(root.data)
				fun(root.left, low, high)
				fun(root.right, low, high)
		fun(root, low, high)
		l.sort()
		return l


class Solution:

	def solve(self, root, low, high, arr):
		if root is not None:
			if low < root.data:
				self.solve(root.left, low, high, arr)
			if low <= root.data and high >= root.data:
				arr.append(root.data)
			self.solve(root.right, low, high, arr)

	def printNearNodes(self, root, low, high):
		arr = []
		self.solve(root, low, high, arr)
		return arr


class Solution:

	def inorder(self, root, low, high, arr):
		if root is not None:
			self.inorder(root.left, low, high, arr)
			arr.append(root.data)
			self.inorder(root.right, low, high, arr)

	def printNearNodes(self, root, low, high):
		arr = []
		self.inorder(root, low, high, arr)
		c = 0
		ans = []
		for ele in arr:
			if ele >= low and ele <= high:
				ans.append(ele)
		return ans


class Solution:

	def printNearNodes(self, root, low, high):
		s = [root]
		res = []
		while s:
			node = s.pop(0)
			if low <= node.data <= high:
				res.append(node.data)
			if node.left:
				s.append(node.left)
			if node.right:
				s.append(node.right)
		res.sort()
		return res


def slove(root, low, high, ans):
	if root is None:
		return
	slove(root.left, low, high, ans)
	if root.data >= low and root.data <= high:
		ans.append(root.data)
	slove(root.right, low, high, ans)
	return ans

class Solution:

	def printNearNodes(self, root, low, high):
		ans = []
		slove(root, low, high, ans)
		return ans


class Solution:

	def solve(self, root, low, high, lst):
		if root == None:
			return
		if low > root.data:
			self.solve(root.right, low, high, lst)
		elif high < root.data:
			self.solve(root.left, low, high, lst)
		else:
			lst.append(root.data)
			self.solve(root.left, low, high, lst)
			self.solve(root.right, low, high, lst)

	def printNearNodes(self, root, low, high):
		arr = []
		self.solve(root, low, high, arr)
		arr.sort()
		return arr


class Solution:

	def printNearNodes(self, root, low, high):
		res = []

		def recursive(root, low, high):
			if root is None:
				return
			if root.data <= low:
				if root.data == low:
					res.append(root.data)
				recursive(root.right, low, high)
			elif root.data >= high:
				recursive(root.left, low, high)
				if root.data == high:
					res.append(root.data)
			else:
				recursive(root.left, low, high)
				res.append(root.data)
				recursive(root.right, low, high)
		recursive(root, low, high)
		return res


class Solution:

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

	def printNearNodes(self, root, low, high):
		arr = []
		a = []
		self.inorder(root, arr)
		for i in arr:
			if i >= low and i <= high:
				a.append(i)
		return a


class Solution:

	def printNearNodes(self, root, low, high):
		ans = []
		self.inorder(root, low, high, ans)
		return ans

	def inorder(self, root, low, high, ans):
		if root:
			self.inorder(root.left, low, high, ans)
			if low <= root.data <= high:
				ans.append(root.data)
			self.inorder(root.right, low, high, ans)


class Solution:

	def getT(self, root, l, h, arr):
		if not root:
			return
		val = root.data
		if val >= l and val <= h:
			arr.append(val)
		self.getT(root.right, l, h, arr)
		self.getT(root.left, l, h, arr)

	def printNearNodes(self, root, low, high):
		arr = []
		self.getT(root, low, high, arr)
		arr.sort()
		return arr


class Solution:

	def printNearNodes(self, root, low, high):

		def inorder(root):
			if root is None:
				return
			inorder(root.left)
			arr.append(root.data)
			inorder(root.right)
		arr = []
		ans = []
		inorder(root)
		for i in range(0, len(arr)):
			if arr[i] >= low and arr[i] <= high:
				ans.append(arr[i])
		return ans


class Solution:

	def printNearNodes(self, root, low, high):
		rangeBST = []

		def getRange(root):
			if not root:
				return
			if low <= root.data <= high:
				rangeBST.append(root.data)
			if low <= root.data:
				getRange(root.left)
			if root.data <= high:
				getRange(root.right)
		getRange(root)
		return sorted(rangeBST)


class Solution:

	def printNearNodes(self, root, low, high):

		def helper(root, l):
			if root == None:
				return
			helper(root.left, l)
			if root.data >= low and root.data <= high:
				l.append(root.data)
			helper(root.right, l)
		l = []
		helper(root, l)
		return l


class Solution:

	def printNearNodes(self, root, low, high):
		L = []

		def solve(root):
			if not root:
				return
			solve(root.left)
			if root.data >= low and root.data <= high:
				L.append(root.data)
			solve(root.right)
		solve(root)
		return L


class Solution:

	def printNearNodes(self, root, low, high):
		x = self.inorder(root, [])
		li = []
		for i in x:
			if low <= i and i <= high:
				li.append(i)
		return li

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


class Solution:

	def printNearNodes(self, root, low, high):
		c = []

		def che(c, root, low, high):
			if root:
				che(c, root.left, low, high)
				if root.data >= low and root.data <= high:
					c.append(root.data)
				che(c, root.right, low, high)
		che(c, root, low, high)
		return c


class Solution:

	def printNearNodes(self, root, low, high, lis=None):
		if lis == None:
			lis = []
		if root == None:
			return
		self.printNearNodes(root.left, low, high, lis)
		if root.data >= low and root.data <= high:
			lis.append(root.data)
		self.printNearNodes(root.right, low, high, lis)
		return lis


class Solution:

	def solve(self, root, l, h):
		if root == None:
			return
		if root.data >= l and root.data <= h:
			self.ans.append(root.data)
		self.solve(root.left, l, h)
		self.solve(root.right, l, h)

	def printNearNodes(self, root, low, high):
		self.ans = []
		self.solve(root, low, high)
		self.ans.sort()
		return self.ans


class Solution:

	def printNearNodes(self, root, low, high):
		array = []
		self._nodes(root, low, high, array)
		return array

	def _nodes(self, node, low, high, array):
		if node:
			if node.data >= low and node.data <= high:
				self._nodes(node.left, low, high, array)
				array.append(node.data)
				self._nodes(node.right, low, high, array)
			elif node.data < low:
				self._nodes(node.right, low, high, array)
			elif node.data > high:
				self._nodes(node.left, low, high, array)


class Solution:

	def printNearNodes(self, root, low, high):
		ans = []

		def dfs(root):
			if not root:
				return
			dfs(root.left)
			if low <= root.data <= high:
				ans.append(root.data)
			dfs(root.right)
		dfs(root)
		return ans


class Solution:

	def printNearNodes(self, root, low, high):
		ans = []
		self.find(root, low, high, ans)
		ans.sort()
		return ans

	def find(self, root, low, high, ans):
		if root == None:
			return
		if low <= root.data <= high:
			ans.append(root.data)
		if low <= root.data and high <= root.data:
			self.find(root.left, low, high, ans)
		elif low >= root.data and high >= root.data:
			self.find(root.right, low, high, ans)
		else:
			self.find(root.left, low, high, ans)
			self.find(root.right, low, high, ans)


def func(root, l, h, ans):
	if root is None:
		return
	func(root.left, l, h, ans)
	if l <= root.data <= h:
		ans.append(root.data)
	func(root.right, l, h, ans)

class Solution:

	def printNearNodes(self, root, low, high):
		ans = []
		func(root, low, high, ans)
		return ans


class Solution:

	def returnbw(self, root, k1, k2, ans):
		if root == None:
			return ans
		if root.data >= k1 and root.data <= k2:
			ans.append(root.data)
			self.returnbw(root.left, k1, k2, ans)
			self.returnbw(root.right, k1, k2, ans)
		elif root.data <= k1:
			self.returnbw(root.right, k1, k2, ans)
		elif root.data > k2:
			self.returnbw(root.left, k1, k2, ans)
		return ans

	def printNearNodes(self, root, low, high):
		curr = self.returnbw(root, low, high, [])
		curr.sort()
		return curr


class Solution:

	def printNearNodes(self, root, low, high):
		q = []

		def ino(root, low, high):
			if root is not None:
				ino(root.left, low, high)
				if low <= root.data <= high:
					q.append(root.data)
				ino(root.right, low, high)
		ino(root, low, high)
		return q


class Solution:
	lis = []

	def l_print(self, root, x, y, lis):
		if root == None:
			return lis
		self.l_print(root.left, x, y, lis)
		if root.data >= x and root.data <= y:
			lis.append(root.data)
		self.l_print(root.right, x, y, lis)

	def printNearNodes(self, root, low, high):
		global lis
		lis = []
		self.l_print(root, low, high, lis)
		return lis


class Solution:

	def printNearNodes(self, root, low, high):
		re = []

		def trav(s):
			re.append(s.data)
			if s.left is not None:
				trav(s.left)
			if s.right is not None:
				trav(s.right)
		trav(root)
		a = []
		for i in re:
			if low <= i <= high:
				a.append(i)
		return sorted(a)


class Solution:

	def printNearNodes(self, root, low, high):
		sol = []

		def inorder(node):
			if node is None:
				return
			if low < node.data:
				inorder(node.left)
			if low <= node.data and node.data <= high:
				sol.append(node.data)
			if node.data < high:
				inorder(node.right)
		inorder(root)
		return sol


class Solution:

	def printNearNodes(self, root, low, high):
		res = []

		def helper(root):
			if not root:
				return None
			if root.data >= low and root.data <= high:
				res.append(root.data)
			if root.data > low:
				helper(root.left)
			if root.data < high:
				helper(root.right)
		helper(root)
		return sorted(res)


class Solution:

	def printNearNodes(self, root, low, high):
		list = []

		def within(root, low, high, list):
			if not root:
				return
			if low <= root.data <= high:
				list.append(root.data)
			within(root.left, low, high, list)
			within(root.right, low, high, list)
		within(root, low, high, list)
		list_copy = list.sort()
		return list


class Solution:

	def printNearNodes(self, root, low, high):
		result = []

		def nprint(node):
			if node.left != None:
				nprint(node.left)
			if low <= node.data <= high:
				result.append(node.data)
			if node.right != None:
				nprint(node.right)
		nprint(root)
		return result


from collections import deque

class Solution:

	def printNearNodes(self, root, low, high):
		arr = []
		self.inorder(root, low, high, arr)
		return sorted(arr)

	def inorder(self, root, low, high, arr):
		if root == None:
			return
		if root.data >= low and root.data <= high:
			arr.append(root.data)
		self.inorder(root.left, low, high, arr)
		self.inorder(root.right, low, high, arr)
		return arr


class Solution:

	def printNearNodes(self, root, low, high):
		v = []
		self.inorder(root, low, high, v)
		return v

	def inorder(self, root, low, high, v):
		if root == None:
			return
		self.inorder(root.left, low, high, v)
		if root.data >= low and root.data <= high:
			v.append(root.data)
		self.inorder(root.right, low, high, v)


class Solution:

	def printNearNodes(self, root, low, high):
		res = []
		self.printUtil(root, low, high, res)
		return res

	def printUtil(self, root, low, high, res):
		if not root:
			return
		if root.data > low:
			self.printUtil(root.left, low, high, res)
		if low <= root.data <= high:
			res.append(root.data)
		if root.data < high:
			self.printUtil(root.right, low, high, res)


class Solution:

	def printNearNodes(self, root, low, high):
		a = []

		def near(root, low, high):
			nonlocal a
			if root is None:
				return
			if root.left:
				near(root.left, low, high)
			if low <= root.data <= high:
				a.append(root.data)
			if root.right:
				near(root.right, low, high)
		near(root, low, high)
		return a


class Solution:

	def printNearNodes(self, root, l, h):
		res = []

		def fun(root):
			if not root:
				return
			if h >= root.data >= l:
				res.append(root.data)
			fun(root.left)
			fun(root.right)
		fun(root)
		return sorted(res)


class Solution:

	def Inorder(self, root, low, high, ans):
		if root == None:
			return None
		else:
			self.Inorder(root.left, low, high, ans)
			if low <= root.data <= high:
				ans.append(root.data)
			self.Inorder(root.right, low, high, ans)

	def printNearNodes(self, root, low, high):
		ans = []
		self.Inorder(root, low, high, ans)
		return ans


class Solution:

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

	def printNearNodes(self, root, low, high):
		ans = self.inorder(root, [])
		final_ans = []
		for i in ans:
			if i <= high and i >= low:
				final_ans.append(i)
		return final_ans


class Solution:

	def printNearNodes(self, root, low, high):
		lis = []

		def solve(root):
			if root:
				solve(root.left)
				lis.append(root.data)
				solve(root.right)
		solve(root)
		arr = []
		for i in lis:
			if i in range(low, high + 1):
				arr.append(i)
		return arr


class Solution:

	def printNearNodes(self, root, low, high):
		s = []

		def inorder(root):
			if root != None:
				inorder(root.left)
				if low <= root.data <= high:
					s.append(root.data)
				inorder(root.right)
		inorder(root)
		return s


class Solution:

	def printNearNodes(self, root, low, high):

		def inorder(root):
			if root == None:
				return
			else:
				inorder(root.left)
				res.append(root.data)
				inorder(root.right)
		res = []
		a = []
		inorder(root)
		for i in range(len(res)):
			if res[i] >= low and res[i] <= high:
				a.append(res[i])
		return a


from collections import deque

class Solution:

	def printNearNodes(self, root, l, h):
		li = []
		q = deque()
		q.append(root)
		while q:
			root = q.popleft()
			if root.data >= l and root.data <= h:
				li.append(root.data)
			if root.left:
				q.append(root.left)
			if root.right:
				q.append(root.right)
		return sorted(li)


from collections import deque

class Solution:

	def printNearNodes(self, root, low, high):
		if root == None:
			return []
		q = deque()
		arr = []
		q.append(root)
		while q:
			node = q.popleft()
			if node.data >= low and node.data <= high:
				arr.append(node.data)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		return sorted(arr)


class Solution:

	def printNearNodes(self, root, low, high):
		A = []
		self.x(root, A)
		m = 0
		n = len(A)
		for i in range(len(A)):
			if A[i] < low:
				m = i + 1
			if A[i] > high:
				n = i
				break
		return A[m:n]

	def x(self, root, A):
		if root is None:
			return
		self.x(root.left, A)
		A.append(root.data)
		self.x(root.right, A)


class Solution:

	def printNearNodes(self, root, low, high):

		def inorder(root, low, high, res):
			if not root:
				return
			inorder(root.left, low, high, res)
			if root.data >= low and root.data <= high:
				res.append(root.data)
			inorder(root.right, low, high, res)
		res = []
		inorder(root, low, high, res)
		return res


class Solution:

	def printNearNodes(self, root, low, high):
		res = []

		def inorder(root, low, high):
			nonlocal res
			if root:
				inorder(root.left, low, high)
				if low <= root.data <= high:
					res.append(root.data)
				inorder(root.right, low, high)
		inorder(root, low, high)
		return res


class Solution:

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

	def printNearNodes(self, root, low, high):

		def traversal(root):
			if root == None:
				return None
			if root.left:
				traversal(root.left)
			if low <= root.data <= high:
				list1.append(root.data)
			if root.right:
				traversal(root.right)
		list1 = []
		traversal(root)
		return list1


class Solution:

	def printNearNodes(self, root, low, high):
		q = deque()
		q.append(root)
		lis = []
		while q:
			node = q.popleft()
			if node.data >= low and node.data <= high:
				lis.append(node.data)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
		lis.sort()
		return lis


class Solution:

	def printNearNodes(self, root, low, high):
		arr = []
		q = []
		q.append(root)
		while len(q) > 0:
			node = q.pop(0)
			if node.left:
				q.append(node.left)
			if node.right:
				q.append(node.right)
			if node.data <= high and node.data >= low:
				arr.append(node.data)
		arr.sort()
		return arr


class Solution:

	def printNearNodes(self, root, low, high):
		if root == None:
			return []
		q = deque([root])
		arr = []
		while q:
			l = len(q)
			for i in range(l):
				curr = q.popleft()
				if curr.data >= low and curr.data <= high:
					arr.append(curr.data)
				if curr.left:
					q.append(curr.left)
				if curr.right:
					q.append(curr.right)
		arr.sort()
		return arr


class Solution:

	def printNearNodes(self, root, low, high):
		_root = self._get_root(root, low, high)
		res = []
		self._in_order_traversal(_root, res)
		return [_ for _ in res if _ >= low and _ <= high]

	def _in_order_traversal(self, root, res):
		if root:
			self._in_order_traversal(root.left, res)
			res.append(root.data)
			self._in_order_traversal(root.right, res)

	def _get_root(self, root, low, high):
		if not root:
			return None
		elif root.data > low and root.data > high:
			return root.left
		elif root.data < low and root.data < high:
			return root.right
		return root


class Solution:

	def solve(self, root, low, high, ans):
		if not root:
			return
		if root.data > high:
			self.solve(root.left, low, high, ans)
		elif root.data < low:
			self.solve(root.right, low, high, ans)
		else:
			self.solve(root.left, low, high, ans)
			ans.append(root.data)
			self.solve(root.right, low, high, ans)

	def printNearNodes(self, root, low, high):
		ans = []
		self.solve(root, low, high, ans)
		return ans


class Solution:

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

	def printNearNodes(self, root, low, high):
		self.printNode(root, low, high)
		return self.l

	def printNode(self, root, low, high):
		if root is None:
			return root
		self.printNode(root.left, low, high)
		if low <= root.data <= high:
			self.l.append(root.data)
		self.printNode(root.right, low, high)


class Solution:

	def printNearNodes(self, root, low, high):
		arr = []
		self.getValues(root, arr, low, high)
		return arr

	def getValues(self, root, arr, low, high):
		if not root:
			return
		self.getValues(root.left, arr, low, high)
		if low <= root.data <= high:
			arr.append(root.data)
		self.getValues(root.right, arr, low, high)
		return


class Solution:

	def printNearNodes(self, root, low, high):

		def sam(s):
			if s is None:
				return
			b = s.data
			if low <= b <= high:
				e.append(b)
			if s.left:
				sam(s.left)
			if s.right:
				sam(s.right)
		e = []
		sam(root)
		e.sort()
		return e


class Solution:

	def printNearNodes(self, root, low, high):

		def samp(sub):
			if sub is None:
				return
			b = sub.data
			if low <= b <= high:
				e.append(b)
			if sub.left:
				samp(sub.left)
			if sub.right:
				samp(sub.right)
		e = []
		samp(root)
		e.sort()
		return e


class Solution:

	def printNearNodes(self, root, low, high):
		l = []

		def trav(root):
			if root:
				trav(root.left)
				if root.data >= low and root.data <= high:
					l.append(root.data)
				trav(root.right)
		trav(root)
		return l


class Solution:

	def printNearNodes(self, root, low, high):
		if not root:
			return []
		result = []
		if low < root.data:
			result.extend(self.printNearNodes(root.left, low, high))
		if low <= root.data <= high:
			result.append(root.data)
		if high > root.data:
			result.extend(self.printNearNodes(root.right, low, high))
		return result


class Solution:

	def printNearNodes(self, root, low, high):
		q = [root]
		temp = []
		while q:
			l = len(q)
			for i in range(l):
				if len(q) != 0:
					x = q.pop(0)
					if x.data <= high and x.data >= low:
						temp.append(x.data)
					if x.left and x.data > low:
						q.append(x.left)
					if x.right and x.data < high:
						q.append(x.right)
		return sorted(temp)


class Solution:

	def printNearNodes(self, root, low, high):
		res = []
		if not root:
			return res
		self.findNodes(root, low, high, res)
		return sorted(res)

	def findNodes(self, root, l, h, res):
		if not root:
			return
		if root.data >= l and root.data <= h:
			res.append(root.data)
		if root.data > h:
			self.findNodes(root.left, l, h, res)
		elif root.data < l:
			self.findNodes(root.right, l, h, res)
		else:
			self.findNodes(root.left, l, h, res)
			self.findNodes(root.right, l, h, res)


class Solution:

	def printNearNodes(self, root, low, high):
		l = []
		if not root:
			return []
		if root.data in range(low, high + 1):
			l.append(root.data)
		if root.left:
			l += self.printNearNodes(root.left, low, high)
		if root.right:
			l += self.printNearNodes(root.right, low, high)
		l.sort()
		return l


class Solution:

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

	def printNearNodes(self, root, low, high):
		if root != None:
			self.printNearNodes(root.left, low, high)
			if root.data <= high and root.data >= low:
				self.res.append(root.data)
			self.printNearNodes(root.right, low, high)
			return self.res


class Solution:

	def printNearNodes(self, root, low, high):
		l = []

		def pre(root):
			if root:
				pre(root.left)
				l.append(root.data)
				pre(root.right)
		pre(root)
		m = []
		for i in l:
			if i >= low and i <= high:
				m.append(i)
		return m