Given a Binary Search Tree (BST) and a range l-h(inclusive), count the number of nodes in the BST that lie in the given range. 
	The values smaller than root go to the left side
	The values greater and equal to the root go to the right side
Example 1:
Input:
      10
     /  \
    5    50
   /    /  \
  1    40  100
l = 5, h = 45
Output: 3
Explanation: 5 10 40 are the node in the
range
Example 2:
Input:
     5
    /  \
   4    6
  /      \
 3        7
l = 2, h = 8
Output: 5
Explanation: All the nodes are in the
given range.
Your Task:
This is a function problem. You don't have to take input. You are required to complete the function getCountOfNode() that takes root, l ,h as parameters and returns the count.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(Height of the BST).
Constraints:
1 <= Number of nodes <= 100
1 <= l < h < 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Range queries

Starter code: #User function Template for python3





#Function to count number of nodes in BST that lie in the given range.

class Solution:

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

        ##Your code here

Solutions:
class Solution:

	def solve(self, root, low, high):
		if root is None:
			return
		if low <= root.data <= high:
			self.cnt += 1
		self.solve(root.left, low, high)
		self.solve(root.right, low, high)

	def getCount(self, root, low, high):
		self.cnt = 0
		self.solve(root, low, high)
		return self.cnt


class Solution:

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

		def count(root, cnt):
			if root == None:
				return
			if root.data > high:
				count(root.left, cnt)
			elif root.data < low:
				count(root.right, cnt)
			else:
				cnt[0] += 1
				count(root.left, cnt)
				count(root.right, cnt)
		cnt = [0]
		count(root, cnt)
		return cnt[0]


class Solution:

	def solve(self, root, left, right):
		if root:
			self.solve(root.left, left, right)
			if left <= root.data <= right:
				self.count += 1
			self.solve(root.right, left, right)

	def getCount(self, root, low, high):
		self.count = 0
		self.solve(root, low, high)
		return self.count


class Solution:

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

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


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 getCount(self, root, low, high):
		arr = []
		c = 0
		self.inorder(root, arr)
		for ele in arr:
			if low <= ele and ele <= high:
				c = c + 1
		return c


class Solution:

	def getCount(self, root, low, high):
		count = 0
		if root.data >= low and root.left is not None:
			count += self.getCount(root.left, low, high)
		if root.data <= high and root.right is not None:
			count += self.getCount(root.right, low, high)
		return count + 1 if root.data >= low and root.data <= high else count


class Solution:

	def getCount(self, root, low, high):
		if root == None:
			return 0
		if root.data >= low and root.data <= high:
			return 1 + self.getCount(root.left, low, high) + self.getCount(root.right, low, high)
		elif root.data < low:
			return self.getCount(root.right, low, high)
		elif root.data > high:
			return self.getCount(root.left, low, high)


class Solution:

	def getCount(self, root, low, high):
		count = 0

		def dfs(root):
			if not root:
				return
			if low <= root.data <= high:
				nonlocal count
				count += 1
			if root.data >= low:
				dfs(root.left)
			if root.data <= high:
				dfs(root.right)
		dfs(root)
		return count


from collections import deque

class Solution:

	def getCount(self, root, low, high):
		P = deque()
		P.append(root)
		S = 0
		while P:
			n = len(P)
			for i in range(n):
				a = P.popleft()
				if low <= a.data <= high:
					S += 1
				if a.left:
					P.append(a.left)
				if a.right:
					P.append(a.right)
		return S


class Solution:

	def util(self, root, low, high):
		global count
		if root == None:
			return
		if root.data >= low and root.data <= high:
			count += 1
		if root.data > low:
			self.util(root.left, low, high)
		if root.data < high:
			self.util(root.right, low, high)

	def getCount(self, root, low, high):
		global count
		count = 0
		self.util(root, low, high)
		return count


class Solution:

	def getCount(self, root, low, high):
		self.count = 0

		def traverse(root):
			if not root:
				return
			if root.data >= low and root.data <= high:
				self.count += 1
			traverse(root.left)
			traverse(root.right)
		traverse(root)
		return self.count


class Solution:

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

		def ranges(root, low, high):
			if not root:
				return 0
			if root.data in range(low, high + 1):
				l = ranges(root.left, low, high)
				r = ranges(root.right, low, high)
				return l + r + 1
			elif root.data > high:
				return ranges(root.left, low, high)
			else:
				return ranges(root.right, low, high)
		return ranges(root, low, high)


