Обход по порядку уровней путем преобразования N-арного дерева в представление списка смежности с K в качестве корневого узла

Учитывая корневой узел N-арного дерева и целое число K , задача состоит в том, чтобы преобразовать данное дерево в представление списка смежности и вывести обход порядка уровней, считая вершину K корневым узлом.

Пример:

Input: Tree in the image below, K = 5

Output:
5 
1 9 10 11 
2 3 4 
6 7 8

Input: Tree in the image below, K = 5

Output:
5 
1
2 3 4 
7 8

Подход: данная проблема может быть решена с помощью обхода DFS на N-арном дереве и сохранения отношения всех ребер в списке смежности в соответствии с представлением списка смежности. Созданный список смежности можно использовать для печати обхода порядка уровней с K в качестве корневого узла. Это можно сделать с помощью обхода BFS, который обсуждается в этой статье.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)