Преобразование плоского массива в вложенное дерево

Дана плоская структура данных — массив ветвей дерева, каждая из которых содержит уникальный идентификатор "id" и ссылку на родительский узел "parent", которая может быть либо "null", либо равна "id" другого элемента. Необходимо восстановить полное дерево, вложенность которого может быть неограниченной, группируя наследников по их родителям.

php/**
 * @param array{int, array{id: int, name: string, parent: ?int}} $dataset
 *
 * @return array{int, array{id: int, name: string, parent: ?int, children: array{int, array}}}
 */
function mapTree(array $dataset): array
{
    // do something
}

function testBuildTree(): void
{
    $input = [
        0 => ['id' => 0, 'parent' => null], // Root
        1 => ['id' => 1, 'parent' => null], // Root
        2 => ['id' => 2, 'parent' => 1], // Child 1
        3 => ['id' => 3, 'parent' => 1], // Child 2
        4 => ['id' => 4, 'parent' => 2], // Grandchild 1
        5 => ['id' => 5, 'parent' => 4], // Great-Grandchild 1
    ];

    $expected = [
        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($input) === $expected);
}

testBuildTree();