Рекурсивная функция для деревьев в Python

Я пытаюсь сделать функцию в Python, которая принимает произвольное node дерева и заполняет список списков на основе node.

Учитывая следующее плохо вычеркнутое дерево:

Если мы начинаем с, например, node 5, мы должны получить:

Список, содержащий все узлы с одним и тем же родителем node, включая тот, который мы начали с (4 и 5)
Любые дочерние узлы, но не их дети (6).
Родительские узлы и любые родительские узлы с одним и тем же родителем и их родительскими узлами и т.д., пока мы не дойдем до корня node, но не включая корень node (только 2 и 3 в этом случае, но если дерево было глубже, и мы начали снижаться, здесь было бы больше.

И узлы должны попасть в список списков, по одному списку для каждой глубины.

Узлы в python:

nodes = [
    {'id': 1, 'parent': None},
    {'id': 2, 'parent': 1},
    {'id': 3, 'parent': 1},
    {'id': 4, 'parent': 2},
    {'id': 5, 'parent': 2},
    {'id': 6, 'parent': 5},
    {'id': 7, 'parent': 6},
    {'id': 8, 'parent': 3}
]

Мы можем видеть только родителей, а не детей, но это формат данных, с которым мне приходится работать, к сожалению.

Итак, если мы возьмем node 5, мы получим список node, который выглядит примерно так:

nl = [
    [{'id': 6, 'parent': 5}],
    [{'id': 4, 'parent': 2}, {'id': 5, 'parent': 2}],
    [{'id': 2, 'parent': 1}, {'id': 3, 'parent': 1}],
]

Это код, который у меня есть. Я считаю, что рекурсивная функция, вероятно, самый простой способ. К сожалению, он, похоже, ничего не делает, как я думаю, и, очевидно, я делаю что-то очень не так. И этот код даже не рассматривает вопрос о приобретении дочерних узлов, которые я не совсем уверен в том, как вообще иметь дело, кроме возможности передачи впоследствии, что было бы намного проще.

node_list = []

def pop_list(nodes=None, parent=None, node_list=None):
    if parent is None:
        return node_list
    node_list.append([])
    for node in nodes:
        if node['parent'] == parent:
            node_list[-1].append(node)
        if node['id'] == parent:
            parent = node['parent']
    return pop_list(nodes, parent, node_list)

print pop_list(nodes, 5, node_list)

Вот результат:

[[], [{'id': 3, 'parent': 1}], []]

Не совсем уверен, где я здесь ошибся.

Ответ 1