Binärer Suchbaum: Laufzeit O(n)?

Question

Frage:

Kann es einen vergleichsbasierten Algorithmus zum erstellen eines binären Suchbaums aus n
Elementen mit Laufzeit in O(n) geben?

Problem:

Ich bin mir bei dieser Frage relativ unsicher, kann mir da jemand weiterhelfen? :/

Answer 1

Würde es einen solchen Algorithmus geben, dann gäbe es auch einen Algorithmus, der n Elemente in Laufzeit O(n) sortiert.

Comments

Oh, danke für die tolle Antwort! :D