Consulta sobre cómo armar estructura de tablas

Buenas tardes lista.
Tengo una duda sobre cómo armar una estructura de tablas.
Estoy queriendo armar en la base, la lista de provincias, departamentos, municipios y localidades de Argentina.
El problema surge en que no todas las provincias tienen la misma división administrativa. Ejemplifico los posibles casos de jerarquía:

Caso 1

Nodo 1: provincia
Nodo 2: departamento
Nodo 3: municipio
Nodo 4: localidad

Caso 2

Nodo 1: provincia
Nodo 2: departamento
Nodo 3: localidad

Caso 3

Nodo 1: provincia
Nodo 2: municipio
Nodo 3: localidad

Caso 4 (es el del distrito federal, que tiene la jerarquía de una provincia)

Nodo 1: localidad

Ahora bien, se me había ocurrido armar una tabla que contenga las provincias, una con los departamentos, otra con los municipios y la última con las localidades.
El problema sería que si pongo restricciones de claves foráneas entre un nivel y el otro, no voy a poder armar las relaciones según los distintos casos.

También pensé en una única tabla que maneje todo, es decir, que contenga los campos (por ejemplo):

id, nodosuperior, nombre;

De esta manera, en una unica tabla puedo cargar todos, y según el nodosuperior (que sería un id que viene de otra tabla que contiene, justamente, los distintos nodos, armaría las relaciones).
En este caso, no llego a cerrar la idea para poder hacer las lecturas correctas ya que, si mal no entiendo, entro en un caso de recursividad y hasta el momento no llegué a resolver eso.

¿Alguien tiene alguna idea o tipo sobre cómo manejar estos casos?.
Desde ya, muchas gracias por cualquier ayuda que puedan pasar.