Community Problem
Range Sum of BST
Difficulty: Easy
Sum every BST value within an inclusive range, pruning subtrees that fall outside.
Range Sum of BST
Sum every BST value within an inclusive range, pruning subtrees that fall outside.
By @ninarossi
February 16, 2026
·
Updated May 18, 2026
506 views
16
Rate
I see this one trip up engineers who treat the BST like a generic binary tree. The naive recursion that visits every node is correct, but it throws away the entire reason BSTs exist (ordered traversal). The interview signal here is whether you can spot the pruning opportunity: when the current node's value is below low, the entire LEFT subtree is guaranteed to also be below low, and you skip it.
Range Sum of BST
Given the root of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].
Examples
Example 1:
- Input:
root = [10, 5, 15, 3, 7, null, 18],low = 7,high = 15 - Output:
32 - Explanation: Nodes in
[7, 15]are7,10,15, summing to32.
Example 2:
- Input:
root = [10, 5, 15, 3, 7, 13, 18, 1, null, 6],low = 6,high = 10 - Output:
23 - Explanation: Nodes in
[6, 10]are6,7,10, summing to23.
Example 3:
- Input:
root = [4, 2, 6, 1, 3, 5, 7],low = 4,high = 4 - Output:
4 - Explanation: Only the root falls in the singleton range.
Example 4:
- Input:
root = [4, 2, 6, 1, 3, 5, 7],low = 8,high = 10 - Output:
0 - Explanation: No node falls in the range.
Constraints
- The number of nodes in the tree is in the range
[1, 2 * 10^4]. 1 <= Node.val <= 10^5.1 <= low <= high <= 10^5.- All
Node.valare unique.
Follow-up
What is the worst-case complexity of the pruned solution on a perfectly balanced BST whose range covers all values? On a degenerate (linked-list-shaped) BST?
Solution
Hints
Solution Walkthrough
Approach: BST-Pruned DFS (O(n) worst case, O(log n + k) typical)
The trick is treating the BST like a BST. A generic tree DFS visits every node and runs in O(n). A BST-aware DFS lets us skip entire subtrees by comparing the node's value to the range.
Algorithm
- If
rootisnull, return0. - If
root.val < low: every value in the left subtree is strictly smaller thanroot.valand therefore also< low. Skip it. Recurse only into the right subtree. - If
root.val > high: symmetric. Recurse only into the left subtree. - Otherwise
low <= root.val <= high. Addroot.valand recurse into BOTH subtrees, because each of them may contain in-range values.
Why It Works
The BST invariant says that for every node, all left descendants are < the node and all right descendants are > the node. So when root.val < low, the entire left subtree is also < low and contributes nothing to the sum. Pruning is sound; we skip exactly the nodes that cannot contribute.
Complexity
Sample BST
10
/ \
5 15
/ \ \
3 7 18Metric Value
Time O(min(n, k + log n)) on a balanced BST where k is the count of in-range nodes
Time O(n) worst case on a degenerate BST or a range that covers everything
Space O(h) recursion stack; O(log n) balanced, O(n) degeneratePitfalls
- Forgetting BST pruning. The naive
if low <= root.val <= high: ans += root.val; recurse(left); recurse(right)is correct but does no better than O(n). The interview point is the prune. - Strict vs inclusive comparisons. The range is inclusive on both sides. A bug like
root.val <= low(instead of<) would skip validlowmatches in the right subtree. - Iterative version. An iterative stack-based variant is fine, but make sure you push only the children that survive the prune; otherwise the wins disappear.
Solution Code