A charity keeps its distinct donation amounts in a binary search tree. Starting from an empty tree, the amounts are inserted one at a time in the order given (standard BST insertion: go left when the new amount is smaller than the current node, otherwise go right). Given an inclusive range [lo, hi], report the sum of every stored amount x with lo <= x <= hi.
Line 1: an integer n, the number of donations.
Line 2: n space-separated distinct integers, the amounts in insertion order.
Line 3: two space-separated integers lo and hi with lo <= hi.
A single integer: the sum of all stored amounts within [lo, hi] (0 if none qualify).
Example 1
Input
6 40 20 60 10 30 50 25 55
Expected
120
Explanation
Stored amounts in [25, 55] are 30, 40, and 50, which sum to 120.
Example 2
Input
4 5 2 8 6 9 20
Expected
0
Explanation
No stored amount lies in [9, 20], so the sum is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →