36

Breadth-first list is important, here. Also, limiting the depth searched would be nice.

$ find . -type d
/foo
/foo/subfoo
/foo/subfoo/subsub
/foo/subfoo/subsub/subsubsub
/bar
/bar/subbar

$ find . -type d -depth
/foo/subfoo/subsub/subsubsub
/foo/subfoo/subsub
/foo/subfoo
/foo
/bar/subbar
/bar

$ < what goes here? >
/foo
/bar
/foo/subfoo
/bar/subbar
/foo/subfoo/subsub
/foo/subfoo/subsub/subsubsub

I'd like to do this using a bash one-liner, if possible. If there were a javascript-shell, I'd imagine something like

bash("find . -type d").sort( function (x) x.findall(/\//g).length; )
6

9 Answers 9

36

The find command supports -printf option which recognizes a lot of placeholders.

One such placeholder is %d which renders the depth of given path, relative to where find started.

Therefore you can use following simple one-liner:

find -type d -printf '%d\t%P\n' | sort -r -nk1 | cut -f2-

It is quite straightforward, and does not depend on heavy tooling like perl.

How it works:

  • it internally generates list of files, each rendered as a two-field line
  • the first field contains the depth, which is used for (reverse) numerical sorting, and then cut away
  • resulting is simple file listing, one file per line, in the deepest-first order
0
24

If you want to do it using standard tools, the following pipeline should work:

find . -type d | perl -lne 'print tr:/::, " $_"' | sort -n | cut -d' ' -f2

That is,

  1. find and print all the directories here in depth first order
  2. count the number of slashes in each directory and prepend it to the path
  3. sort by depth (i.e., number of slashes)
  4. extract just the path.

To limit the depth found, add the -maxdepth argument to the find command.

If you want the directories listed in the same order that find output them, use "sort -n -s" instead of "sort -n"; the "-s" flag stabilizes the sort (i.e., preserves input order among items that compare equally).

4
  • Add "2>/dev/null" to the find command, i.e., find . -type d 2>/dev/null Will ensure that find error don't screw up the results. Nov 1, 2011 at 18:45
  • How about sorting alphabetically?
    – mr5
    Oct 24, 2015 at 8:51
  • Does not work if dirnames have spaces. For instance, if a dir is "/data/Mundial/Trinidad\ y\ Tobago/" you will have just "/data/arbol/Mundial/Trinidad".
    – alemol
    Nov 16, 2016 at 18:33
  • Thank you, this is the best one liner for sorting paths breadth-first that I've found (ignoring issues like spaces in pathnames). If you need to sort depth-first, see this explanation for a sort callback with strcmp() on each path element, returning length1 - length2 if components all match (equivalent to treating nonexistent components as empty strings) stackoverflow.com/a/4820233/539149 Apr 21, 2018 at 20:25
7

My feeling is that this is a better solution than previously mentioned ones. It involves grep and such and a loop, but I find it works very well, specifically for cases where you want things line buffered and not the full find buffered.

It is more resource intensive because of:

  • Lots of forking
  • Lots of finds
  • Each directory before the current depth is hit by find as many times as there is total depth to the file structure (this shouldn't be a problem if you have practically any amount of ram...)

This is good because:

  • It uses bash and basic gnu tools
  • It can be broken whenever you want (like you see what you were looking for fly by)
  • It works per line and not per find, so subsequent commands don't have to wait for a find and a sort
  • It works based on the actual file system separation, so if you have a directory with a slash in it, it won't be listed deeper than it is; if you have a different path separator configured, you still are fine.
#!/bin/bash 
depth=0

while find -mindepth $depth -maxdepth $depth | grep '.'
do
    depth=$((depth + 1))
done

You can also fit it onto one line fairly(?) easily:

depth=0; while find -mindepth $depth -maxdepth $depth | grep --color=never '.'; do depth=$((depth + 1)); done

But I prefer small scripts over typing...

7

You can use find command, find /path/to/dir -type d So below example list of directories in current directory :

find . -type d
1
  • 1
    This is not breadth-first, as explained literally in the question. Mar 3, 2021 at 16:57
6

I don't think you could do it using built-in utilities, since when traversing a directory hierarchy you almost always want a depth-first search, either top-down or bottom-up. Here's a Python script that will give you a breadth-first search:

import os, sys

rootdir = sys.argv[1]
queue = [rootdir]

while queue:
    file = queue.pop(0)
    print(file)
    if os.path.isdir(file):
        queue.extend(os.path.join(file,x) for x in os.listdir(file))

Edit:

  1. Using os.path-module instead of os.stat-function and stat-module.
  2. Using list.pop and list.extend instead of del and += operators.
3

I tried to find a way to do this with find but it doesn't appear to have anything like a -breadth option. Short of writing a patch for it, try the following shell incantation (for bash):

LIST="$(find . -mindepth 1 -maxdepth 1 -type d)";
while test -n "$LIST"; do
    for F in $LIST; do
        echo $F;
        test -d "$F" && NLIST="$NLIST $(find $F -maxdepth 1 -mindepth 1 -type d)";
    done;
    LIST=$NLIST;
    NLIST="";
done

I sort of stumbled upon this accidentally so I don't know if it works in general (I was testing it only on the specific directory structure you were asking about)

If you want to limit the depth, put a counter variable in the outer loop, like so (I'm also adding comments to this one):

# initialize the list of subdirectories being processed
LIST="$(find . -mindepth 1 -maxdepth 1 -type d)";
# initialize the depth counter to 0
let i=0;
# as long as there are more subdirectories to process and we haven't hit the max depth
while test "$i" -lt 2 -a -n "$LIST"; do
    # increment the depth counter
    let i++;
    # for each subdirectory in the current list
    for F in $LIST; do
        # print it
        echo $F;
        # double-check that it is indeed a directory, and if so
        # append its contents to the list for the next level
        test -d "$F" && NLIST="$NLIST $(find $F -maxdepth 1 -mindepth 1 -type d)";
    done;
    # set the current list equal to the next level's list
    LIST=$NLIST;
    # clear the next level's list
    NLIST="";
done

(replace the 2 in -lt 2 with the depth)

Basically this implements the standard breadth-first search algorithm using $LIST and $NLIST as a queue of directory names. Here's the latter approach as a one-liner for easy copy-and-paste:

LIST="$(find . -mindepth 1 -maxdepth 1 -type d)"; let i=0; while test "$i" -lt 2 -a -n "$LIST"; do let i++; for F in $LIST; do echo $F; test -d "$F" && NLIST="$NLIST $(find $F -maxdepth 1 -mindepth 1 -type d)"; done; LIST=$NLIST; NLIST=""; done
5
  • 1
    Looking at it again, this definitely makes my list of "things that should never be done in Bash" ;-)
    – David Z
    Feb 12, 2009 at 1:36
  • Can you also format it not as a one-liner to make understanding the code easier? (But yes, don't do this in bash :-)
    – Emil Sit
    Feb 12, 2009 at 1:37
  • Also prints regular files in base directory.
    – ypnos
    Feb 12, 2009 at 1:53
  • The -1 option for ls is unnecessary -- ls automatically prints in one column if stdout is not a terminal (i.e. if it's a pipe). Feb 12, 2009 at 2:00
  • k, fixed the regular file problem
    – David Z
    Feb 12, 2009 at 2:03
2

Without the deserved ordering: find -maxdepth -type d

To get the deserved ordering, you have to do the recursion yourself, with this small shellscript:

#!/bin/bash
r () 
{
    let level=$3+1
    if [ $level -gt $4 ]; then return 0; fi
    cd "$1"
    for d in *; do
        if [ -d "$d" ]; then
            echo $2/$d
        fi;
    done
    for d in *; do
        if [ -d "$d" ]; then
            (r "$d" "$2/$d" $level $4)
        fi;
    done
}
r "$1" "$1" 0 "$2"

Then you can call this script with parameters base directory and depth.

2
  • This is exactly what I want, but with the wrong ordering. I changed the question to clarify, thanks! Feb 12, 2009 at 1:25
  • see my addition! I wasn't finished :)
    – ypnos
    Feb 12, 2009 at 1:35
1

Here's a possible way, using find. I've not thoroughly tested it, so user beware...

depth=0
output=$(find . -mindepth $depth -maxdepth $depth -type d | sort); 
until [[ ${#output} -eq 0 ]]; do 
  echo "$output"
  let depth=$depth+1
  output=$(find . -mindepth $depth -maxdepth $depth -type d | sort)
done
0

Something like this:

find . -type d | 
  perl -lne'push @_, $_;
    print join $/,
      sort { 
        length $a <=> length $b || 
          $a cmp $b 
        } @_ if eof'

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.