if($_SERVER['REQUEST_METHOD'] == 'POST'){
//do the magic, baby!
}
Выбираем все данные [...]и формируем ассоциативный массив $cats, ключем будет id родительской категорий.
foreach($cats as $cat){
$newcats[$cat['parent_id']][$cat['id']] = $cat;
}
$cats = $newcats;