Usando la recursividad para construir la navegación

Aquí hay un ejemplo con recursividad.

function buildNavigation($items, $parent = NULL)
{
    $hasChildren = false;
    $outputHtml = '<ul>%s</ul>';
    $childrenHtml = '';

    foreach($items as $item)
    {
        if ($item['parent'] == $parent) {
            $hasChildren = true;
            $childrenHtml .= '<li>'.$item['category_name'];         
            $childrenHtml .= buildNavigation($items, $item['category_id']);         
            $childrenHtml .= '</li>';           
        }
    }

    // Without children, we do not need the <ul> tag.
    if (!$hasChildren) {
        $outputHtml = '';
    }

    // Returns the HTML
    return sprintf($outputHtml, $childrenHtml);
}

print buildNavigation($items);

Ese script produce el siguiente resultado:

<ul>
    <li>Menu 1</li>
    <li>Menu 2
        <ul>
            <li>Sub Menu 2.1</li>
            <li>Sub Menu 2.2</li>
            <li>Sub Menu 2.3
                <ul>
                    <li>Sub Menu 2.2.1</li>
                    <li>Sub Menu 2.2.2</li>
                    <li>Sub Menu 2.2.3</li>
                </ul>
            </li>
        </ul>
    </li>
    <li>Menu 3</li>
</ul>