Is there a “breadth-first” search option available in os.walk() or equivalent Python function?

Question

Example directory tree:

     root
     /|\
    / | \
   /  |  \
  A   B   C
     /     \
    /       \
   D         E
              \
               \
                F
                 \
                  \
                   G

os.walk() will traverse this directory tree using the depth-first search algorithm. For example, os.walk() will process this tree in this order: root, A, B, D, C, E, F, G. os.walk() doesn't seem to provide an option for a breadth-first search. If this option were available, it would process this tree in this order instead: root, A, B, C, D, E, F, G. In my application, I need to do the reverse search. However, os.walk(tree, topdown = False) yields: A, D, B, G, F, E, C, root. On the contrary, the breadth-first search in reverse would yield: G, F, E, D, C, B, A, root.

I've had to create my own solution which is below:

def reversewalk(path):
    dirlist = {}
    for dirName, subdirList, fileList in os.walk(path, topdown=False):
        depth = dirName.count(os.path.sep)
        dirlist[os.path.abspath(dirName)] = (depth, dirName, subdirList, fileList)
    return sorted(dirlist.items(), key = lambda x : x[1], reverse = True)

My question is: Is there a "breadth-first" search option available in os.walk() or equivalent Python function? Follow up question is: If not, is there a better solution than the one I've presented?

Answer 1

The following code is from an ActiveState article I read:

#!/usr/bin/env python
import os

# -------------------------------------------
def breadthFirstFileScan( root ) :
    dirs = [root]
    # while we has dirs to scan
    while len(dirs) :
        nextDirs = []
        for parent in dirs :
            # scan each dir
            for f in os.listdir( parent ) :
                # if there is a dir, then save for next ittr
                # if it  is a file then yield it (we'll return later)
                ff = os.path.join( parent, f )
                if os.path.isdir( ff ) :
                    nextDirs.append( ff )
                else :
                    yield ff
        # once we've done all the current dirs then
        # we set up the next itter as the child dirs 
        # from the current itter.
        dirs = nextDirs

# -------------------------------------------
# an example func that just outputs the files.
def walkbf( path ) :
    for f in breadthFirstFileScan( path ) :
        print f

# ============================================
# as a demo we'll just start from where we 
# were called from.
walkbf( os.getcwd() )