<?php
$pagelist = $db->query("SELECT * FROM categories;");
$cat = array();
while ($echo = $pagelist->fetchArray()) {
$cat[$echo['parentid']][] = array('id' => $echo['id'], 'parentid' => $echo['parentid'], 'name' => $echo['name']);
}

//вывод каталога с помощью рекурсии
function view_cat($arr,$parent_id = 0) {
 //Условия выхода из рекурсии
 if(empty($arr[$parent_id])) {
  return;
 }
 echo '<ul>';
 //перебираем в цикле массив и выводим на экран
 for($i = 0; $i < count($arr[$parent_id]);$i++) {
  echo '<li><a href="?category_id='.$arr[$parent_id][$i]['id'].
 '&parent_id='.$parent_id.'">'
 .$arr[$parent_id][$i]['name'].'</a>';
  //рекурсия - проверяем нет ли дочерних категорий
  view_cat($arr,$arr[$parent_id][$i]['id']);
  echo '</li>';
 }
 echo '</ul>';

}

view_cat($cat);
?>