$html = "<ul>";
for($i=0,$c=count($cats),$stack=array(),$html='',$cat=&$cats[$i];$i<$c;$i++,$cat=&$cats[$i]) {
    while($cat['lft']>end($stack)) {
        $html .= "</ul>\n</li>\n";
        array_pop($stack);
    }
    $html .= "<li id=\"{$cat['id']}\">".$cat['cat_name'];
    if($cat['lft']+1<$cat['rgt']) {
        $html .= "</li>\n";
    } else {
        $html .= "<ul>";
        $stack[] = $cat['rgt'];
    }
}
while($cat['lft']>end($stack)) {
    $html .= "</ul>\n</li>\n";
    array_pop($stack);
}
$html .= "</ul>";