Files that are tracked by Git will be removed by Git when switching from a commit in which they exist (and hence are tracked1) to a commit in which they do not exist (and hence are not tracked). Having been removed by switching from the commit in which those files existed and were tracked, to a commit in which they do not exist and are not tracked, they are not in the work-tree and are not untracked files.
Should you somehow—by any means—switch from a commit in which a file is tracked, to a commit in which it is not, and therefore remove the copy of the file from the index2 so that it is untracked, without also removing the copy of the file from your work-tree,3 that file is now untracked and therefore Git won't remove it. There are multiple ways to achieve this, including running git rm --cached, which removes a copy of a file from the index without touching the copy of the file in your work-tree.
Git does little, and cares nothing, about folders: folders are the province, obsession, and problem of your computer system, not of Git. All Git cares about are files, which have names that for some reason, your computer insists on breaking up into folder-y pieces ending with a file-y piece: dir/sub/file.ext, which is a file in Git's eyes, is not a file on your computer: it is a folder (or directory) named dir containing a folder named sub containing a file named file.ext. Git does its best to accommodate your operating system's obsession with "folders" by creating dir/ so that it can create dir/sub/ so that it can create dir/sub/file.ext—the file it cares about—on demand. When Git is cleaning out a bunch of files such as dir/sub/file1.ext through dir/sub/fileN.ext, if it has cleaned out the last file, it will remove dir/sub/ as well. But it cannot do that if any file, including an untracked one, remains in that directory, so in that case, it won't ... and having removed all the dir/sub/* files—remember, to Git, these are just files, there's no folder-ing involved here—that it was tracking, Git now has no idea that dir/sub/ even exists any more. That's now your problem; if you remove the last of the untracked files from there, it's up to you to remove the directory too.
I have, over the decades, seen various corner cases where Git doesn't remove empty folders / directories despite having just cleaned them out while updating the index. These have decreased over time: it's much rarer now than it was back in 2005 (to the extent that I have not personally seen it in some years now). If you can find a repeatable sequence that leaves these behind, that does not involve operator error (untracked files), this is a bug, and you can file a bug report with the Git folks.4
1A Git file is tracked if and only if it is in the index. That's all there is to this: the presence of a file in the index means the file is tracked. The absence of a file in the index means that the file is not tracked.
To examine the index contents—note that this is quite long and not meant for everyday use by users—run git ls-files --stage. This thing—the entity that Git calls the index—is a central and key concept; you must understand how Git uses it, at least to some degree, to use Git effectively. Unfortunately, many Git tutorials try to hide it. Git itself doesn't show it very well: git ls-files --stage is not friendly at all.
The index is also known as the staging area, and (rarely these days) the cache. All three names refer to the same thing, although some commands (e.g., git apply) use --cached and --index in different ways.
2Technically, the "copies" of files in the index are actually references to Git's internal blob objects. See the git ls-files --stage output from footnote 1: each file entry in the index consists of a mode, a blob hash ID, a staging slot number—usually zero—and a name. (The index also contains cache data, hence one of its three alternate names.)
3The copies of files in your work-tree are yours to play with. That is why this is your work-tree: it is where you do your work. Git does not use these files to make the next commit; it uses instead the copies / references that are in the index. It's the index that matters when making new commits, and git checkout first extracts a checked-out commit to the index, before un-freezing and de-compressing and generally un-Git-ifying your files so that you can access them in your work-tree.
This is also why you have to git add files all the time: git add means copy the file back into the index, i.e., replace the frozen-format blob object with a new one made from whatever is in the work-tree now. Note that git add will in fact remove a file from the index, if the file is not in the work-tree, so in that sense, it's really make the index copy match the work-tree copy, even if that means remove the file.
4If you're using an ancient version of Git, upgrade before filing. If git --version prints anything older than about 2.17, that's pretty ancient. The current version is 2.25.1.
