Range Sum / Count in a BST

The problem

Given a BST and a range [lo, hi], compute either:

• the sum of all node values inside the range, or
• the count of nodes inside the range.

Both versions have the same algorithmic skeleton.

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Pattern: bounds pruning

The BST property gives us a powerful pruning rule. At any node:

• If node.val < lo, the entire left subtree has values smaller than lo — prune it entirely; recurse right only.
• If node.val > hi, the entire right subtree has values larger than hi — prune it; recurse left only.
• Otherwise the node is in range — contribute it, then recurse into both children (subtrees may contain partial matches on either side).

This is the same pattern as Validate BST's "bounds recursion", just used to prune rather than constrain. It generalizes to any subtree-aggregation query (min, max, average, count below k, etc.).

Range Sum

def range_sum(root: Node | None, lo: int, hi: int) -> int:
    """Sum of all values v in the BST with lo <= v <= hi."""
    if root is None:
        return 0
    if root.val < lo:
        return range_sum(root.right, lo, hi)              # whole left subtree pruned
    if root.val > hi:
        return range_sum(root.left,  lo, hi)              # whole right subtree pruned
    # lo <= root.val <= hi: this node contributes, both subtrees may have matches
    return root.val + range_sum(root.left, lo, hi) + range_sum(root.right, lo, hi)

Range Count

def range_count(root, lo, hi):
    """Number of values in [lo, hi]."""
    if root is None: return 0
    if root.val < lo: return range_count(root.right, lo, hi)
    if root.val > hi: return range_count(root.left,  lo, hi)
    return 1 + range_count(root.left, lo, hi) + range_count(root.right, lo, hi)

Trace

Tree:           10
              /    \
             5      15
            / \      \
           3   7     18

range_sum(root=10, lo=7, hi=15):
  10 in [7,15] -> contribute 10.
  recurse left (root=5):
    5 < 7 -> recurse RIGHT only (root=7):
      7 in [7,15] -> contribute 7. left/right None.
      = 7.
    = 7.
  recurse right (root=15):
    15 in [7,15] -> contribute 15.
    left=None.
    right (root=18):
      18 > 15 -> recurse LEFT only.  left=None -> 0.
      = 0.
    = 15.
  return 10 + 7 + 15 = 32.

Complexity

• Expected (balanced BST): O(log n + k) where k is the number of matches. Pruning makes us visit only the "boundary" path plus the in-range subtree.
• Worst case: O(n) on a degenerate tree (long chain). No tree can beat this asymptotically without augmentation.
• Space: O(h) recursion stack.

If you need many queries: augment with subtree sums

For a forest of repeated range queries on a static tree, augment each node with the sum (and/or count) of its subtree. Then a range query touches only O(log n) nodes on average, using the same pruning rule but combining cached subtree aggregates instead of recursing into "all-in-range" subtrees. This is the order-statistics tree pattern extended to interval queries.

Variations worth knowing

• Count nodes ≤ k: degenerate case of range count with lo = −∞. Equivalent to a "rank" query.
• Range min/max: same skeleton, change the combine to min / max. The "I'm strictly below lo" branch contributes nothing (identity element).
• Static range queries on an array: if the data isn't a tree at all, prefix sums give O(1) range sum after an O(n) preprocessing. Segment trees / Fenwick trees give O(log n) with updates.