Someone

$html = "<ul>";
$stack=array();
$html="";
foreach($cats as $cat) {
    #this category is outside the last category on the stack
    #we need to close until we're outside the scope of the last rgt on the stack.
    while($cat['lft']>end($stack)) {
        $html .= "</ul>\n</li>\n";
        array_pop($stack);
    }
    $html .= "<li id=\"{$cat['id']}\">".$cat['cat_name'];
    #if the category has no children, close the list item.
    if($cat['lft']+1==$cat['rgt']) {
        $html .= "</li>\n";
    #category has children, start a list...add the "parent"'s right value to the stack
    } else {
        $html .= "<ul>";
        $stack[] = $cat['rgt'];
    }
}
#more stack popping as we clean up.
while($cat['lft']>end($stack)) {
    $html .= "</ul>\n</li>\n";
    array_pop($stack);
}
$html .= "</ul>";