Meiner Meinung nach liegt der Knackpunkt in der Array-Repräsentation des bin. Baumes, die sicherlich ohne zusätzliche Hilfsarrays, die parent-Referenzen o.ä. enthalten, auskommen soll.
So etwas habe ich hier gefunden: http://www.cogs.susx.ac.uk/courses/dats/notes/html/node79.html
Der Baum wird also mit dem breadth-first-Verfahren traversiert und im Array abgelegt.
Aus dem Array wird der bin. Baum durch die übliche insert-Methode rekonstruiert.
.
Oder habe ich etwas übersehen? Weil nur scharf nachgedacht und nicht mit Programm getestet...