class Solution:

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

		def check(root, max, min):
			if root == None:
				return 0
			if root.data > min - 1 and root.data < max + 1:
				l = check(root.left, max, min)
				r = check(root.right, max, min)
				return l + r + 1
			elif root.data > max:
				return check(root.left, max, min)
			else:
				return check(root.right, max, min)
		return check(root, high, low)


class Solution:

	def getCount(self, root, low, high):
		a = []
		c = 0

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


class Solution:

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

		def helper(node):
			if not node:
				return 0
			if node.data < low:
				return helper(node.right)
			if node.data > high:
				return helper(node.left)
			return 1 + helper(node.left) + helper(node.right)
		return helper(root)


class Solution:

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

		def dfs(root, l, h):
			nonlocal c
			if root.data >= l and root.data <= h:
				c = c + 1
			if root.left != None:
				dfs(root.left, l, h)
			if root.right != None:
				dfs(root.right, l, h)
		c = 0
		dfs(root, low, high)
		return c


class Solution:

	def getCount(self, root, low, high):
		if root is None:
			return 0
		leftSubTree = 0
		rightSubTree = 0
		current = 0
		if low < root.data:
			leftSubTree = self.getCount(root.left, low, high)
		if low <= root.data <= high:
			current += 1
		if high >= root.data:
			rightSubTree = self.getCount(root.right, low, high)
		return leftSubTree + rightSubTree + current


class Solution:

	def getCount(self, root, low, high):
		return self._getCount(root, low, high)

	def _getCount(self, node, l, h) -> int:
		if not node:
			return 0
		if l <= node.data <= h:
			return 1 + self._getCount(node.left, l, h) + self._getCount(node.right, l, h)
		else:
			return self._getCount(node.left, l, h) + self._getCount(node.right, l, h)


class Solution:

	def getCount(self, root, low, high):
		return self._getcount(root, low, high)

	def _getcount(self, node, low, high):
		if not node:
			return 0
		left_count = self._getcount(node.left, low, high)
		right_count = self._getcount(node.right, low, high)
		if low <= node.data <= high:
			return 1 + left_count + right_count
		else:
			return left_count + right_count


import sys

class Solution:

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

		def countnode(root, lb, ub):
			if not root:
				return
			if root.data in range(lb, ub + 1):
				self.count += 1
			countnode(root.left, lb, ub)
			countnode(root.right, lb, ub)
		self.count = 0
		countnode(root, low, high)
		return self.count


class Solution:

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

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


class Solution:

	def __init__(self):
		self.count = 0

	def getCount(self, root, low, high):
		if not root:
			return 0
		if root.data < low:
			return self.getCount(root.right, low, high)
		elif root.data > high:
			return self.getCount(root.left, low, high)
		else:
			return 1 + self.getCount(root.left, low, high) + self.getCount(root.right, low, high)


class Solution:

	def getCount(self, root, low, high):
		self.total = 0

		def f(root):
			if not root:
				return
			if root.data <= high and root.data >= low:
				self.total += 1
				f(root.left)
				f(root.right)
				return
			elif root.data < low:
				f(root.right)
			elif root.data > high:
				f(root.left)
			else:
				return
		f(root)
		return self.total


class Solution:

	def getCount(self, root, low, high):
		ans = 0
		if root.left:
			ans += self.getCount(root.left, low, high)
		if root.right:
			ans += self.getCount(root.right, low, high)
		if low <= root.data <= high:
			ans += 1
		return ans


class Solution:

	def getTrav(self, root, low, high, li):
		if root:
			if root.data >= low and root.data <= high:
				li[0] += 1
			self.getTrav(root.left, low, high, li)
			self.getTrav(root.right, low, high, li)

	def getCount(self, root, low, high):
		li = [0]
		if root:
			self.getTrav(root, low, high, li)
			return li[0]
		else:
			return li[0]


class Solution:

	def getCount(self, root, low, high):
		x = self.order(root, [])
		c = 0
		for i in x:
			if low <= i and i <= high:
				c += 1
		return c

	def order(self, node, a):
		if node:
			a.append(node.data)
			self.order(node.left, a)
			self.order(node.right, a)
		return a


class Solution:

	def nodes(self, root, k):
		if not root:
			return k
		k.append(root.data)
		self.nodes(root.left, k)
		self.nodes(root.right, k)

	def getCount(self, root, low, high):
		k = []
		self.nodes(root, k)
		c = 0
		for i in k:
			if i >= low and i <= high:
				c += 1
		return c


