Encontre o k-ésimo menor valor em uma BST
Dada uma árvore binária de pesquisa (BST) vazia, sem nós, você precisa realizar dois tipos de consultas:
insert x– insere o valorxna BST
smallest k– exibe o k-ésimo menor elemento na BST
Dadas
q consultas, você deve escrever um programa para processar todas elas.Entrada
A primeira linha da entrada contém um número
q (1 ≤ q ≤ 1000).As próximas
q linhas contêm as consultas. Para todas as consultas insert, o valor de x não excede em valor absoluto. Para todas as consultas smallest, o valor de k não excede o tamanho atual da árvore.Saída
Para cada consulta
smallest, o programa deve imprimir o k-ésimo menor valor na BST.Exemplos
Entrada | Saída |
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