List all BST nodes in the range a..b

You're in a Salesforce interview and the interviewer draws a binary search tree on the whiteboard. "Given two numbers, a and b," they say, "return all node values that fall within that range, sorted." This problem, also known as a "Range Query on a Binary Search Tree" on other platforms, tests two things at once: whether you understand BST properties, and whether you can exploit tree structure to avoid unnecessary work.

TL;DR

Perform a modified in-order traversal that prunes subtrees falling outside the range [a, b]. Before going left, check if a < node.data (otherwise, nothing in the left subtree can be in range). Before going right, check if b > node.data. If the current node's value is within [a, b], add it to the result. Because in-order traversal visits BST nodes in ascending order, the result is automatically sorted. Time complexity is O(n) worst case, O(log n + k) for balanced trees where k is the count of in-range nodes.

Why This Problem Matters

BST range queries show up frequently in interviews at companies like Amazon and Salesforce because they test whether you can move beyond brute-force tree traversal. Anyone can traverse every node and filter afterward. The differentiator is recognizing that the BST ordering property lets you skip entire subtrees, turning what could be an exhaustive scan into a targeted search.

Binary Search Trees: The Ordering Property

A binary search tree enforces a simple rule: for every node, all values in the left subtree are smaller, and all values in the right subtree are larger.

This ordering property is what makes BSTs useful for search operations. It also means that an in-order traversal (left, root, right) visits nodes in ascending order. That fact is central to solving this problem.

Understanding the Problem

Given: The root of a BST and two integers a and b Return: A list of all node values where a ≤ value ≤ b, sorted in ascending order Constraints: The range is inclusive on both ends. The tree has 1 to 1000 nodes. Both a and b are non-negative, and b ≥ a.

Here is the example from the problem:

listInRange(root, 1, 3) -> [2]
listInRange(root, 1, 4) -> [2, 4]
listInRange(root, 2, 4) -> [2, 4]

Edge Cases

1. Empty tree (null root): Return an empty list
2. Single node: Check if it falls in range
3. Range covers entire tree: Equivalent to a full in-order traversal
4. Range covers no nodes: Return an empty list
5. Range boundaries match node values: Both a and b are inclusive, so matching nodes should be included

Solution Approach

The naive approach would be to traverse every node, collect all values, filter by range, and sort. That works, but it ignores the BST property entirely.

A better approach leverages two insights:

1. In-order traversal produces sorted output on a BST, so we get the sorting requirement for free.
2. The BST property lets us prune subtrees that cannot contain in-range values.

The Pruning Logic

At each node, three decisions happen in sequence:

• Go left? Only if a < node.data. If a ≥ node.data, every value in the left subtree is smaller than a and cannot be in range.
• Add current? Only if node.data >= a && node.data <= b.
• Go right? Only if b > node.data. If b ≤ node.data, every value in the right subtree is larger than b and cannot be in range.

This sequence is just in-order traversal with guard conditions.

Walkthrough

Consider this tree with range [1, 4]:

The algorithm traces through the tree as follows:

The result is [1, 2, 3, 4], produced in sorted order without any explicit sorting step.

How Pruning Helps

With a different range, like [2, 4] on a larger tree, the pruning becomes more visible:

When the range is [2, 4], the algorithm never visits nodes 7, 8, or 10 because at node 5 the check b > node.data fails (4 is not greater than 5), so the entire right subtree is skipped.

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.LinkedList;
import java.util.List;

public class Solution {
  public List<Integer> listInRange(TreeNode root, int a, int b) {
    List<Integer> dataValues = new LinkedList<>();
    buildInOrder(root, dataValues, a, b);
    return dataValues;
  }

  private void buildInOrder(TreeNode node, List<Integer> dataValues, int a, int b) {
    if (node != null) {
      // Only traverse left if there could be in-range values there
      if (a < node.data) buildInOrder(node.left, dataValues, a, b);

      // Add current node if it's within range
      if (node.data >= a && node.data <= b) dataValues.add(node.data);

      // Only traverse right if there could be in-range values there
      if (b > node.data) buildInOrder(node.right, dataValues, a, b);
    }
  }
}

The structure is clean: the public method creates the result list and delegates to a private helper that does the recursive traversal. The helper modifies the list in place rather than returning sublists, avoiding the overhead of merging collections at each recursive call.

Complexity Analysis

Time Complexity: O(n)

In the worst case (a skewed tree or a range covering all nodes), every node is visited once. Each visit performs O(1) work: two comparisons for pruning, one range check, and possibly one list append.

For a balanced BST, the effective complexity is O(log n + k) where k is the number of in-range nodes. The O(log n) accounts for traversing from the root to the first in-range node, and O(k) covers visiting all k in-range nodes.

Space Complexity: O(n)

The result list holds up to n values if every node is in range. The recursion stack uses O(h) space where h is the tree height, which is O(log n) for a balanced tree and O(n) for a skewed one. Combined, worst case is O(n).

