BSTで2番目に小さい値を見つける
初期状態としてノードが1つも存在しない空のBinary Search Tree (BST) が与えられています。このBSTに対して、次の2種類のクエリを行います:
insert x- 値xをBSTに挿入する
smallest- BSTの中で2番目に小さい要素を出力する
合計で
q 個のクエリが与えられるので、これらのクエリを処理するプログラムを作成してください。入力 (Input)
最初の行に、クエリの個数を示す整数
q (1 ≤ q ≤ 1000) が与えられます。続く
q 行には、各クエリが1行ずつ与えられます。すべての insert クエリにおいて、値 x は絶対値で10^9を超えません。また、すべての smallest クエリを行う時点で、BSTには少なくとも2つの要素が含まれていることが保証されています。出力 (Output)
各
smallest クエリに対して、BST内で2番目に小さい要素を出力してください。例 (Examples)
Input | Output |
7
insert 2
insert 1
smallest
insert 10
smallest
insert -1
smallest | 2
2
1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB