<?php
$arr = array(
    array(
        'id' => '1',
        'name' => 'Имя раздела 1',
        'parentid' => '0'
    ),
    array(
        'id' => '2',
        'name' => 'Имя раздела 2',
        'parentid' => '0'
    ),
    array(
        'id' => '3',
        'name' => 'Имя раздела 3',
        'parentid' => '1'
    ),
    array(
        'id' => '4',
        'name' => 'Имя раздела 4',
        'parentid' => '2'
    ),
    array(
        'id' => '5',
        'name' => 'Имя раздела 5',
        'parentid' => '4'
    ),
    array(
        'id' => '6',
        'name' => 'Имя раздела 6',
        'parentid' => '2'
    ),
);


function form_tree($mess)
{
    if (!is_array($mess)) {
        return false;
    }
    $tree = array();
    foreach ($mess as $value) {
        $tree[$value['parentid']][] = $value;
    }
    return $tree;
}


function build_tree($cats, $parent_id)
{
    if (is_array($cats) && isset($cats[$parent_id])) {
        $tree = '<ul>';
        foreach ($cats[$parent_id] as $cat) {
            $tree .= '<li>' . $cat['name'];
            $tree .= build_tree($cats, $cat['id']);
            $tree .= '</li>';
        }
        $tree .= '</ul>';
    } else {
        return false;
    }
    return $tree;
}


$tree = form_tree($arr);
echo build_tree($tree, 0);