Count BST nodes that lie in a given range | Practice Medium 0 attempts
GeeksforGeeks ↗

Count BST nodes that lie in a given range | Practice

Medium TreeBinary TreeDFS GeeksforGeeks

You're given a binary search tree and two bounds l and h. Count how many of the tree's nodes have a value falling within [l, h], inclusive on both ends.

Input Format
Implement countInRange(root, l, h). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
root = [10,5,50,1,null,40,100]
l = 5
h = 45
Output
3

Example 2

Input
root = [10]
l = 11
h = 20
Output
0
Constraints
  • 1 <= N <= 10^4
  • 1 <= l <= h <= 10^5
Test Cases (2)
Case 1
Args: [[10,5,50,1,null,40,100],5,45] Expected: 3
Case 2
Args: [[10],11,20] Expected: 0
Topics
TreeBinary TreeDFS

Pruned Iterative DFS

Count nodes in the range and skip subtrees whose values cannot fall inside it.

javascript
function countInRange(root, l, h) {
  const stack=root?[root]:[];let count=0;
  while(stack.length){const node=stack.pop();if(node.val>=l&&node.val<=h)count++;if(node.left&&node.val>=l)stack.push(node.left);if(node.right&&node.val<=h)stack.push(node.right);}
  return count;
}

Time: O(n) | Space: O(h) auxiliary space, excluding output

Saved in this browser only. Private to you.

JavaScript