Merge array by element’s parent_id in PHP

I am not sure if this has already been asked in PHP but I couldn’t find the answer

I have an array that lists id and parent id

$cats = [▼
  0 => array:4 [▼
    "id" => 5
    "parent_id" => 4
    "category" => "Detroit"
    "children" => []
  ]
  1 => array:4 [▼
    "id" => 4
    "parent_id" => 3
    "category" => "Michigan"
    "children" => []
  ]
  2 => array:4 [▼
    "id" => 2
    "parent_id" => 1
    "category" => "Cannes"
    "children" => []
  ]
  3 => array:4 [▼
    "id" => 1
    "parent_id" => 0
    "category" => "France"
    "children" => []
  ]
  4 => array:4 [▼
    "id" => 3
    "parent_id" => 0
    "category" => "United States"
    "children" => []
  ]
]

I want to loop by parent id backwards to merge the grandchildren into the children and the children into the parent.

I tried to find the parent by id using array search and then push the child into the parent’s children array

foreach ($cats as $element){
            //If not the root level
            if($element['parent_id']!==0){
                //Find parent index
                $parent_index = array_search($element['parent_id'],array_column($cats,'id'));
                //Push Child
                array_push($cats[$parent_index]['children'],$element);

            }
        }

I figure I need to unset the original child after it is pushed into the parent array but it seems when the child is pushed into the parent, the grandchild is missing (as you can see by the last entry of United States [index 4] having Michigan but not Detroit) which I though would have been updated in index 2.

array:5 [▼
  0 => array:4 [▼
    "id" => 5
    "parent_id" => 4
    "category" => "Detroit"
    "children" => []
  ]
  1 => array:4 [▼
    "id" => 4
    "parent_id" => 3
    "category" => "Michigan"
    "children" => array:1 [▼
      0 => array:4 [▼
        "id" => 5
        "parent_id" => 4
        "category" => "Detroit"
        "children" => []
      ]
    ]
  ]
  2 => array:4 [▼
    "id" => 2
    "parent_id" => 1
    "category" => "Cannes"
    "children" => []
  ]
  3 => array:4 [▼
    "id" => 1
    "parent_id" => 0
    "category" => "France"
    "children" => array:1 [▼
      0 => array:4 [▼
        "id" => 2
        "parent_id" => 1
        "category" => "Cannes"
        "children" => []
      ]
    ]
  ]
  4 => array:4 [▼
    "id" => 3
    "parent_id" => 0
    "category" => "United States"
    "children" => array:1 [▼
      0 => array:4 [▼
        "id" => 4
        "parent_id" => 3
        "category" => "Michigan"
        "children" => []
      ]
    ]
  ]
]

I appreciate any hint or answers on what I am doing wrong or why this isn’t working. Thanks!

Answer

Every time I see an arbitrarily nested array I think of recursion. You cannot do this with only one loop through the array.

This is my approach: loop through the array looking for children and append them to a new array, the first time to an empty array, successive times to the children array, recursively.

$cats = [
  [
    "id" => 5,
    "parent_id" => 4,
    "category" => "Detroit",
    "children" => [],
  ],
  [
    "id" => 4,
    "parent_id" => 3,
    "category" => "Michigan",
    "children" => [],
  ],
  [
    "id" => 2,
    "parent_id" => 1,
    "category" => "Cannes",
    "children" => [],
  ],
  [
    "id" => 1,
    "parent_id" => 0,
    "category" => "France",
    "children" => [],
  ],
  [
    "id" => 3,
    "parent_id" => 0,
    "category" => "United States",
    "children" => [],
  ]
];

$out = [];

function get_children($in, &$out, $parent){
    foreach ($in as $item) {
        if ($parent == $item["parent_id"]){
            $out[] = $item;
            get_children($in, $out[count($out)-1]["children"], $item["id"]);
        }
    }
}

get_children($cats, $out, 0);

print_r($out);

//OUTPUT:
Array
(
    [0] => Array
        (
            [id] => 1
            [parent_id] => 0
            [category] => France
            [children] => Array
                (
                    [0] => Array
                        (
                            [id] => 2
                            [parent_id] => 1
                            [category] => Cannes
                            [children] => Array
                                (
                                )

                        )

                )

        )

    [1] => Array
        (
            [id] => 3
            [parent_id] => 0
            [category] => United States
            [children] => Array
                (
                    [0] => Array
                        (
                            [id] => 4
                            [parent_id] => 3
                            [category] => Michigan
                            [children] => Array
                                (
                                    [0] => Array
                                        (
                                            [id] => 5
                                            [parent_id] => 4
                                            [category] => Detroit
                                            [children] => Array
                                                (
                                                )

                                        )

                                )

                        )

                )

        )

)

It might not be the most performant solution and I’m not knowledgeable enough to tell you the time or space complexity, but hey, it works!

EDIT

I realized only later that you can delete the elements from the original array when you add them to the new array, this should make it much more performant:

function get_children(&$in, &$out, $parent){
    foreach ($in as $key=>$item) {
        if ($parent == $item["parent_id"]){
            $out[] = $item;
            unset($in[$key]);
            get_children($in, $out[count($out)-1]["children"], $item["id"]);
        }
    }
}