O seguinte (se você substituir o primeiro diretório por diretório1 e o segundo por diretório2) deve fazer o que você está procurando e rapidamente:
find directory1 -type d -printf "%P\n" | sort > file1
find directory2 -type d -printf "%P\n" | sort | diff - file1
O princípio fundamental é que ele imprime todos os diretórios, incluindo os subdiretórios em relação aos diretórios baseN do diretório.
Isso pode falhar (produzir saída wierd) se você tiver retornos de carro em alguns dos nomes de diretório, mas não em outros.