How to do a breadth-first search using `find`

find

The -depth primary to find causes it to perform a depth-first search.

However, the default sequence is not a breadth-first search.

The default sequence could be informally described as a "depth-first traversal that handles nodes when they are first encountered rather than doing so during backtracking."

I have an actual need for breadth first search. How can I make find behave in this way?

For illustration, with the following setup:

$ mkdir -p alpha/{bravo,charlie,delta}
$ touch alpha/charlie/{alpha,beta,gamma,phi}

find has the following default behavior:

$ find alpha
alpha
alpha/charlie
alpha/charlie/alpha
alpha/charlie/phi
alpha/charlie/beta
alpha/charlie/gamma
alpha/delta
alpha/bravo

and with -depth, it performs as follows:

$ find alpha -depth
alpha/charlie/alpha
alpha/charlie/phi
alpha/charlie/beta
alpha/charlie/gamma
alpha/charlie
alpha/delta
alpha/bravo
alpha

However, what I want is the following (fictitious) option:

$ find alpha -bfs
alpha
alpha/charlie
alpha/delta
alpha/bravo
alpha/charlie/alpha
alpha/charlie/phi
alpha/charlie/beta
alpha/charlie/gamma

In other words I need find to process/report on all files/dirs at a given depth before proceeding further.

How can I do this?

Best Answer

You can do it with just shell wildcards. Build up a pattern with progressively more directory levels.

pattern='*'
set -- $pattern
while [ $# -ne 1 ] || [ "$1" != "$pattern" ]; do
  for file; do
    …
  done
  pattern="$pattern/*"
  set -- $pattern
done

This misses dot files. Use FIGNORE='.?(.)' in ksh, shopt -s dotglob in bash, or setopt glob_dots in zsh to include them.

Caveats:

  • This will blow up memory if there are a lot of files.
  • This traverses symbolic links to directories recursively.

If you want to choose the order or directories and non-directories, and performance isn't critical, you can make two passes and test [ -d "$file" ] on each pass.

Related Question