Course contentsShow
← Computer Science
Lesson 514 of 2,87212. Binary Search TreesFree lesson

Range Query in BST

Find all values within a given range by pruning branches outside the range during traversal.

Range Query in BST

You'll learn how to efficiently find all values within a given range by exploiting the BST property to skip entire branches that can't contain valid results.

When you need to find all values between two boundaries (say, all numbers from 15 to 40) in a BST, you could traverse every node and check if it's in range. But that's wasteful! The BST property gives us something better: we can intelligently prune branches we know won't contain any valid values.

The Core Idea

Think of searching a phone book for all names starting with letters M through P. You wouldn't flip through A–L or Q–Z, right? Similarly, in a BST:

  • If the current node's value is less than your range minimum, ignore its entire left subtree (everything there is even smaller)
  • If the current node's value is greater than your range maximum, ignore its entire right subtree (everything there is even larger)
  • If the node is within range, collect it and explore both subtrees

How It Works

Start at the root and make decisions:

  1. Node < range minimum? Only explore the right subtree
  2. Node > range maximum? Only explore the left subtree
  3. Node in range? Add it to results, then explore both left and right subtrees

This approach transforms a potentially O(n) problem into something much faster—you only visit nodes that are relevant or lead to relevant values.

Example

Finding values between 15 and 40 in a BST with root 25:

  • 25 is in range → add it, check both sides
  • Go left to 10 → too small, only check its right subtree
  • Go right to 30 → in range, check both sides

You completely skip nodes under 10's left child!

Key Takeaway: Range queries in BSTs achieve efficiency by pruning entire subtrees that fall outside the target range, making them much faster than checking every single node.