A pricing service stores distinct tariff 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). After all insertions, report the k-th smallest tariff stored in the tree.
Line 1: an integer n, the number of tariffs.
Line 2: n space-separated distinct integers, the tariffs in insertion order.
Line 3: an integer k.
A single integer: the k-th smallest tariff (1-indexed, so k = 1 is the minimum).
Example 1
Input
5 30 10 40 20 50 3
Expected
30
Explanation
The stored tariffs sorted ascending are 10, 20, 30, 40, 50. The 3rd smallest is 30.
Example 2
Input
4 7 3 9 1 1
Expected
1
Explanation
Sorted ascending the tariffs are 1, 3, 7, 9, so the 1st smallest (the minimum) is 1.
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 →