Price Band Total
EasyTrees
Problem
An online shop keeps product prices (distinct integers) in a binary search tree. For a promotion it needs the total of every price inside an inclusive band [lo, hi].
Return the sum of all node values v with lo ≤ v ≤ hi.
Example 1
- Input:
- root = [10, 5, 15, 3, 7, null, 18], lo = 7, hi = 15
- Output:
- 32
7 + 10 + 15 = 32.
Example 2
- Input:
- root = [10, 5, 15, 3, 7, 13, 18, 1, null, 6], lo = 6, hi = 10
- Output:
- 23
6 + 7 + 10 = 23.
Constraints
- 0 ≤ number of nodes ≤ 2·10^4
- 1 ≤ node.val ≤ 10^5
- 1 ≤ lo ≤ hi ≤ 10^5
- All values are distinct.
Hint
Show the first hint
If a node's value is below lo, which of its subtrees can still contain prices in the band?
Walkthrough
How to approach it
01Clarify before coding
- Is the band inclusive? Yes, both lo and hi count.
- Can the tree be empty? Yes: the total is 0.
- Can the sum overflow? At most 2·10^4 values of 10^5 → 2·10^9, which fits a 64-bit integer and a JavaScript number.
02Brute force
Visit every node and add the ones in range.
Cost: O(n) time always, even when the band covers only a handful of nodes deep in one corner.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.