Gegeben sei ein Array mit paarweise verschiedenen Werten. Alice schlägt einen neuen Sortier-Algorithmus TreeSort vor um die Werte aufsteigend zu sortieren:

1. Füge die Werte nacheinander in einen binären Suchbaum ein.
2. Durchlaufe den Suchbaum per In-order-Traversierung und
   gebe so alle Werte sortiert zurück.

Führen Sie eine Analyse des Algorithmus durch (eine Implementierung ist nicht gefordert!). Wie lautet die Komplexitätsklasse (Speicherbedarf und Laufzeit) des Algorithmus im Best-Case und im Worst-Case? Für welche Eingaben wird dieser Worst-Case jeweils erreicht?