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:
- Node < range minimum? Only explore the right subtree
- Node > range maximum? Only explore the left subtree
- 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.