Ich würd's anders herum machen.
Nodes wie sie hereinkommen in eine Liste werfen. Kommt ein Node, zwei Dinge tun:
1) Falls der Node einen Parent hat: Alle bestehenden Nodes absuchen, ob da dieser Parent bei ist (nicht vergessen die gesamten Teilbäume mit abzusuchen). Ist der Parent schon da, den neuen Node da dran hängen, ansonsten hinten an die Liste kleben.
2) Alle "First-Level"-Nodes durchsuchen (also diesmal nur die tatsächlich in der Liste stehenden, nicht was hinten dran ist), und schauen ob da welche den eben eingefügten als Parent haben. Diese dann an den neuen Node anhängen und aus der Liste löschen (damit wandert der ggf. daran hängende Teilbaum ja gleich mit).
Hat den Vorteil, dass du nur ein Mal durch die
DB musst, und auch nicht nachträglich zusammenfügen o.ä. musst. Ausserdem entdeckst du evtl. auch noch fehler, wenn nämlich die Liste nachher >1 lang ist, sind Nodes ohne gültigen Parent in der
DB 
Die Suchoperation bei 2) lässt sich gut durch Sortierthalten der Liste optimieren, da dann z.B. mit Binary Serach gesucht werden kann. Bei 1) geht das nur, wenn sicher ist dass alle children des Nodes N eine kleinere ID als der Node N+1 in der sortierten Liste haben. (Was alles ohnehin nur bei Bäumen mit ein paar tausend Nodes merkbare Unterschiede machen sollte.)
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)