Без рекурсии:
1. Cначала отсортировать по количеству предков.
2. Потом для каждого элемента списка(для каждого его последнего листка) искать потомков, найденных засовываем во внутрь предка(в дерево) и удаляем из списка.
3. Затем проверяем есть ли элементы с предками - одиночки, если есть, то опять к пункту 2.
Сложность тут будет наверное O(n*n)