Maximaler Knoten in einem Binary Search Tree
Ausgehend von einem leeren Binary Search Tree (BST) ohne Knoten sollen Sie drei Arten von Abfragen ausführen:
insert x– Fügt den Wertxin den BST ein.max– Gibt den maximalen Wert im BST aus.print– Gibt den BST in In-Order-Reihenfolge aus.
Es wird vorausgesetzt, dass q Abfragen vorliegen. Ihre Aufgabe ist es, ein Programm zu schreiben, das diese Abfragen entsprechend ausführt.
Input
Die erste Zeile der Eingabe enthält eine einzelne Zahl q (1 ≤ q ≤ 1000).
Die nächsten q Zeilen enthalten Abfragen. Bei allen insert-Abfragen überschreitet der Wert x nicht den Betrag .
Output
Für jede max-Abfrage soll das Programm den maximalen Wert des BST in einer eigenen Zeile ausgeben.
Für jede print-Abfrage soll das Programm die Post-Order-Traversierung des BST ausgeben. Die Werte werden dabei durch ein Leerzeichen getrennt.
Examples
Input | Output |
|---|---|
7 insert 2 insert 1 max insert 0 max insert 4 print | 2 2 0 1 4 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB