A shop keeps the prices of its items in a binary search tree with distinct values. Given an inclusive band lo..hi, return the sum of every price p with lo <= p <= hi. Return 0 if none qualify.
Examples
20
/ \
10 30
/ \ / \
5 15 25 40
Input: root = build_tree([20, 10, 30, 5, 15, 25, 40]), lo = 10, hi = 25
Output: 70 (10 + 15 + 20 + 25)
50
/ \
30 70
/ \ \
20 40 80
\
25
Input: root = build_tree([50, 30, 70, 20, 40, None, 80, None, 25]), lo = 26, hi = 60
Output: 120 (30 + 40 + 50)
Constraints
0 <= number of nodes <= 3000- All values are distinct integers,
lo <= hi - Do not descend into subtrees that lie entirely outside the band
Goals
- Add up only the values inside an inclusive range
- Skip subtrees that cannot contain any value in range