Дан линейный набор элементов, представляющих узлы дерева. Каждый элемент содержит уникальный идентификатор id и ссылку на родительский узел parent, которая может быть null (корневой узел) либо указывать на id другого элемента. Требуется собрать полное дерево произвольной глубины, разместив дочерние элементы внутри массива children их родителя.

/**
 * @param array{int, array{id: int, name: string, parent: ?int}} $flatList
 *
 * @return array{int, array{id: int, name: string, parent: ?int, children: array{int, array}}}
 */
function mapTree(array $flatList): array
{
    // implement conversion here
}

function testBuildTree(): void
{
    $source = [
        0 => ['id' => 0, 'parent' => null], // корень
        1 => ['id' => 1, 'parent' => null], // корень
        2 => ['id' => 2, 'parent' => 1],    // потомок 1
        3 => ['id' => 3, 'parent' => 1],    // потомок 2
        4 => ['id' => 4, 'parent' => 2],    // внук 1
        5 => ['id' => 5, 'parent' => 4],    // правнук 1
    ];

    $resultTree = [
        0 => ['id' => 0, 'parent' => null],
        1 => [
            'id' => 1, 'parent' => null, 'children' => [
                0 => ['id' => 2, 'parent' => 1, 'children' => [
                    0 => ['id' => 4, 'parent' => 2, 'children' => [
                        0 => ['id' => 5, 'parent' => 4],
                    ]],
                ]],
                1 => ['id' => 3, 'parent' => 1],
            ],
        ],
    ];

    assert(mapTree($source) === $resultTree);
}

testBuildTree();

Конверсия плоского массива в вложенную иерархию дерева