class Solution:

	def count(self, root, l, h):
		if root is None:
			return
		self.count(root.left, l, h)
		if root.data >= l and root.data <= h:
			self.c += 1
		self.count(root.right, l, h)

	def getCount(self, root, low, high):
		self.c = 0
		self.count(root, low, high)
		return self.c


def check(root, lst):
	if root:
		check(root.left, lst)
		lst.append(root.data)
		check(root.right, lst)

class Solution:

	def getCount(self, root, low, high):
		lst = []
		check(root, lst)
		cnt = 0
		for i in lst:
			if i >= low and i <= high:
				cnt += 1
		return cnt


class Solution:

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

		def traverse(root):
			if root is None:
				return []
			return traverse(root.left) + [root.data] + traverse(root.right)
		arr = traverse(root)
		countOfNodes = 0
		for i in range(len(arr)):
			if arr[i] >= low and arr[i] <= high:
				countOfNodes += 1
		return countOfNodes


class Solution:

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

		def trav(rot):
			re.append(rot.data)
			if rot.left is not None:
				trav(rot.left)
			if rot.right is not None:
				trav(rot.right)
		trav(root)
		re = sorted(re)
		ans = 0
		for i in re:
			if low <= i <= high:
				ans += 1
		return ans


class Solution:

	def getCount(self, root, low, high):
		count = [0]

		def countnodes(root, low, high):
			if root == None:
				return
			if high < root.data:
				countnodes(root.left, low, high)
				return
			if low <= root.data and root.data <= high:
				count[0] += 1
			if l >= root.data:
				countnodes(root.right, low, high)
				return
			countnodes(root.left, low, root.data - 1)
			countnodes(root.right, root.data, high)
			return
		countnodes(root, low, high)
		return count[0]


class Solution:

	def __init__(self):
		self.ans = 0

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

		def inorder(root, low, high):
			if root:
				inorder(root.left, low, high)
				if root.data <= high and root.data >= low:
					self.ans += 1
				inorder(root.right, low, high)
		inorder(root, low, high)
		return self.ans


class Solution:

	def getCount(self, root, low, high):
		q = []
		c = 0
		q.append(root)
		while q:
			z = q.pop(0)
			if low <= z.data <= high:
				c += 1
			if z.left is not None:
				q.append(z.left)
			if z.right is not None:
				q.append(z.right)
		return c


class Solution:

	def getCount(self, root, low, high):
		count = 0

		def preorder(node, low, high):
			if not node:
				return
			nonlocal count
			if node.data in range(low, high + 1):
				count += 1
			preorder(node.left, low, high)
			preorder(node.right, low, high)
		preorder(root, low, high)
		return count


class Solution:

	def inorder(self, root):
		v = []
		if root:
			v = self.inorder(root.left)
			v.append(root.data)
			v += self.inorder(root.right)
		return v

	def getCount(self, root, low, high):
		if root is None:
			return
		ans = []
		ans = self.inorder(root)
		count = 0
		for i in range(len(ans)):
			if ans[i] >= low and ans[i] <= high:
				count += 1
		return count


class Solution:

	def getCount(self, root, low, high):
		if root == None:
			return 0
		l = self.getCount(root.left, low, high)
		r = self.getCount(root.right, low, high)
		if low <= root.data <= high:
			return l + r + 1
		else:
			return l + r


class Solution:

	def getCount(self, root, low, high):
		queue = [root]
		res = []
		while queue:
			level = []
			val = []
			for i in queue:
				if i == None:
					continue
				val.append(i.data)
				level.append(i.left)
				level.append(i.right)
			if val:
				res += val
			queue = level
		count = 0
		for i in res:
			if i >= low and i <= high:
				count += 1
		return count


class Solution:

	def getCount(self, root, low, high):
		vals = []

		def inorder(root):
			if root == None:
				return
			nonlocal vals
			inorder(root.left)
			vals.append(root.data)
			inorder(root.right)
			return vals
		inorder(root)
		count = 0
		for i in vals:
			if i < low:
				continue
			if i >= low and i <= high:
				count += 1
			if i > high:
				return count
		return count


class Solution:

	def find(node, ino):
		if node:
			Solution.find(node.left, ino)
			ino.append(node.data)
			Solution.find(node.right, ino)
		else:
			return

	def getCount(self, root, low, high):
		ino = []
		Solution.find(root, ino)
		cnt = 0
		for val in ino:
			if val >= low and val <= high:
				cnt += 1
		return cnt


