EasyNeetCode150TreeDepth-First SearchBinary Search TreeBinary Tree
Range Sum of BST
Sum of values in range [low, high].
Examples
Input
root = [10,5,15,3,7,null,18], low = 7, high = 15
Output
32
Nodes: 7 + 10 + 15 = 32.
Constraints
- •
Number of nodes in [1,2*10^4] - •
1 <= low < high <= 10^6 - •
1 <= Node.val <= 10^6
Approaches
Traverse all, filter range.
CodeT: O(n) | S: O(h) stack
Skip branches outside range.
CodeT: O(n) | S: O(h)
Same approach.
CodeT: O(n) | S: O(h)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| DFS | O(n) | O(h) stack | Traverse all, filter range. |
| DFS + Pruning | O(n) | O(h) | Skip branches outside range. |
| DFS Optimized | O(n) | O(h) | Same approach. |
DFS
T: O(n)S: O(h) stack
Traverse all, filter range.
DFS + Pruning
T: O(n)S: O(h)
Skip branches outside range.
DFS Optimized
T: O(n)S: O(h)
Same approach.
Common Mistakes
Not pruning unnecessary branches
Not handling null root
Off-by-one in range