Code › algorithm-study

LeetCode 938 - Range Sum of BST

Solving BST range sum through BFS, DFS, and prefix sums

algorithmleetcodebsttreebfsdfscpplearning

This is an Easy binary search tree problem. Given low and high, the task is to sum the node values that fall inside the range, so it looks like a simple tree traversal at first. In this post, I revisit a BFS-first solution through BST pruning and space complexity.

  • Problem link: 938. Range Sum of BST
  • Summary: Given the root of a binary search tree and two values low and high, return the sum of all node values between low and high.

For example, imagine this tree.

       6
      / \
     4   8
    / \ / \
   3  5 7  9
  /
 2

For the range [2, 5], the included values are 2, 3, 4, and 5, so the answer is 14. For [6, 6], only 6 is included, so the answer is 6.

A BST has a useful property. Values in the left subtree are smaller than the current node, and values in the right subtree are larger. That means I do not always need to visit every node. If the current value is smaller than low, the left side is even smaller and can be skipped. If the current value is larger than high, the right side is even larger and can be skipped.

Approach

My first instinct was BFS. Put the root into a queue, pop nodes one by one, and add the value if it is inside the range. It is easy to follow and easy to implement.

The simplest version visits every node. In the example tree, the traversal order is roughly this.

6 -> 4 -> 8 -> 3 -> 5 -> 7 -> 9 -> 2

That produces the correct answer, but it would also work for a normal binary tree. It does not use the fact that the left side is smaller and the right side is larger.

So the next step was pruning. If the current node value is greater than low, the left subtree may still contain values inside the range. If the current node value is less than high, the right subtree may also contain values inside the range.

The opposite cases can be skipped. If the current node is less than or equal to low, the left subtree is too small. If the current node is greater than or equal to high, the right subtree is too large. In other words, the pruning happens before pushing children into the queue.

#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        if (!root) return 0;

        int total = 0;
        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();

            if (low <= node->val && node->val <= high) {
                total += node->val;
            }

            if (node->left && node->val > low) {
                q.push(node->left);
            }

            if (node->right && node->val < high) {
                q.push(node->right);
            }
        }

        return total;
    }
};

The two important lines are these.

if (node->left && node->val > low) q.push(node->left);
if (node->right && node->val < high) q.push(node->right);

Whether I go left depends on whether the current value is greater than low. Whether I go right depends on whether the current value is less than high. I initially focused on the traversal style, but these two conditions are closer to the heart of the problem.

Troubleshooting

Space complexity with BFS

Even with pruning, the worst-case time complexity is still O(n). If the range is wide, or if the tree shape makes pruning ineffective, I may still visit most of the nodes. That part was not surprising.

The more interesting part was space complexity. BFS uses a queue, and that queue can hold many nodes from the same level at once. In a balanced binary tree, the number of nodes roughly doubles as we go down each level.

level 0: 1 node
level 1: 2 nodes
level 2: 4 nodes
level 3: 8 nodes

In a complete binary tree with 15 nodes, the last level alone has 8 nodes. That is close to n / 2. BFS processes the upper level while pushing nodes from the next level, so at some point the queue can hold many nodes near the widest level.

That is why BFS space complexity can grow to O(n) in a balanced tree. Even if the widest level is n / 2, Big O drops the constant factor, so it is still O(n).

Thinking about O(n) as real memory

In algorithm problems, O(n) space appears often enough that it is easy to move past it, but if n is 10 billion, the same notation requires a more concrete memory check. If the queue holds only node pointers for 10 billion nodes, and each pointer is 8 bytes, that alone is about 80 GB.

10,000,000,000 * 8 bytes
= 80,000,000,000 bytes
≈ 80 GB

That is only the simple pointer calculation. Real node objects, container overhead, and runtime memory can make the number larger. In actual systems, O(n) space is not just “linear.” I need to ask how large n can be and what each unit actually holds.

When many range queries arrive

If the tree is very large and the same function is called repeatedly, the question changes again. Suppose the tree is fixed, but range sum queries keep arriving with different low, high values. Traversing the tree on every request can become the wrong unit of work.

In that case, inorder traversal and prefix sums become useful. A BST produces sorted values through inorder traversal, so if the tree is fixed, I can build a sorted array once and precompute prefix sums over it.

values: [2, 3, 4, 5, 6, 7, 8, 9]
prefix: [0, 2, 5, 9, 14, 20, 27, 35, 44]

For a low, high query, I can find the first position greater than or equal to low and the first position greater than high using binary search. Then the answer is the difference between two prefix values.

left = lower_bound(values, low)
right = upper_bound(values, high)
answer = prefix[right] - prefix[left]

This moves the repeated traversal cost into preprocessing. The preprocessing takes O(n) time and O(n) extra space, but each query becomes O(log n). This is not really an improvement to the single LeetCode call. It is a system-level optimization for repeated range queries over fixed data.

That assumption matters. The sorted array and prefix sum approach works cleanly when the input data is fixed. If values are inserted or deleted, the sorted array has to stay ordered, and the prefix sums have to be updated. When the data keeps changing, that cost can become the real problem.

