Finde den zweitkleinsten Wert in einem BST
Ausgehend von einem leeren Binary Search Tree (BST) ohne Knoten, sollen zwei Arten von Abfragen ausgeführt werden:
insert x– fügt den Wertxin den BST ein
smallest– gibt das zweitkleinste Element im BST aus
Sie erhalten
q Abfragen und sollen ein Programm schreiben, das diese Abfragen bearbeitet.Eingabe
Die erste Zeile enthält eine einzelne Zahl
q (1 ≤ q ≤ 1000).Die nächsten
q Zeilen enthalten die Abfragen. Bei allen insert-Abfragen überschreitet der Wert von x nicht den Betrag von . Bei allen smallest-Abfragen ist garantiert, dass der BST mindestens 2 Elemente hat.Ausgabe
Für jede
smallest-Abfrage gibt das Programm das zweitkleinste Element im BST aus.Beispiele
Eingabe | Ausgabe |
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