Побудова дерева

Вказівки

Переробіть алгоритм побудови дерева.

Деякі вебфоруми мають деревоподібне компонування, тому дописи показуються як дерево. Проте зазвичай дописи зберігаються в базі даних як невпорядкована множина записів. Тож коли ми показуємо дописи користувачеві, структуру дерева доводиться відновлювати.

У цій вправі ми переробимо робочий, але повільний і негарний фрагмент коду, який реалізує логіку побудови дерева для сильно абстрагованих записів. Записи містять лише ID та ID батьківського запису. ID завжди лежить від 0 (включно) до довжини масиву записів (не включно). У всіх записів батьківський ID менший за їхній власний ID, крім кореневого запису, у якого батьківський ID дорівнює його власному ID.

Приклад дерева:

root (ID: 0, parent ID: 0)
|-- child1 (ID: 1, parent ID: 0)
|    |-- grandchild1 (ID: 2, parent ID: 1)
|    +-- grandchild2 (ID: 4, parent ID: 1)
+-- child2 (ID: 3, parent ID: 0)
|    +-- grandchild3 (ID: 6, parent ID: 3)
+-- child3 (ID: 5, parent ID: 0)