Прямой обход дерева

Это же обычный обход графа вглубь.

Самый простой вариант, конечно — рекурсия.

получить массив словарей

Зачем? Почему не просто словарь?

levels = {}
def vizit(ID, counter=1):
  levels[ID] = counter
  for i in tree.get(ID, []): vizit(i, counter+1)

vizit(rootID)

как то так, tree это словарь с деревом

Кстати ТС не учел что корней может быть несколько. Ну и про получение корня как ID не фигурирующего в качестве дочерних элементов не учел.

Зачем? Почему не просто словарь?

Ему последовательность важна видимо. Но тогда можно взять OrderedDict конечно.

Или просто список пар (узел, глубина).

OrderedDict

А кстати, задача была бы интереснее, если бы id корневого узла был неизвестен.

А по факту корень и так неизвестен. Я ж написал что сперва все корни надо выдернуть как ID не встречкющиеся в дочерних.

А, да, писал, точно. Извините :)

Да, но это через set тривиально же делается:

set(tree.keys())-set(sum(tree.values(), []))

листья аналогично можно найти:

set(sum(tree.values(), []))-set(tree.keys())

чую мы сейчас за ТС-а сдадим зачет;-)

PS. Я бы у него спросил что делать если граф местами закольцован. Это чуть интересней.

PS. Я бы у него спросил что делать если граф местами закольцован. Это чуть интересней.

Да не, ТС говорил о дереве, но при необходимости можно ввести проверки и помечать узлы которые уже обошли.

Да, можно еще предложить ТС написать однострочник через reduce для поиска уровней;-)

OrderedDict

Не актуален.

Python 3.9.7 (default, Sep  4 2021, 03:09:52)
Type 'copyright', 'credits' or 'license' for more information
IPython 7.28.0 -- An enhanced Interactive Python. Type '?' for help.

In [1]: d = {i: i for i in range(30)}

In [2]: for k, v in d.items():
   ...:     print(k, v)
   ...:
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29