Common Pitfalls

1. Forgetting to prune: Traversing every node and filtering afterward works but misses the optimization that interviewers are looking for.

2. Using strict inequality for range checks: The range is inclusive on both ends. Using node.data > a instead of node.data >= a would exclude boundary values.

3. Pruning with the wrong condition: A common mistake is checking a <= node.data before going left. The correct check is a < node.data. If a == node.data, there is no reason to go left since all left children are strictly smaller than a.

4. Sorting the result: If you use in-order traversal, the result is already sorted. Adding an explicit sort is wasted work and signals to the interviewer that you do not fully understand BST traversal ordering.

Interview Tips

When solving this in an interview:

1. State the BST property explicitly: "In-order traversal gives us sorted order, so we get the sorted output for free."

2. Explain the pruning: "We skip the left subtree when a >= node.data because all left descendants are smaller. Same logic on the right with b."

3. Mention the complexity improvement: On balanced trees, pruning reduces visited nodes from O(n) to O(log n + k).

4. Consider follow-ups:

   • "What if we need this query repeatedly?" (Consider augmenting the BST with subtree sizes for an order-statistics tree.)
   • "What if the tree is not a BST?" (You would need a full traversal plus sorting.)
   • "Can you do this iteratively?" (Yes, using an explicit stack.)

Key Takeaways

• In-order traversal on a BST visits nodes in ascending order, which satisfies the sorted output requirement without a separate sort step.
• The BST property enables pruning: skip the left subtree when a >= node.data and the right subtree when b <= node.data, because those subtrees cannot contain in-range values.
• The helper method pattern (public method creates the list, private method fills it recursively) is a standard approach for tree problems that accumulate results.
• Worst-case complexity is O(n) time and O(n) space, but balanced BSTs benefit from pruning with O(log n + k) time where k is the number of results.
• Always clarify whether range boundaries are inclusive or exclusive. In this problem, both a and b are inclusive.

Solutions in Other Languages

Python

from typing import List
from TreeNode import TreeNode

class Solution:
    def list_in_range(self, root: TreeNode, a: int, b: int) -> List[int]:
        data_values = []
        self.build_in_order(root, data_values, a, b)
        return data_values

    def build_in_order(self, node: TreeNode, data_values: List[int], a: int, b: int):
        if node is not None:
            if a < node.data:
                self.build_in_order(node.left, data_values, a, b)
            if a <= node.data <= b:
                data_values.append(node.data)
            if b > node.data:
                self.build_in_order(node.right, data_values, a, b)

JavaScript

class Solution {
  listInRange(root, a, b) {
    const dataValues = [];
    this.buildInOrder(root, dataValues, a, b);
    return dataValues;
  }

  buildInOrder(node, dataValues, a, b) {
    if (node !== null) {
      if (a < node.data) this.buildInOrder(node.left, dataValues, a, b);
      if (node.data >= a && node.data <= b) dataValues.push(node.data);
      if (b > node.data) this.buildInOrder(node.right, dataValues, a, b);
    }
  }
}

TypeScript

class Solution {
  listInRange(root: TreeNode | null, a: number, b: number): number[] {
    const dataValues: number[] = [];
    this.buildInOrder(root, dataValues, a, b);
    return dataValues;
  }

  buildInOrder(node: TreeNode | null, dataValues: number[], a: number, b: number): void {
    if (node !== null) {
      if (a < node.data) this.buildInOrder(node.left, dataValues, a, b);
      if (node.data >= a && node.data <= b) dataValues.push(node.data);
      if (b > node.data) this.buildInOrder(node.right, dataValues, a, b);
    }
  }
}

C++

#include <vector>

class Solution {
public:
  std::vector<int> listInRange(TreeNode *root, int a, int b) {
    std::vector<int> dataValues;
    buildInOrder(root, dataValues, a, b);
    return dataValues;
  }

private:
  void buildInOrder(TreeNode *node, std::vector<int> &dataValues, int a, int b) {
    if (node != nullptr) {
      if (a < node->data) buildInOrder(node->left, dataValues, a, b);
      if (node->data >= a && node->data <= b) dataValues.push_back(node->data);
      if (b > node->data) buildInOrder(node->right, dataValues, a, b);
    }
  }
};

Scala

import scala.collection.mutable

class Solution {
  def listInRange(root: TreeNode, a: Int, b: Int): List[Int] = {
    val dataValues = mutable.ArrayBuffer[Int]()
    buildInOrder(root, dataValues, a, b)
    dataValues.toList
  }

  private def buildInOrder(
    node: TreeNode,
    dataValues: mutable.ArrayBuffer[Int],
    a: Int,
    b: Int
  ): Unit = {
    if (node != null) {
      if (a < node.data) buildInOrder(node.left, dataValues, a, b)
      if (node.data >= a && node.data <= b) dataValues.append(node.data)
      if (b > node.data) buildInOrder(node.right, dataValues, a, b)
    }
  }
}

