Loading...
Loading...
Loading...
Kavya's coaching centre ranks mock-test scores. Each score is a change from the last test, so it can be negative. The n scores are inserted, in the given order, into an empty binary search tree.
For each query k, print the k-th smallest score in the tree. If the tree has fewer than k scores, print NONE.
NONE.Example
Input
7 50 30 70 20 40 60 80 3 1 4 8
Output
20 50 NONE
In sorted order the scores are 20 30 40 50 60 70 80. The 1st is 20, the 4th is 50, and there is no 8th.
Try the problem first. Open one hint at a time.
Which walk of a binary search tree visits the values in sorted order?
An in-order walk (left subtree, node, right subtree) gives the values from smallest to largest.
Do the in-order walk once and store the values in a list. Then each query is a lookup at index k - 1.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor