Range Sum of a BST

Range Sum of a BST looks like a plain tree-traversal problem, but it is really a lesson in pruning. The binary-search-tree ordering lets you throw away entire subtrees without ever looking inside them.

The slow way first

The obvious idea: do an ordinary traversal of the whole tree, and for each node add its value to a running total if it falls inside [lo, hi]. That is correct, and it is O(n) because it touches every node.

The question to ask: do I really have to visit every node? In a BST, no. If a node value is already below lo, then everything in its left subtree is smaller still — none of it can be in range. The same logic mirrors on the high side. We can skip those branches entirely.

The idea: let the BST order prune branches

At each node, compare its value against the range and decide which way to recurse:

• If node.val < lo, the node and its whole left subtree are too small — recurse right only.
• If node.val > hi, the node and its whole right subtree are too big — recurse left only.
• Otherwise the node is in range — add it and recurse both ways.

The key insight: the BST property turns a comparison into permission to discard a whole subtree — that is what makes this faster than a blind traversal on skewed ranges.

Walk through it

Step through the animation. We start at root 10 (in range, add it). Going left we hit 5, which is below lo = 7, so we prune its left child 3 entirely and only go right to 7 (in range, add). Back up, 15 is in range (add), and its child 18 is above hi = 15, so we prune right. The running sum ends at 10 + 7 + 15 = 32, and node 3 is never examined.

Pseudocode

function range_sum(node, lo, hi):
    if node is None:
        return 0
    if node.val < lo:                 # too small: skip left subtree
        return range_sum(node.right, lo, hi)
    if node.val > hi:                 # too big: skip right subtree
        return range_sum(node.left, lo, hi)
    # in range: count this node and check both sides
    return node.val
         + range_sum(node.left, lo, hi)
         + range_sum(node.right, lo, hi)

The Python solution

def range_sum_bst(node, lo, hi):
    if node is None:
        return 0
    if node.val < lo:
        return range_sum_bst(node.right, lo, hi)
    if node.val > hi:
        return range_sum_bst(node.left, lo, hi)
    return (node.val
            + range_sum_bst(node.left, lo, hi)
            + range_sum_bst(node.right, lo, hi))

• The first if is the base case: a None node contributes 0 and stops the recursion.
• node.val < lo means everything to the left is smaller too, so we skip left and recurse right only.
• node.val > hi means everything to the right is larger too, so we skip right and recurse left only.
• The final return is the in-range case: count node.val itself and add the sums from both subtrees.
• Because each recursive call returns a number, the total bubbles up naturally without a shared accumulator.

Complexity

Worst case is still O(n) (a range that covers everything), but pruning skips whole subtrees in practice, and the recursion depth is O(h) — the height of the tree — for the call stack.

When this pattern shows up

Practice