The documentation of this function is generally ambiguous, because os.walk is a generator. Thus "generate" means (1) yielded from a generator and (2) prepared for later use within the generator. To avoid the ambiguity, "generate" should be avoided if possible. (1) might be replaced by "return" and (2) by "prepare".

@zbysz
The paragraph you cite is about "Modifying dirnames ". If you are not "Modifying dirnames" (like me) this section easily skips your attention.

My problem was, of course, that I had myself changed the directory structure - It's not a race condition with another process but an effect  of the loop os.walk was managing.

@pitrou
shutil.rmtree cannot help me, because I'm only deleting empty dirs.

Proposal (very verbose I'm afraid):
If you change the directory structure below dirpath while topdown=True, you can modify dirnames in-place so that walk will visit the right directories. If you change the directory structure below dirpath while topdown=False (maybe while you where there), dirnames and filenames can still reflect the old situation and it might be necessary to call os.listdir again.