Does the -depth option of find imply depth-first tree traversal

find

As I understand it the -depth option of the find command causes the specified actions to take place on the way out of a directory (and maybe I understand it wrong) during a depth-first traversal of a tree structure.

Without the -depth option specified, does it normally make an action occur before the depth-first traversal is complete, or does it do a breadth-first traversal of the directories and run the action first normally?

Best Answer

find uses a depth-first strategy (as opposed to breadth-first), whether -depth is specified or not. -depth only guarantees that sub-directories are processed before their parents.

A quick example:

mkdir -p a/{1,2,3} b c
find .

produces

.
./a
./a/2
./a/1
./a/3
./b
./c

whereas

find . -depth

produces

./a/2
./a/1
./a/3
./a
./b
./c
.

If you want breadth-first search, you can use bfs which is a breadth-first implementation of find.

Related Solutions

Expected behavior of `find -depth` if execute permission denied for subdirectory

Probably the better approach is to handle such directories explicitly. I don't know whether these are standard features but at least with Gnu find this is possible:

find . \( -type d \( \! -executable -or \! -readable \) \) -prune -or -type d

of course, it is also possible to print a message if a directory is ignored:

find . \( -type d \( \! -executable -or \! -readable \) \) \
  -printf "Permission denied: %p\n" -prune -or -type d -print

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

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.

Best Answer

Related Solutions

Expected behavior of `find -depth` if execute permission denied for subdirectory

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

Related Question