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

Given a BST and a range [l, h], count all nodes with values in the range [l, h] inclusive.

Example: BST = [10,5,50,1,null,40,100], l=5, h=45 → Output: 3 (nodes 5, 10, 40)

Sample Input
—
Sample Output
—
Constraints
  • 1 <= N <= 10^4
  • 1 <= l <= h <= 10^5
Topics
TreeBinary TreeDFS

Pruned Inorder DFS

function countInRange(root, l, h) {
  if (!root) return 0;
  if (root.val < l) return countInRange(root.right, l, h);
  if (root.val > h) return countInRange(root.left, l, h);
  return 1 + countInRange(root.left, l, h) + countInRange(root.right, l, h);
}

Time: O(h + k) where k = nodes in range | Space: O(h)

Saved in this browser only. Private to you.

JavaScript