A store keeps its distinct price points in a binary search tree. Starting from an empty tree, the prices are inserted one at a time in the order given (standard BST insertion: go left when the new price is smaller than the current node, otherwise go right). Given a budget, report the floor of the budget: the largest stored price that is less than or equal to budget.
Line 1: an integer n, the number of prices.
Line 2: n space-separated distinct integers, the prices in insertion order.
Line 3: an integer budget.
A single integer: the largest stored price <= budget. If no stored price is <= budget, print NONE.
Example 1
Input
6 40 20 60 10 30 50 35
Expected
30
Explanation
The stored prices <= 35 are 10, 20, and 30; the largest of these is 30, so the floor is 30.
Example 2
Input
5 5 2 8 6 9 1
Expected
NONE
Explanation
No stored price is <= 1 (the minimum is 2), so the answer is NONE.
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 →