509. Range Key Total
A bakery records its daily order sizes in a binary search tree: keys in a node's left subtree are smaller, keys in its right subtree are larger, and every key is distinct. The manager wants the combined size of all orders that fall inside a band.
Given root and two integers low and high, return the sum of the keys of all nodes whose key is at least low and at most high; both ends are inclusive. If no key lies in the band, or the tree is empty, the answer is 0. The result is guaranteed to fit in a 32-bit signed integer.
Example 1
- Input:
- root = [15,8,22,4,11,18,30], low = 10, high = 20
- Output:
- 44
- Explanation:
The keys 11, 15 and 18 lie between 10 and 20, and 11 + 15 + 18 = 44.
Example 2
- Input:
- root = [15,8,22,4,11,18,30], low = 23, high = 29
- Output:
- 0
- Explanation:
No key lies between 23 and 29, so the total is 0.
Constraints
0 ≤ number of nodes ≤ 104
0 ≤ Node.val ≤ 105
0 ≤ low ≤ high ≤ 105
The tree is a valid binary search tree with distinct keys.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(h)