Вобщем ничего такого сложного, но поскольку я на нее потратил сильно больше времени, чем казалось она того стоит (может просто тупил, да), то решил поделиться. ИМХО как вариант для собеседования тоже подойдет.
Дано: дерево в виде таблицы id'шек:
parent_id id
--------------
10 1
10 2
20 3
-1 20
20 10
parent_id = -1 означает корень, корней может быть больше одного
Плучить: таблицу отсортированную так, что каждому следующему parent_id предшествует его "объявление" в виде id. Т.е., для данного примера это будет:
parent_id id
--------------
-1 20
20 3
20 10
10 1
10 2
Решаем на любом языке (оберон как всегда интереснее всего
Решение на чистом SQL (из него все пошло) тоже интересно