class Solution:

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

		def count(root, low, high, list):
			if not root:
				return
			if low <= root.data <= high:
				list.append(root.data)
			count(root.left, low, high, list)
			count(root.right, low, high, list)
		list = []
		count(root, low, high, list)
		return len(list)


class Solution:

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

		def dfs(root, count, l, h):
			if not root:
				return 0
			left = dfs(root.left, count, l, h)
			right = dfs(root.right, count, l, h)
			if root.data >= l and root.data <= r:
				count += 1
			return count + left + right
		return dfs(root, 0, low, high)


class Solution:

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

		def foo(root, low, high, res):
			if not root:
				return
			foo(root.left, low, high, res)
			if root.data >= low and root.data <= high:
				res[0] += 1
			foo(root.right, low, high, res)
		res = [0]
		foo(root, low, high, res)
		return res[0]


class Solution:

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

		def helper(root):
			x = []
			if not root:
				return x
			x += helper(root.left)
			x.append(root.data)
			x += helper(root.right)
			return x
		ans = 0
		cur = helper(root)
		for i in cur:
			if i > high:
				break
			if i >= low:
				ans += 1
		return ans


def func(root, l, h, ans):
	if root is None:
		return
	if l <= root.data <= h:
		ans[0] += 1
	if root.data > l:
		func(root.left, l, h, ans)
	if root.data < h:
		func(root.right, l, h, ans)

class Solution:

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


class Solution:

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

		def f(t):
			if t == None:
				return
			f(t.left)
			if t.data >= low and t.data <= high:
				l[0] += 1
			f(t.right)
		f(root)
		return l[0]


class Solution:

	def getCount(self, root, low, high):
		s = []
		cur = root
		while cur:
			s.append(cur)
			cur = cur.left
		res = 0
		while s:
			top = s.pop()
			if low <= top.data <= high:
				res += 1
			cur = top.right
			while cur:
				s.append(cur)
				cur = cur.left
		return res


class Solution:

	def ount(self, root, low, high):
		if not root:
			return
		if root.data >= low and root.data <= high:
			self.c += 1
		self.ount(root.left, low, high)
		self.ount(root.right, low, high)

	def getCount(self, root, low, high):
		self.c = 0
		self.ount(root, low, high)
		return self.c


class Solution:

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

	def getCount(self, root, low, high):
		arr = []
		self.find(root, low, high, arr)
		return len(arr)


class Solution:

	def getCount(self, root, low, high):
		if root == None:
			return 0
		lsize = 0
		rsize = 0
		if root.data > low:
			lsize = self.getCount(root.left, low, high)
		if root.data < high:
			rsize = self.getCount(root.right, low, high)
		if root.data >= low and root.data <= high:
			return rsize + lsize + 1
		else:
			return rsize + lsize


class Solution:

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

	def getCount(self, root, low, high):
		count = []
		self.Inorder(root, low, high, count)
		return len(count)


class Solution:

	def getcountnode(self, root, low, high, count):
		if root is None:
			return
		self.getcountnode(root.left, low, high, count)
		if low <= root.data <= high:
			count[0] += 1
		elif root.data > high:
			return
		self.getcountnode(root.right, low, high, count)

	def getCount(self, root, low, high):
		count = [0]
		self.getcountnode(root, low, high, count)
		return count[0]


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 getCount(self, root, low, high):
		arr = self.inorder(root, [])
		counter = 0
		for i in arr:
			if i <= high and i >= low:
				counter = counter + 1
		return counter


def getAns(root, low, high):
	global ans
	if root == None or high < low:
		return
	if root.data >= low and root.data <= high:
		ans += 1
		getAns(root.left, low, root.data - 1)
		getAns(root.right, root.data, high)
	elif root.data < low:
		getAns(root.right, low, high)
	elif root.data > high:
		getAns(root.left, low, high)

class Solution:

	def getCount(self, root, low, high):
		global ans
		ans = 0
		getAns(root, low, high)
		return ans


class Solution:

	def getCount(self, root, l, h):
		c = 0

		def inorder(root, l, h):
			nonlocal c
			if not root:
				return
			if l <= root.data <= h:
				c += 1
			inorder(root.left, l, h)
			inorder(root.right, l, h)
		inorder(root, l, h)
		return c


class Solution:

	def getCount(self, root, low, high):
		if root is None:
			return 0
		output = low <= root.data <= high
		output += self.getCount(root.left, low, high)
		output += self.getCount(root.right, low, high)
		return output


class Solution:

	def getCount(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 len(s)


def inorder(root):
	if not root:
		return []
	return inorder(root.left) + [root.data] + inorder(root.right)

class Solution:

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