Breadth-First Search in a Directory

1. Overview

The find command is the most widely used command to find files and directories in Linux. It has a rich number of options for searching files and directories. Additionally, it lets us perform subsequent operations on the files or directories found.

As we’ll see, find performs a depth-first traversal of subdirectories to find files and directories.

In this tutorial, we’ll discuss how to list all subdirectories in a directory using breadth-first search.

2. The Default Search Behavior of find

The find command uses a depth-first search by default.

Let’s verify it with an example:

$ ls –l
drwxr-xr-x 3 alice alice 4096 Jan 23 15:58 dir1
drwxr-xr-x 3 alice alice 4096 Jan 23 15:58 dir2
drwxr-xr-x 3 alice alice 4096 Jan 23 15:58 dir3

We have three directories in our working directory. These are dir1, dir2 and dir3. Let’s list all subdirectories using find:

$ find . -type d
.
./dir1
./dir1/dir1.1
./dir2
./dir2/dir2.1
./dir2/dir2.1/dir2.1.1
./dir2/dir2.1/dir2.1.1/dir2.1.1.1
./dir2/dir2.1/dir2.1.1/dir2.1.1.2
./dir3

We used the -type d option to find all subdirectories in the current directory. As it’s apparent from the output, there are several subdirectories. The important point for us in this output is the search order. The find command first found the subdirectories in dir1, then in dir2, and finally in dir3. It listed the subdirectories of a directory starting from the top to the bottom in the directory hierarchy.

It’s possible to reverse the traversal of subdirectories from the bottom to the top using the -depth option. This option results in listing subdirectories before their parents:

$ find . -depth -type d
./dir1/dir1.1
./dir1
./dir2/dir2.1/dir2.1.1/dir2.1.1.1
./dir2/dir2.1/dir2.1.1/dir2.1.1.2
./dir2/dir2.1/dir2.1.1
./dir2/dir2.1
./dir2
./dir3
.

Although we listed the subdirectories from the bottom to the top in the directory hierarchy, this is still a depth-first search.

How can we use find to perform a breadth-first traversal of subdirectories? It should first traverse the subdirectories having a depth of 1, then subdirectories having a depth of 2, and so on. The output of a breadth-first search should be like the following in our case:

.
./dir1
./dir2
./dir3
./dir1/dir1.1
./dir2/dir2.1
./dir2/dir2.1/dir2.1.1
./dir2/dir2.1/dir2.1.1/dir2.1.1.1
./dir2/dir2.1/dir2.1.1/dir2.1.1.2

Unfortunately, find doesn’t have an option for breadth-first traversal of subdirectories.

3. A Solution for Breadth-First Search

We’ll find a method for the breadth-first traversal of subdirectories in this section.

3.1. Transforming the Output of Depth-First Search

We’ll use the printf option of find to transform the output of the depth-first search of find to an output of the breadth-first search.

The printf option has several directives. We’ll use the %d and %P directives:

$ find . -type d -printf "%d %p\n"
0 .
1 ./dir1
2 ./dir1/dir1.1
1 ./dir2
2 ./dir2/dir2.1
3 ./dir2/dir2.1/dir2.1.1
4 ./dir2/dir2.1/dir2.1.1/dir2.1.1.1
4 ./dir2/dir2.1/dir2.1.1/dir2.1.1.2
1 ./dir3

The %d directive prints the depth of the found file or directory in the directory tree. 0 is the starting directory. It corresponds to the current directory in our case.

The %p directive prints the name of the found file or directory.

Therefore, the find . –type –d –printf “%d %p\n” command listed the found subdirectories together with their depths. For example, the ./dir1 subdirectory has a depth of 1 while the ./dir2/dir2.1/dir2.1.1/dir2.1.1.1 subdirectory has a depth of 4.

Now, we’ll sort the directories using the depths in the first column:

$ find . -type d -printf "%d %p\n" | sort -n -k 1
0 .
1 ./dir1
1 ./dir2
1 ./dir3
2 ./dir1/dir1.1
2 ./dir2/dir2.1
3 ./dir2/dir2.1/dir2.1.1
4 ./dir2/dir2.1/dir2.1.1/dir2.1.1.1
4 ./dir2/dir2.1/dir2.1.1/dir2.1.1.2

We used the sort command for sorting. The -k option of sort is for sorting on a specific column. Since we specified the first column using -k 1, we sorted the subdirectories using their depths in the first column.

The -n option of sort, on the other hand, is for sorting numerically. For example, if we don’t use the -n option, sort lists a subdirectory having a depth of 10 before a subdirectory having a depth of 1.

Therefore, we have a list of subdirectories sorted according to their depths. We’ll filter the output using awk to list only the subdirectories:

$ find . -type d -printf "%d %p\n" | sort -n -k 1 | awk '{print $2}'
.
./dir1
./dir2
./dir3
./dir1/dir1.1
./dir2/dir2.1
./dir2/dir2.1/dir2.1.1
./dir2/dir2.1/dir2.1.1/dir2.1.1.1
./dir2/dir2.1/dir2.1.1/dir2.1.1.2

We used the awk ‘{print $2}’ to print only the second column in the output. The output is the same as the breadth-first search result we targeted in the previous section. Therefore, we we were able to transform the output of a depth-first search of find to an output of the breadth-first search.

3.2. Limiting the Depth

It’s possible to limit the depth using the -maxdepth option of find:

$ find . -maxdepth 2 -type d -printf "%d %p\n" | sort -n -k 1 | awk '{print $2}'
.
./dir1
./dir2
./dir3
./dir1/dir1.1
./dir2/dir2.1

Since we specified the maximum depth as 2 using the additional -maxdepth 2 option, the output just contains the subdirectories having a maximum depth of 2.

4. Conclusion

In this article, we discussed how to list all subdirectories in a directory using a breadth-first search.

Firstly, we saw that find uses a depth-first search by default. However, it doesn’t have an option for breadth-first traversal.

Then, we used the -printf option of find to display the found subdirectories together with their depths. We sorted the subdirectories according to their depths using the sort command and filtered the sorted subdirectories using awk.

Finally, we learned that it’s possible to limit the depth of subdirectories in the output using the -maxdepth option of find.