build tree structure from flat array with parent IDs

tree_structure_from_flat_array.php

<?php

$menu = [
    1 => ['id' => 1, 'parent' => null, 'name' => 'Root Menu 1'],
    2 => ['id' => 2, 'parent' => 1, 'name' => 'Sub Menu 1 > 1'],
    3 => ['id' => 3, 'parent' => 1, 'name' => 'Sub Menu 1 > 2'],
    4 => ['id' => 4, 'parent' => 2, 'name' => 'Sub Menu 1 > 1 > 1']
];

function buildTree(&$menu)
{
    foreach ($menu as $menuItem) {
        if (is_null($menuItem['parent'])) continue;
        $parent = $menuItem['parent'];
        $menu[$parent]['sub'][] = &$menuItem;
    }

    return $menu;
}

echo json_encode(buildTree($menu), JSON_PRETTY_PRINT);