Tenes que usar recursividad. La db esta bien, así que la lógica sería algo así:
Código PHP:
function arbol( $parent ){
$r = mysql_query( "SELECT * FROM categorias where parent ='$parent' " );
while( $rs = mysql_fetch_assoc( $r ) ){
echo $rs["nombre"] . "<br />";
arbol( $rs["id"] );
} mysql_free_result( $r );
}
arbol( 0 );
Espero que no te haga un loop infinito :P, no la probé, pero debería funcionarte ;)
Ah, y esta de funcionar si permite n padres he hijos.