Range Sum of BST
Easy · Trees · Tree · Depth-First Search · Binary Search Tree · Binary Tree
Problem
You are given the root of a binary search tree and two integers low and high. Return the sum of the values of all nodes whose value lies in the inclusive range [low, high].
In a binary search tree every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger. All values are different.
Examples
Input: root = [20,10,30,5,15,25,35], low = 12, high = 27 Output: 60
The values 15, 20 and 25 fall in the range: 15 + 20 + 25 = 60.
Input: root = [20,10,30], low = 1, high = 9 Output: 0
Every value is larger than 9.
Input: root = [10,5,15,3,7,None,18], low = 7, high = 15 Output: 32
The range is inclusive: 7 + 10 + 15 = 32.
Constraints
- The tree has between 1 and 2 · 10^4 nodes
- 1 <= Node.val <= 10^5, all values distinct
- 1 <= low <= high <= 10^5
Approaches
- Baseline: visit every node — time O(n), space O(h) for the stack
Follow-up
If the same tree gets many range queries, store at each node the sum of its subtree. A query then walks two root-to-leaf paths (one for low, one for high) and adds whole subtrees at once: O(h) per query instead of visiting every node in range.
Related problems
Start free on Cariara · Coding problems · System design studio
