Преобразование списка словарей в иерархический словарь

Если id гарантированно уникальны, то никаких рекурсий не надо, достаточно просто организовать доступ к родителям по id (то есть создать словарь) и распихать элементы по этим родителям, пройдясь циклом один или два раза

Если в исходных данных родители гарантированно идут первыми, то достаточно пройтись циклом всего один раз. Данная реализация предполагает, что в словаре tree_items_by_id уже добавлены родители в предыдущих итерациях:

data = [
    {"id": "000", "name": "name_1", "status": "pass", "parent_id": None},
    {"id": "000_0", "name": "name_2", "status": "pass", "parent_id": None},
    {"id": "111", "name": "child_1", "status": "pass", "parent_id": "000"},
    {"id": "111_1", "name": "child_1_1", "status": "pass", "parent_id": "111"},
    {"id": "111_2", "name": "child_1_2", "status": "pass", "parent_id": "111"},
]

def make_tree(tests):
    # Сюда кладутся элементы без родителей
    tree = []

    # А здесь элементы с родителями будут искать своего родителя по id
    tree_items_by_id = {}

    for item_data in tests:
        # Для работы кода у элементов должны быть уникальные id
        item_id = item_data["id"]
        if item_data["id"] in tree_items_by_id:
            raise ValueError(f"Duplicate id {item_id}")

        parent_id = item_data["parent_id"]
        if parent_id is not None:
            # Если родитель есть — ищем его по id,
            # чтобы положить новый элемент в его children
            parent = tree_items_by_id[parent_id]
            parent_list = parent["children"]
            key_prefix = parent["key"] + "-"
        else:
            # Если родителя нет — положим новый элемент в tree
            parent = None
            parent_list = tree
            key_prefix = ""

        # Формируем новый элемент в нужном виде
        item = {
            "key": key_prefix + str(len(parent_list)),
            "data": item_data.copy(),
            "children": [],
        }
        item["data"].pop("parent_id")

        # Кладём его родителю (а если родителя нет, то parent_list это tree)
        parent_list.append(item)

        # И отдельно организуем доступ к нему через id
        tree_items_by_id[item_id] = item

    return tree

import json
print(json.dumps(make_tree(data), indent=2))

Если данные могут быть перемешаны, то key создаёт здесь существенную проблему, потому что для его формирования нужно знать всех родителей. Я попробовал сделать два цикла: первый формирует tree как обычно, но с пустыми key, а второй цикл, имея готовую структуру данных, может пройтись во всем элементам и сформировать key:

data = [
    {"id": "000", "name": "name_1", "status": "pass", "parent_id": None},
    {"id": "000_0", "name": "name_2", "status": "pass", "parent_id": None},
    {"id": "111", "name": "child_1", "status": "pass", "parent_id": "000"},
    {"id": "111_1", "name": "child_1_1", "status": "pass", "parent_id": "111"},
    {"id": "111_2", "name": "child_1_2", "status": "pass", "parent_id": "111"},
]

def make_tree2(tests):
    # Сюда кладутся элементы без родителей
    tree = []

    # А здесь элементы с родителями будут искать своего родителя по id
    children_by_id = {}

    for item_data in tests:
        # Для корректной работы кода у элементов должны быть уникальные id
        item_id = item_data["id"]

        parent_id = item_data["parent_id"]
        if parent_id is not None:
            # Если родитель есть — создаём список children для него
            try:
                parent_list = children_by_id[parent_id]
            except KeyError:
                parent_list = []
                children_by_id[parent_id] = parent_list
        else:
            # Если родителя нет — положим новый элемент в tree
            parent_list = tree

        # Формируем новый элемент в почти нужном виде
        # Список children мог быть создан в предыдущих итерациях цикла
        try:
            children = children_by_id[item_id]
        except KeyError:
            children = []
            children_by_id[item_id] = children

        item = {
            "key": "",  # Придётся сформировать позже
            "data": item_data.copy(),
            "children": children,
        }
        item["data"].pop("parent_id")

        # Кладём его родителю (а если родителя нет, то parent_list это tree)
        parent_list.append(item)

    # Теперь формируем key во втором цикле, используя очередь
    queue = [(str(item_idx), item) for item_idx, item in enumerate(tree)]
    while queue:
        key, item = queue.pop()
        item["key"] = key
        for child_idx, child_item in enumerate(item["children"]):
            # Заполняем очередь элементами из children
            # (можно заменить очередь на рекурсию, если она нравится больше)
            queue.append((f"{key}-{child_idx}", child_item))

    return tree

import random
random.shuffle(data)

import json
print(json.dumps(make_tree2(data), indent=2))

Рекурсивное решение - идём от текущего узла вверх по ветке, создавая недостающие parent узлы.

Пример: если первым попался узел child_1_1_1_1_1, то сначала надо создать ветку из 5 вышестоящих узлов, потом добавить его к родителю в children. Для child_1_1_1_1_2 ничего строить не придётся, нужная ветка и родитель уже есть - просто добавляем.

Алгоритм - перебираем список data, каждый словарь пытаемся добавить к родительскому узлу. Если такового ещё нет в дереве, откладываем текущий словарь и занимаемся родительским. Так рекурсивно поднимаемся пока не дойдём до существующего узла или корня, который гарантированно есть. После того как родительский узел оказывается на положенном месте, возвращаемся к отложенному словарю, делаем из него узел и добавляем его родителю в children.

Для быстрого нахождения узлов по id, все созданные узлы складываем в словарь pool. Благодаря этому, наличие родительского узла определяется за О(1), без поиска в дереве.

Для быстрого нахождения по id словарей с исходными данными создаём мапу (словарь) - id_to_data_map. Чтобы не искать в data за O(n).

data = [
    {"id": "000", "name": "name_1", "status": "pass", "parent_id": None},
    {"id": "000_0", "name": "name_2", "status": "pass", "parent_id": None},
    {"id": "111", "name": "child_1", "status": "pass", "parent_id": "000"},
    {"id": "111_1", "name": "child_1_1", "status": "pass", "parent_id": "111"},
    {"id": "111_2", "name": "child_1_2", "status": "pass", "parent_id": "111"}
]

def make_node(data_dct):
    node = {
        "key" : "", 
        "data" : {
            "name" : data_dct["name"],
            "id"   : data_dct["id"],
            "status" : data_dct["status"]
        },
        "children" : []
    }
    return node
    
def add_node(data_dct, pool, id_to_data_map):
    cur_id = data_dct["id"]
    if cur_id in pool:
        return

    parent_id = data_dct["parent_id"]
    if parent_id not in pool:
        add_node(id_to_data_map[parent_id], pool, id_to_data_map)
        return
    parent_node = pool[parent_id]

    node = make_node(data_dct)
    pool[cur_id] = node

    num = len(parent_node["children"])
    key = parent_node["key"]
    node["key"] = num if key == "" else f"{key}-{num}"

    parent_node["children"].append(node)

def make_tree(data):
    dummy_root = make_node({"id": "", "name": "", "status": "", "parent_id": None})
    id_to_data_map = {dct["id"] : dct for dct in data}
    pool = {None : dummy_root}
    for dct in data:
        add_node(dct, pool, id_to_data_map)

    return dummy_root["children"]

result = make_tree(data)
print(json.dumps(result, indent=4))