Range Query in BST

Related data structure:

• Binary Search Tree (BST)

AlgorithmTreeBinary_Search_TreeBinary_Tree

---

A range query is defined by two values $k_1$ and $k_2$. We are to find all keys $k$ stored in BST $T$ that $k_1\le k\le k_2$. E.g. Find all cars on eBay priced between 10k and 15k.

• Input
  • rangeQuery(lowerBoundK1, upperBoundK2)
• Output
  • print all keys from lower bound (k1) to upper bound (k2) inclusive.

Example

• Input
  • rangeQuery(3, 7), given a BST with keys 2,3,5,7,8,9
• Output
  • 3, 5, 7

Implementation

The range query method traverses the BST in an in-order fashion.

1. Check if the current root is null, if yes then the method returns, as there are no more nodes to process
2. If the value of the current root is greater than the lower bound, we process to find the suitable lower bound in the tree. The method recursively calls itself on the left subtree until find a node that is less than the lower bound
3. Then we check if the previous node is in range of lower to upper, if yes, print the node
4. Now we move onto the right subtree, and recursively search and print nodes that fall in range

public void rangeQuery(int lower, int upper) {  
    rangeQueryHelper(root, lower, upper);  
}  
  
private void rangeQueryHelper(Node root, int lower, int upper) {  
    if (root == null)  
        return ;  
        
    if (lower < root.data)  
        rangeQueryHelper(root.left, lower, upper);  
        
    if (lower <= root.data && root.data <= upper)  
        System.out.println(root.data);  
        
    if (upper > root.data)  
        rangeQueryHelper(root.right, lower, upper);  
}

Complexity analysis

Time complexity

In the worst-case, the algorithm may need to travers the entire tree (the range to query is the range that spans the entire tree), resulting visiting each node of the tree exactly once. The time complexity of traversing the entire tree is $O(n)$ where $n$ is the number of nodes in the BST. In an average case, the algorithm traverse the path from the root to the lower bound in the range, and then visit all the nodes within the range. The time complexity of traversing the path is $O(\log n)$, and the time complexity of visiting the nodes within the range is $O(k)$ where $k$ is the size of the range. Therefore, the overall time complexity is $O(k+\log n)$.

---

Back to parent page: Binary Search Tree (BST)