At that point, the discussion starts to look less like a LeetCode traversal problem and more like a database indexing problem. For mutable range queries, a B+ tree becomes a better structure to think about. A B+ tree stores many keys per page, keeps the actual values ordered at the leaf level, and links the leaves so range scans can move across them. A query does not need to keep a wide BFS queue or a deep recursive stack in memory. It follows the path to the relevant leaf pages and scans the range from there, which makes the working set and disk access pattern easier to control. If the query needs a range sum rather than just the rows, the tree also needs aggregate metadata such as partial sums on pages or subtrees.

That deserves a separate database-series post. For this LeetCode note, the useful boundary is simpler: fixed data can use a flattened sorted array plus prefix sums, while changing data pushes the design toward an index structure such as a B+ tree.

Complexity analysis

1. BFS with pruning

  • Time complexity: O(n)

    • Pruning can skip some subtrees, but in the worst case the range is wide or the tree shape requires visiting most nodes.

  • Space complexity: O(width), worst case O(n)

    • BFS stores nodes from the same level in the queue. In a balanced tree, the widest level can contain close to half of all nodes, so the worst case becomes O(n).

2. DFS with pruning

  • Time complexity: O(n)

    • Like BFS, DFS can still visit every node in the worst case, but it uses the BST range to skip unnecessary subtrees.

  • Space complexity: O(h)

    • DFS keeps the current path on the call stack. In a balanced tree, h = log n, so the extra stack space is O(log n). In a skewed tree, the shape becomes close to a linked list, so the height can grow to O(n). In that case, BST search itself also becomes O(n), and with a large enough input the linear call stack can cause a stack overflow.

For the single LeetCode call, DFS with pruning is the natural final answer. If the tree is balanced, DFS does not need to hold a wide level in memory. It only carries the current path. But the input tree is already given, so the solution is not supposed to rebuild it as an AVL tree or a Red-Black tree. In this problem, the right thing is to account for the skewed-tree case where DFS can still use an O(n) call stack.

If I were designing and maintaining the BST as a real data structure, that would be a different decision. Then a self-balancing BST such as an AVL tree or a Red-Black tree would be a better fit because it keeps the height around O(log n) and prevents the search path from degrading into a linked list. The total storage still grows with n nodes, but the height stays controlled.

3. System view: fixed data + prefix sums

  • Preprocessing: O(n)

    • Run an inorder traversal, build a sorted array, and compute the prefix sum array.

  • Space complexity: O(n)

    • The sorted values and prefix sums have to be stored separately.

  • Query complexity: O(log n)

    • Use binary search to find the positions for low and high, then subtract two prefix values. This is simple and fast in a system where the input data is fixed and range-sum queries repeat. If values change frequently, maintaining the sorted array and prefix sums becomes expensive.

4. System view: frequently changing data + B+ tree

Prefix sums are fast, but they require a separate sorted value array and a prefix sum array. That works well when the data is fixed. If values are inserted or deleted, both the ordering and the accumulated sums have to be maintained.

A B+ tree is a different fit for that situation. Instead of flattening the whole dataset into arrays for every range-sum strategy, it organizes data into page-sized nodes and ordered leaf pages. The total storage does not disappear, but a single range query mostly works with the path from root to leaf and the leaf pages that cover the requested range. Compared with keeping a full prefix sum array in memory, the working set for one query can be much smaller and the disk access pattern is easier to reason about.

A B+ tree alone does not magically answer range sums, though. If the system needs sums without scanning all matching rows, it still needs aggregate metadata such as partial sums on pages or subtrees. That belongs more to database index design than to this LeetCode solution, so I am only leaving the pointer here.

Optimized code

Based on that reasoning, I would settle on DFS with BST pruning.

class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        if (!root) return 0;

        if (root->val < low) {
            return rangeSumBST(root->right, low, high);
        }

        if (root->val > high) {
            return rangeSumBST(root->left, low, high);
        }

        return root->val
            + rangeSumBST(root->left, low, high)
            + rangeSumBST(root->right, low, high);
    }
};

If the current value is smaller than low, the left subtree is too small and I only need the right side. If the current value is larger than high, the right subtree is too large and I only need the left side. When the current node is inside the range, I include it and check both sides.

Summary and reflection

After getting a correct BFS solution, reviewing it through space complexity made DFS with pruning easier to justify for the single LeetCode call. BFS and DFS both produce the correct answer, but BFS may keep many nodes from the same level in a queue, while DFS keeps the current path on the call stack. That difference becomes much more visible as the input grows.

In a BST, the rule that the left side is smaller and the right side is larger becomes the pruning condition. If the current value is below low, the left subtree can be skipped. If the current value is above high, the right subtree can be skipped. That makes this problem less about summing values mechanically and more about recalculating time and space cost from the structure of the data.

The optimizations in this note sit at different levels. For the algorithm problem, the answer is DFS with pruning. If I can design the underlying tree itself, a self-balancing BST such as an AVL tree or a Red-Black tree is the way to avoid skew. Prefix sums and B+ trees belong to the system-design version of the question, where range-sum queries repeat and the storage model starts to matter. At that point, the real question is how the data is stored, how often it changes, and what kind of repeated queries the system has to answer.