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