Range Sum of BST: Pruned DFS

You are given the root of a binary search tree and two integers low and high. Return the sum of all node values that fall within the inclusive range [low, high].

This is LeetCode 938: Range Sum of BST, and it is a great problem for understanding how to exploit the BST property to skip entire subtrees during traversal.

Why this is more than a simple traversal

You could solve this by visiting every node in the tree, checking if the value is in range, and adding it to a running sum. That works, but it ignores the most useful property of the data structure you are working with.

In a BST, every node in the left subtree has a smaller value than the current node, and every node in the right subtree has a larger value. That ordering gives you free information about which branches to skip.

If the current node's value is less than low, every node in its left subtree is also less than low. You do not need to visit any of them. If the current node's value is greater than high, every node in its right subtree is also greater than high. You can prune that entire branch too.

This is the same idea behind binary search: use the structure of sorted data to avoid looking at things you already know are irrelevant.

The approach: DFS with BST pruning

The algorithm is a recursive DFS that makes pruning decisions at each node:

1. If the node is null, return 0 (base case).
2. If node.val is less than low, skip the left subtree entirely and only recurse right.
3. If node.val is greater than high, skip the right subtree entirely and only recurse left.
4. If node.val is within [low, high], add it to the sum and recurse into both subtrees.

Here is the clean Python solution:

def range_sum_bst(root, low, high):
    if root is None:
        return 0
    if root.val < low:
        return range_sum_bst(root.right, low, high)
    if root.val > high:
        return range_sum_bst(root.left, low, high)
    return (root.val
            + range_sum_bst(root.left, low, high)
            + range_sum_bst(root.right, low, high))

Each recursive call either prunes a subtree or includes the current node and explores both children. The BST property ensures the pruning is always correct.

Step-by-step walkthrough

Let's trace through the example tree [10, 5, 15, 3, 7, null, 18] with low = 7 and high = 15.

Notice how node 3 and node 18 were never even considered for the sum. The BST property told us they could not possibly be in range, so we pruned those branches entirely. On larger trees, this pruning can save a significant amount of work.

Complexity analysis

Time: In the worst case (every node is in range), you visit all n nodes, giving O(n). In practice, pruning reduces this. If the range is narrow, you visit roughly O(h + k) nodes where h is the tree height and k is the number of nodes in range.

Space: The recursion depth is bounded by the height of the tree. For a balanced BST, that is O(log n). For a completely skewed tree, it could be O(n).

The building blocks

This problem uses two fundamental ideas:

BST property exploitation. The ordering invariant of a BST (left subtree values are smaller, right subtree values are larger) lets you make decisions about entire subtrees without visiting them. This is the same property that makes BST search O(log n) instead of O(n). Any time you see a BST in a problem, ask yourself: can I use the ordering to skip work?

DFS traversal. The recursive structure follows the standard DFS template: handle the base case, process the current node, and recurse into children. The only twist here is that you conditionally recurse into one or both children based on the pruning logic. This conditional recursion pattern appears in many tree problems where you want to avoid exploring irrelevant branches.

Edge cases

• Empty tree (root is None): return 0. The base case handles this directly.
• Single node: if the node's value is in [low, high], return that value. Otherwise return 0.
• All nodes in range: no pruning happens, and you visit every node. The algorithm still works correctly, it just does not get the pruning speedup.
• No nodes in range: pruning cuts off early at every level. The function returns 0 after visiting only O(h) nodes along the pruning path.
• low equals high: you are looking for a single value. The pruning narrows the search to a single root-to-leaf path, making this essentially a BST lookup.
• Skewed tree (all nodes in a line): the call stack goes O(n) deep, but pruning still works. If the range is near the bottom of the chain, you skip the top portion. If it is near the top, you skip the bottom.

From understanding to recall

You just traced through how BST pruning lets you skip entire subtrees during a range sum. Right now, you can see exactly why checking node.val < low means "nothing to the left matters" and why node.val > high means "nothing to the right matters."

But when you face a BST problem in an interview next month, will you instinctively reach for the pruning optimization? Or will you write a brute-force traversal and miss the O(h + k) opportunity?

The pattern here is simple: if the current value is out of range on one side, only recurse into the other side. That is three lines of logic. But remembering to apply it under pressure requires practice. Spaced repetition helps you bridge the gap between understanding a technique today and recalling it automatically when you need it.

Related posts

• Validate Binary Search Tree - Uses BST range constraints in a different way, passing valid bounds down the recursion to verify the tree structure
• Binary Search Tree Iterator - Another problem where exploiting the BST ordering property is the key insight
• Kth Smallest Element in a BST - Uses inorder traversal of a BST to find elements in sorted order, another classic BST property exploitation