If you just tack a -p on your rmdir, that'll work in one pass. It won't be pretty or optimal, but it should get everything. That tells rmdir to remove any non-empty parent directories of the one you're removing.
You can save a little bit by adding the -empty flagtest to find, so it doesn't bother with non-empty directories.