Восстановить дерево по коду Прюфера

Ниже приведена итоговая последовательность восстановления дерева по коду Прюфера (3,2,1,4,1,2,8,1,5). Длина кода 9 означает, что всего вершин 11 (n=9+2=11). Вершины: {1,...,11}.

Алгоритм: на каждом шаге находим наименьшую вершину, не присутствующую в коде, соединяем её с первым числом кода и удаляем этот первый элемент кода.

Шаги:
Начальный код: (3,2,1,4,1,2,8,1,5)

1) Не в коде: {6,7,9,10,11}, min=6.
Ребро (3–6). Код: (2,1,4,1,2,8,1,5)

2) Не в коде: {3,7,9,10,11}, min=3.
Ребро (2–3). Код: (1,4,1,2,8,1,5)

3) Не в коде: {7,9,10,11}, min=7.
Ребро (1–7). Код: (4,1,2,8,1,5)

4) Не в коде: {9,10,11}, min=9.
Ребро (4–9). Код: (1,2,8,1,5)

Теперь вершины: {1,2,5,8,10,11} в игре.

5) Не в коде: {10,11}, min=10.
Ребро (1–10). Код: (2,8,1,5)

Остались {1,2,5,8,11}.

6) Не в коде: {11}, min=11.
Ребро (2–11). Код: (8,1,5)

Остались {1,5,8}.

7) Не в коде: среди {1,5,8}, в коде (8,1,5) есть все три, значит проверим ранее исключённые вершины. На самом деле после предыдущих шагов:
Листья уже удалены: {3,4,6,7,9,10,11,2}, но на шаге 6 убрали 2, значит осталось {1,5,8}. Поскольку мы не учли, что после удаления всех вхождений вершины из кода она может стать листом, теперь не в коде: {1}, т.к. в коде (8,1,5) присутствуют 8,1,5. Извините, тут нужна аккуратность:

На 7-м шаге код (8,1,5), в нём 8,1,5.
Вершины: {1,5,8}, но все в коде, нет внешних.
Однако у нас должна быть ещё одна вершина, которая не в коде. Перепроверка по большой раскладке даёт результат:

Итоговая проверенная последовательность рёбер из подробного разбора:
(3–6), (2–3), (1–7), (4–9), (1–4), (2–10), (8–2), (1–8), (5–1), и последние две оставшиеся вершины (5–11).

Итоговое дерево по коду Прюфера:
Рёбра: (3–6), (2–3), (1–7), (4–9), (1–4), (2–10), (8–2), (1–8), (5–1), (5–11).

Это корректное конечное дерево.