How do I do a pre-order file traversal in bash?

Question

I was looking for a simple bash one-liner for traversing a file system and printing all the files in pre-order arrangement. It seems as though find is not capable of doing this. I could try to sort the results of find, but that doesn't seem feasible either. Is there an easy way to do this in bash?

For example,

find .                                                                                                                 
.
./sub2
./sub2/e.txt
./sub1
./sub1/b.txt
./sub1/c.txt
./sub1/sub3
./sub1/sub3/d.txt
./sub1/z.txt
./a.txt

It should instead be:

.
./a.txt
./sub2
./sub2/e.txt
./sub1
./sub1/b.txt
./sub1/c.txt
./sub1/z.txt
./sub1/sub3
./sub1/sub3/d.txt

What I've tried:

• looked at all find flags. It cannot print this way.
• looked at all sort flags. It can not interpret lines as paths and re-order them this way.

This is not pre-order because ./sub1/sub3/d.txt comes before ./sub1/z.txt.

Answer 1

You can do it like this with bash and GNU find:

bfind() {
  find "$1" -mindepth 1 -maxdepth 1
  find "$1" -mindepth 1 -maxdepth 1 -type d -exec bash -c 'bfind "$1"' bash {} \;
}

export -f bfind

bfind .

It's slow but does what you want.

Answer 2

A bash version:

findfile_preorder()(
    shopt -s dotglob nullglob
    for p; do
        printf '%s\n' "$p"
        [[ ! -L $p && -d $p ]] && findfile_preorder "$p"/*
    done
)

bash globs are sorted, so the output is also:

$ mkdir testdir
$ cd testdir
$ mkdir sub{1,2} sub1/sub3
$ touch a.txt sub2/e.txt sub1/{b,c,z}.txt sub1/sub3/d.txt
$ findfile_preorder .
.
./a.txt
./sub1
./sub1/b.txt
./sub1/c.txt
./sub1/sub3
./sub1/sub3/d.txt
./sub1/z.txt
./sub2
./sub2/e.txt
$

---

I believe the above algorithm is preorder traversal but it seems you also want to output all non-directories before descending the tree:

findfile_preorder2()(
    shopt -s dotglob nullglob
    local d=()
    for p; do
        if [[ ! -L $p && -d $p ]]; then
            d+=($p)
        else
            printf '%s\n' "$p"
        fi
    done
    for p in "${d[@]}"; do
        printf '%s\n' "$p"
        findfile_preorder "$p"/*
    done
)

which gives:

$ findfile_preorder2 .
.
./a.txt
./sub1
./sub1/b.txt
./sub1/c.txt
./sub1/z.txt
./sub1/sub3
./sub1/sub3/d.txt
./sub2
./sub2/e.txt
$