En način je, da celoten meni sestaviš že na bazi. To bi bilo v primeru, da bi imel v tabeli en kup zapisov, aktualni bi pa bili samo nekateri:
http://guilhembichot.blogspot.com/2013/11/with-recursive-and-mysql.html
V MS-SQL se za te namene uporablja rekurzivni klic s pomočjo WITH ukaza, pri MySQL je pa potrebno malo več telovadbe.
Drugi način, ki je verjetno bolj primeren zate, je pa da uporabiš kakšen bolj ali manj učinkovit (= enostavnejši) algoritem za sestavljanje drevesa - kot so ti že predlagali.
Čisto enostavni način, ki je hkrati zelo neučinkovit, ko imaš veliko podatkov, je da uporabiš dve FOR zanki. Z vsako od njih se sprehodiš skozi svoj seznam in na PARENT_ID dodajaš ID zapise.
// Primer, ko imaš polje $kateg, kjer imaš pod vsakim zapisom spet polje vrednosti (lahko pa to predelaš z uporabo FOREACH)
// Tole pišem na pamet ni pretestirano
// Dele, ki se začnejo s TODO je potrebno še doprogramirati
$result = [];
// Spodnje zanke ponavljaj toliko časa, dokler ne bo nič več za dodati
$repeat = true;
while ($repeat) {
$repeat = false;
for ($a = 0, $ac = count($kateg); $a < $ac; $a++) {
$a_id = $kateg[$a]['id'];
$a_pid = $kateg[$a]['parent_id'];
// TODO: Dodaj preverjanje, če je element že v seznamu $result[], casting
if ($a_pid === null) $result[$a_id]['id_path'] = $a_id; // Sestavljaj pot povezanih ID-jev
for ($b = 0, $bc = count($kateg); $b < $bc; $b++) {
$b_id = $kateg[$b]['id'];
$b_pid = $kateg[$b]['parent_id'];
// TODO: Ni optimalno, ker se mora parent že nahajati v končnem seznamu
if ($a_id === $b_pid && in_array($a_id, $result)) {
// Dodaj v končni seznam
// TODO: Dodaj preverjanje, če je element že v seznamu $result[], casting
$result[$b_id]['id_path'] = $result[$a_id]['id_path'] . '#' . $b_id; // Sestavljaj pot povezanih ID-jev
$repeat = true;
}
}
}
}
Na koncu še posortiraš polje po 'id_path' ter urediš zamike.
Optimizacije so možne: npr. beležiš zapise, ki so že bili dodani in se po njih ne sprehajaš več v naslednjih korakih, idr.