BSTでk番目に小さい値を探す
空の二分探索木 (Binary Search Tree、BST) が与えられた状態から、次の2種類のクエリを処理する必要があります:
insert x- BSTに値xを挿入する
smallest k- BSTの中でk番目に小さい要素を出力する
クエリの総数として
qが与えられるので、これらのクエリを処理するプログラムを作成してください。入力
最初の行には、整数
q (1 ≤ q ≤ 1000) が与えられます。続く
q 行にはクエリが書かれています。出力
各
smallest クエリに対して、BSTの中でk番目に小さい要素を出力してください。例
入力例 | 出力例 |
8
insert 2
insert 1
smallest 1
smallest 2
insert 10
insert 20
smallest 3
smallest 2 | 1
2
10
2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB