How to create nested array ancestors recursively in PHP

I’m using PHP 7.3. I want to create a nested array that each item must contain its own ancestors.

Original Array:

[
    [
        id => 1,
        parentId => ""
    ],
    [
        id => 2,
        parentId => 1
    ],
    [
        id => 3,
        parentId => 2
    ]
]

Required Array:

[
    [
        id => 1,
        parentId => "",
        ancestors => []
    ],
    [
        id => 2,
        parentId => 1,
        ancestors => [
            [
                id => 1,
                parentId => "",
                ancestors => []
            ],
        ]
    ],
    [
        id => 3,
        parentId => 2,
        ancestors => [
                [
                    id => 1,
                    parentId => "",
                    ancestors => []
                ],
                [
                    id => 2,
                    parentId => 1,
                    ancestors => [
                        [
                            id => 1,
                            parentId => "",
                            ancestors => []
                        ],
                    ]
                ],
        ]
    ]
]

I tried to use this solution, but I think this problem is different. Any help / guidance is greatly appreciated! Thanks.

Answer

You could first make use of array_column to group your entries by ID, then array_reduce to build your new array that includes ancestors (without altering the base one):

$entriesById = array_column($array, null, 'id');
    
$entriesWithAncestors = array_reduce(
  $entriesById,

  static function (array $result, array $entry) use ($entriesById): array {
    $result[$entry['id']] = $entry + ['ancestors' => []];
    $parentId = $entry['parentId'];
    while (isset($result[$parentId])) {
      $result[$entry['id']]['ancestors'][] = $result[$parentId];
      $parentId = $entriesById[$parentId]['parentId'] ?? null;
    }
    return $result;
  }, 

  []
);

print_r($entriesWithAncestors);

Demo

Note that this assumes parent entries are always present before their children in the original array, as you mentioned in the comments.