Range Sum of BST
Last Updated: March 29, 2026
Understanding the Problem
We have a binary search tree (BST) and a range defined by low and high. We need to find every node whose value falls within that range (inclusive on both ends) and return their sum.
The critical detail here is that this is a BST, not just any binary tree. In a BST, for every node, all values in its left subtree are smaller and all values in its right subtree are larger. This ordering property gives us the ability to prune entire subtrees that can't possibly contain values in our range. If a node's value is less than low, there's no point exploring its left subtree since everything there is even smaller. Similarly, if a node's value is greater than high, its right subtree is all larger values we don't care about.
Key Constraints:
Number of nodes up to 2 * 10^4→ Even O(n) traversal of the entire tree is perfectly fine. We're not under pressure to find a sub-linear solution.1 <= Node.val <= 10^5→ All positive values, so no concerns about integer overflow when summing (max possible sum is 2 10^4 10^5 = 2 * 10^9, which fits in a 32-bit signed integer but is close to the limit).1 <= low <= high <= 10^5→ The range is always valid (low never exceeds high), so no need for input validation.- All
Node.valare unique → Each node contributes at most once to the sum. No duplicate counting issues.
Approach 1: DFS (Visit All Nodes)
Intuition
The most straightforward approach is to traverse the entire tree using DFS and, at each node, check whether its value falls within [low, high]. If it does, add it to our running sum. This completely ignores the BST property and treats the tree as a generic binary tree.
It's simple, it's correct, and it's easy to code under pressure. For small trees, this is perfectly fine.
Algorithm
- Start a DFS traversal from the root.
- At each node, check if its value is between
lowandhigh(inclusive). - If yes, add the node's value to the sum.
- Recurse on both left and right children regardless of the node's value.
- Return the total sum.
Example Walkthrough
Code
- Time Complexity: O(n). We visit every single node in the tree exactly once, regardless of whether it's in range or not.
- Space Complexity: O(h) where h is the height of the tree. The recursion stack goes as deep as the tree height. O(log n) for a balanced BST, O(n) for a skewed tree.
This approach works correctly but visits every node, even those in subtrees that can't possibly contain in-range values. What if we used the BST ordering property to skip entire subtrees?
Approach 2: DFS with BST Pruning (Optimal)
Intuition
The BST property gives us a powerful shortcut. For any node:
- If
node.val < low, then node.val and everything in its left subtree is below our range. We only need to check the right subtree. - If
node.val > high, then node.val and everything in its right subtree is above our range. We only need to check the left subtree. - If
low <= node.val <= high, the node is in range. We add its value and need to check both subtrees since the left subtree might have values >= low and the right subtree might have values <= high.
This pruning means we skip entire branches of the tree that can't contribute to the sum. On a balanced BST with a narrow range, this can reduce the work dramatically.
The BST invariant guarantees that for any node, every value in its left subtree is strictly less than the node's value, and every value in its right subtree is strictly greater. So when a node's value falls below low, we know with certainty that its left subtree is entirely below low too. There's nothing to find there. The same logic applies in reverse for nodes above high.
This is essentially a targeted search that narrows itself using the same ordering property that makes binary search work on sorted arrays. Instead of blindly visiting every node, we follow only the paths that could lead to in-range values.
Algorithm
- If the current node is null, return 0.
- If the node's value is less than
low, recurse only on the right child (left subtree is all too small). - If the node's value is greater than
high, recurse only on the left child (right subtree is all too large). - Otherwise, add the node's value and recurse on both children.
Example Walkthrough
Code
- Time Complexity: O(n) in the worst case. If every node falls within [low, high], we visit all n nodes. In practice, pruning often reduces this to O(log n + k) where k is the number of in-range nodes.
- Space Complexity: O(h) where h is the height of the tree. The recursion stack depth equals the tree height. O(log n) for a balanced BST, O(n) for a completely skewed tree.
The recursive approach is clean and concise. But what if we wanted to avoid recursion entirely, perhaps to guard against stack overflow on very deep trees?
Approach 3: Iterative BFS with Pruning
Intuition
The same pruning logic works iteratively with a queue (BFS). We process nodes from the queue, add the value if it's in range, and only enqueue children whose subtrees could contain in-range values.
Some interviewers prefer seeing an iterative solution because it avoids the risk of stack overflow on very deep trees, even though for the given constraints (up to 2 * 10^4 nodes) recursion is perfectly safe.
Algorithm
- Initialize a queue with the root node and a sum variable set to 0.
- While the queue is not empty, dequeue a node.
- If the node's value is in range, add it to the sum.
- If the node's value is greater than
low, enqueue the left child (it might have in-range values). - If the node's value is less than
high, enqueue the right child (it might have in-range values). - Return the sum.
Example Walkthrough
Code
- Time Complexity: O(n) in the worst case. Same as the recursive approach. We visit each relevant node once. Pruning reduces the constant factor but doesn't change the worst-case bound.
- Space Complexity: O(n). The queue can hold up to O(n) nodes in the worst case. This is worse than the recursive approach's O(h) for tall narrow trees, but avoids stack overflow on extremely deep skewed trees.