¡Usa la recursividad! Nota:¡el siguiente código no es seguro para gráficos cíclicos (es posible que los nodos no sean ancestros de sí mismos)!
printChildren($items,0);
function printChildren(array $items, $parentId){
foreach($items as $item){
if($item['parent']==$parentId){
print '<li>';
print $item['label']; //or whatever you want about the current node
print '<ul>';
printChildren($items, $item['id']);
print '</ul></li>';
}
}
}