Code Logo

BST Range Query

Published at25 Jul 2026
Created by
Binary Search Tree Easy 1 views
Like0

Given an array representing a Binary Search Tree (BST) in level-order and two integers low and high, return an array of all values in the BST that fall within the inclusive range [low, high].

For example, in the BST [5, 3, 8, 1, 4, 7, 9] with range [3, 7], the result is [3, 4, 5, 7] (sorted). If no values fall in the range, return []. An empty tree returns [].

Range queries are a common BST operation used in database indexing, geographic information systems, and interval searching. The BST property allows efficient range queries by pruning subtrees that cannot contain values in the target range. If the current node is less than low, the entire left subtree can be skipped; if greater than high, the right subtree can be skipped.

For the array-based representation, perform a traversal starting at index 0. If the current node's value is within [low, high], add it to the result. Recursively traverse both children unless the current value is outside the range, in which case you can prune one side.

Edge cases include an empty tree (return []), a range where no values match (return []), low == high (return values exactly equal to that), and very wide ranges that include all nodes (return the full tree in sorted order).

Example Input & Output

Example 1
Input
[1,2,3,4,5],2,4
Output
3
Explanation

Values 2,3,4 are in range [2,4]

Example 2
Input
[10,20,30,40,50],25,35
Output
1
Explanation

Only 30 is in range

Example 3
Input
[],1,5
Output
0
Explanation

Empty

Example 4
Input
[1,2,3],0,10
Output
3
Explanation

All in range

Example 5
Input
[5,10,15],20,30
Output
0
Explanation

None in range

Algorithm Flow

Recommendation Algorithm Flow for BST Range Query

Solution Approach

Traverse the BST and collect values within the range, pruning subtrees that cannot contain valid values.

function solution(arr, low, high) {
  var r = [];
  function traverse(i) {
    if (i >= arr.length) return;
    if (arr[i] > low) traverse(2 * i + 1);
    if (arr[i] >= low && arr[i] <= high) r.push(arr[i]);
    if (arr[i] < high) traverse(2 * i + 2);
  }
  traverse(0);
  return r;
}

Define a recursive function that visits nodes. If the current value is greater than low, traverse the left subtree (it may contain valid values). If the current value is within range, add it. If the current value is less than high, traverse the right subtree. Start at index 0.

Time complexity is O(n) worst case (when all nodes are in range). Space complexity is O(n) for the result and recursion stack.

Best Answers

java
class Solution {
    public int solution(int[] nums, int l, int h) {
        int c=0;for(int n:nums){if(n>=l&&n<=h)c++;}return c;
    }
}