Encontrar el valor k-ésimo más pequeño en un BST
Dado un árbol de búsqueda binaria (BST) vacío sin ningún nodo, se solicitan 2 tipos de consultas:
insert x- insertar el valorxen el BST
smallest k- imprimir el elemento k-ésimo más pequeño en el BST
Dadas
q consultas, se pide escribir un programa que ejecute estas operaciones.Entrada
La primera línea de la entrada contiene un único número
q (1 ≤ q ≤ 1000).Las siguientes
q líneas contienen consultas. Para todas las consultas insert, el valor de x no supera en valor absoluto. Para todas las consultas smallest, el valor de k no excede el tamaño actual del árbol.Salida
Para cada consulta
smallest, el programa debe imprimir el elemento k-ésimo más pequeño en el árbol de búsqueda binaria.Ejemplos
Entrada | Salida |
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