Kotlin

class Solution {
    fun listInRange(root: TreeNode?, a: Int, b: Int): List<Int> {
        val dataValues = mutableListOf<Int>()
        buildInOrder(root, dataValues, a, b)
        return dataValues
    }

    private fun buildInOrder(node: TreeNode?, dataValues: MutableList<Int>, a: Int, b: Int) {
        if (node != null) {
            if (a < node.data) buildInOrder(node.left, dataValues, a, b)
            if (node.data >= a && node.data <= b) dataValues.add(node.data)
            if (b > node.data) buildInOrder(node.right, dataValues, a, b)
        }
    }
}

Swift

class Solution {
    func listInRange(_ root: TreeNode?, _ a: Int, _ b: Int) -> [Int] {
        var dataValues = [Int]()
        buildInOrder(root, &dataValues, a, b)
        return dataValues
    }

    private func buildInOrder(_ node: TreeNode?, _ dataValues: inout [Int], _ a: Int, _ b: Int) {
        if let node = node {
            if a < node.data { buildInOrder(node.left, &dataValues, a, b) }
            if node.data >= a && node.data <= b { dataValues.append(node.data) }
            if b > node.data { buildInOrder(node.right, &dataValues, a, b) }
        }
    }
}

Rust

impl Solution {
    pub fn list_in_range(&self, root: Option<Box<TreeNode>>, a: i32, b: i32) -> Vec<i32> {
        let mut data_values: Vec<i32> = Vec::new();
        Self::build_in_order(&root, &mut data_values, a, b);
        data_values
    }

    fn build_in_order(node: &Option<Box<TreeNode>>, data_values: &mut Vec<i32>, a: i32, b: i32) {
        if let Some(ref current) = *node {
            if a < current.data {
                Self::build_in_order(&current.left, data_values, a, b);
            }
            if current.data >= a && current.data <= b {
                data_values.push(current.data);
            }
            if b > current.data {
                Self::build_in_order(&current.right, data_values, a, b);
            }
        }
    }
}

Ruby

class Solution
  def list_in_range(root, a, b)
    data_values = []
    build_in_order(root, data_values, a, b)
    data_values
  end

  def build_in_order(node, data_values, a, b)
    unless node.nil?
      build_in_order(node.left, data_values, a, b) if a < node.data
      data_values << node.data if node.data >= a && node.data <= b
      build_in_order(node.right, data_values, a, b) if b > node.data
    end
  end
end

C#

using System.Collections.Generic;

public class Solution {
    public List<int> ListInRange(TreeNode? root, int a, int b) {
        var dataValues = new List<int>();
        BuildInOrder(root, dataValues, a, b);
        return dataValues;
    }

    private void BuildInOrder(TreeNode? node, List<int> dataValues, int a, int b) {
        if (node != null) {
            if (a < node.data) BuildInOrder(node.left, dataValues, a, b);
            if (node.data >= a && node.data <= b) dataValues.Add(node.data);
            if (b > node.data) BuildInOrder(node.right, dataValues, a, b);
        }
    }
}

Dart

class Solution {
  List<int> listInRange(TreeNode? root, int a, int b) {
    List<int> dataValues = [];
    buildInOrder(root, dataValues, a, b);
    return dataValues;
  }

  void buildInOrder(TreeNode? node, List<int> dataValues, int a, int b) {
    if (node != null) {
      if (a < node.data) buildInOrder(node.left, dataValues, a, b);
      if (node.data >= a && node.data <= b) dataValues.add(node.data);
      if (b > node.data) buildInOrder(node.right, dataValues, a, b);
    }
  }
}

PHP

class Solution {
    public function listInRange(?TreeNode $root, int $a, int $b): array {
        $dataValues = [];
        $this->buildInOrder($root, $dataValues, $a, $b);
        return $dataValues;
    }

    private function buildInOrder(?TreeNode $node, array &$dataValues, int $a, int $b): void {
        if ($node !== null) {
            if ($a < $node->data) $this->buildInOrder($node->left, $dataValues, $a, $b);
            if ($node->data >= $a && $node->data <= $b) $dataValues[] = $node->data;
            if ($b > $node->data) $this->buildInOrder($node->right, $dataValues, $a, $b);
        }
    }
}

Practice Makes Perfect

BST range queries build on the same in-order traversal pattern you'll use in many tree problems. Once you're comfortable here, try these related challenges:

• Find the kth smallest node in a BST (in-order traversal with early termination)
• Validate a binary search tree (in-order traversal with ordering checks)
• Find the lowest common ancestor in a BST (similar pruning logic)

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top tech companies. Consistent practice with BST problems builds the pattern recognition that makes interview day feel routine.