Count Nodes in a Range

Count Nodes in a Range takes a binary search tree and a range [lo, hi], and asks how many node values fall inside it. The naive answer visits every node — but a BST lets us be much smarter by pruning whole subtrees we can prove are out of range.

The slow way first

The obvious approach: walk the entire tree, and for every node check if lo <= val <= hi, adding 1 each time it is. That works and is O(n) — but it ignores the one thing that makes a BST special: its ordering. We end up visiting nodes we could have proven irrelevant without ever looking at them.

The question to ask: can I skip a subtree entirely? In a BST, yes — and that is the whole trick.

The idea: prune using BST order

At each node, compare its value to the range:

• If node.val < lo, the node is too small, and so is everything in its left subtree. Recurse right only.
• If node.val > hi, the node is too big, and so is everything in its right subtree. Recurse left only.
• Otherwise the node is in range: count it, and recurse both sides since either may hold more matches.

Each comparison can lop off an entire branch, so we touch far fewer nodes than a blind full traversal.

Walk through it

Step through the animation. We start at root 10 (in range, count 1), go right into 5 which is below lo so its left child 3 is pruned, reach 7 (in range, count 2), then handle the right side: 15 and 13 are both in range (count 3, then 4), while 18 is above hi and is skipped. The final count is 4.

Pseudocode

count_range(node, lo, hi):
    if node is empty: return 0
    if lo <= node.val <= hi:
        # in range: count this node and recurse both sides
        return 1 + count_range(node.left)  + count_range(node.right)
    if node.val < lo:
        return count_range(node.right)      # left subtree all too small
    return count_range(node.left)           # right subtree all too big

The Python solution

def count_range(node, lo, hi):
    if node is None:
        return 0
    if lo <= node.val <= hi:
        return 1 + count_range(node.left, lo, hi) \
                 + count_range(node.right, lo, hi)
    if node.val < lo:
        return count_range(node.right, lo, hi)
    return count_range(node.left, lo, hi)

• The base case node is None returns 0 — an empty branch contributes nothing.
• lo <= node.val <= hi is the in-range test; when true we add 1 and recurse into both children.
• node.val < lo means this node and its whole left subtree are below the range, so we recurse right only.
• The final line handles node.val > hi: the node and its right subtree are above the range, so we recurse left only.
• The pruning lives in those last two branches — each one drops an entire subtree from the search.

Complexity

Worst case is still O(n) when the whole tree is in range, but pruning routinely skips large branches in practice. The extra space is O(h) for the recursion stack, where h is the tree height.

When this pattern shows up

Practice