Der Ansatz von ManBu wird auch hier gezeigt:
http://stackoverflow.com/questions/4...flat-structure
Das wäre immerhin schon lineare Laufzeit (also O(n) worst-case) wenn ich mich nicht irre. (Den erstellten Baum am Ende in-order zu durchlaufen ist ebenfalls linear mit der Anzahl der Elemente) Viel schneller (bzgl. big-O) wird es wohl auch nicht gehen.