How to Recursively List All Directories at a Location, Breadth-First

How do I recursively list all directories at a location, breadth-first?

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

Recursively listing all subdirectory of a given directory

To print the directory structure in a BFS, you could use a queue. Since C doesn't have such a thing in its standard library, you have to roll your own or use a library. Here's a simple example of how this might work, alongside a cleaned up version of your DFS.

#include <dirent.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void listDirBFS(char *name)
{
    int q_front = 0;
    int q_back = 1;
    int q_cap = 4;
    char **q = malloc(q_cap * sizeof(*q));

    for (q[0] = strdup(name); q_front != q_back;) 
    {
        name = q[q_front++];
        DIR *dir = opendir(name);

        if (!dir) continue;

        printf("%s\n", name);
        size_t name_len = strlen(name);
        struct dirent *cDir;

        while ((cDir = readdir(dir)))
        {
            char *subName = cDir->d_name;

            if (strcmp(subName, ".") && strcmp(subName, "..") &&
                cDir->d_type == DT_DIR)
            {
                char *path = malloc(name_len + strlen(subName) + 2);
                sprintf(path, "%s/%s", name, subName);

                if (q_back >= q_cap && 
                    !(q = realloc(q, sizeof(*q) * (q_cap *= 2)))) 
                {
                    fprintf(stderr, "%s:%d realloc\n", __FILE__, __LINE__);
                    exit(1);
                }

                q[q_back++] = path;
            }
        }

        free(name);         
        closedir(dir);
    }

    free(q);
}

void listDir(char *name)
{
    DIR *dir = opendir(name);

    if (!dir) return;

    printf("%s\n", name);
    size_t name_len = strlen(name);
    struct dirent *cDir;

    while ((cDir = readdir(dir)))
    {
        char *subName = cDir->d_name;

        if (strcmp(subName, ".") && strcmp(subName, "..") &&
            cDir->d_type == DT_DIR)
        {
            char *path = malloc(name_len + strlen(subName) + 2);
            sprintf(path, "%s/%s", name, subName);
            listDir(path);
            free(path);
        }
    }

    closedir(dir);
}

int main(int argc, char **argv)
{   
    puts("== DFS ==");
    listDir(".");
    puts("\n== BFS ==");
    listDirBFS(".");
    return 0;
}

Output:

== DFS ==
.
./a
./a/b
./a/b/e
./a/bb
./a/bb/f
./a/bb/f/g
./aa
./aa/c
./aaa
./aaa/d
./aaa/d/h
./aaa/d/hh

== BFS ==
.
./a
./aa
./aaa
./a/b
./a/bb
./aa/c
./aaa/d
./a/b/e
./a/bb/f
./aaa/d/h
./aaa/d/hh
./a/bb/f/g

A few remarks and suggestions on your code:

• sizeof(name) + sizeof(subName) is incorrect. sizeof returns the size of the pointers; strlen is probably what you intended to get the lengths of the pointed-to strings. This avoids undefined behavior due to possibly strcat-ing beyond the allocated memory.
• Always free memory after use to avoid memory leaks.
• Compiling with the -Wall flag to turn warnings on reveals that control reaches the end of a non-void function. Change your return type from int to void if you're not actually returning an integer.
• Note that I changed where the prints occur. You can move them back to the location of the recursive call, but I prefer to do the work for each node at the top of the function before exploring children. The algorithms are fundamentally the same.

How to recursively list directories in C on Linux?

Here is a recursive version:

#include <unistd.h>
#include <sys/types.h>
#include <dirent.h>
#include <stdio.h>
#include <string.h>

void listdir(const char *name, int indent)
{
    DIR *dir;
    struct dirent *entry;

    if (!(dir = opendir(name)))
        return;

    while ((entry = readdir(dir)) != NULL) {
        if (entry->d_type == DT_DIR) {
            char path[1024];
            if (strcmp(entry->d_name, ".") == 0 || strcmp(entry->d_name, "..") == 0)
                continue;
            snprintf(path, sizeof(path), "%s/%s", name, entry->d_name);
            printf("%*s[%s]\n", indent, "", entry->d_name);
            listdir(path, indent + 2);
        } else {
            printf("%*s- %s\n", indent, "", entry->d_name);
        }
    }
    closedir(dir);
}

int main(void) {
    listdir(".", 0);
    return 0;
}

Recursive breadth first traversal in Bash

You cannot pass arrays as arguments. You can only pass strings. You'll have to expand
the array to a list of its contents first. I've taken the liberty of making depth
local to your function, rather than what I assume is a global variable.

traverse(){
  local depth=$1
  shift
  # Create a new array consisting of all the arguments.
  # Get into the habit of quoting anything that
  # might contain a space
  for x in "$@"; do
    echo "directory contains: $@"
    new_temp=()
    for y in "$x"/*; do
      echo "$x/$y"
      new_temp+=( "$x/$y" )
    done
  done

  (( depth-- ))
  if (( depth > 0 )); then
    traverse $depth "${new_temp[@]}"
  fi
}

$ dir=( a b c d )
$ init_depth=3
$ traverse $init_depth "${dir[@]}"  

Recursively iterate over all the files in a directory and its subdirectories in Qt

I suggest you have a look at QDirIterator.

QDirIterator it(dir, QStringList() << "*.jpg", QDir::Files, QDirIterator::Subdirectories);
while (it.hasNext())
    qDebug() << it.next();

You could simply use QDir::entryList() recursively, but QDirIterator is simpler. Also, if you happen to have directories with a huge amount of files, you'd get pretty large lists from QDir::entryList(), which may not be good on small embedded devices.

Example (dir is QDir::currentPath()):

luca @ ~/it_test - [] $ tree
.
├── dir1
│   ├── image2.jpg
│   └── image3.jpg
├── dir2
│   └── image4.png
├── dir3
│   └── image5.jpg
└── image1.jpg

3 directories, 5 files
luca @ ~/it_test - [] $ /path/to/app
"/home/luca/it_test/image1.jpg"
"/home/luca/it_test/dir3/image5.jpg"
"/home/luca/it_test/dir1/image2.jpg"
"/home/luca/it_test/dir1/image3.jpg"

How to set recursive depth for the Windows command DIR?

I'm sure it is possible to write a complex command that would list n levels of directories. But it would be hard to remember the syntax and error prone. It would also need to change each time you want to change the number of levels.

Much better to use a simple script.

EDIT 5 Years Later - Actually, there is a simple one liner that has been available since Vista. See my new ROBOCOPY solution.

Here is a batch solution that performs a depth first listing. The DIR /S command performs a breadth first listing, but I prefer this depth first format.

@echo off
setlocal
set currentLevel=0
set maxLevel=%2
if not defined maxLevel set maxLevel=1

:procFolder
pushd %1 2>nul || exit /b
if %currentLevel% lss %maxLevel% (
  for /d %%F in (*) do (
    echo %%~fF
    set /a currentLevel+=1
    call :procFolder "%%F"
    set /a currentLevel-=1
  )
)
popd

The breadth first version is nearly the same, except it requires an extra FOR loop.

@echo off
setlocal
set currentLevel=0
set maxLevel=%2
if not defined maxLevel set maxLevel=1

:procFolder
pushd %1 2>nul || exit /b
if %currentLevel% lss %maxLevel% (
  for /d %%F in (*) do echo %%~fF
  for /d %%F in (*) do (
    set /a currentLevel+=1
    call :procFolder "%%F"
    set /a currentLevel-=1
  )
)
popd

Both scripts expect two arguments:

arg1 = the path of the root directory to be listed

arg2 = the number of levels to list.

So to list 3 levels of the current directory, you could use

listDirs.bat . 3

To list 5 levels of a different directory, you could use

listDirs.bat "d:\my folder\" 5

Using os.walk() to recursively traverse directories in Python

This will give you the desired result

#!/usr/bin/python

import os

# traverse root directory, and list directories as dirs and files as files
for root, dirs, files in os.walk("."):
    path = root.split(os.sep)
    print((len(path) - 1) * '---', os.path.basename(root))
    for file in files:
        print(len(path) * '---', file)

Can 'find' or any other tool search for files breadth-first?

Yes, sort of.

You can use the -depth option to make it process a directory's contents before the directory itself. You can also use the -maxdepth option to limit how many directories down it will drill.

Iterate through a fileSystem without using Binary tree or recursion

If, for some reason, you insist on non recursive solution, although FileVisitor is definitely way to go with this in Java, breadth first search can be implemented non recursively.

This is general definition, marking is used to avoid circular referencing although you wont have that in this case:

• Enqueue root of directories and mark root as discovered
• while queue is not empty
• dequeue and process element
• discover adjacent edges - children
• for every child, if not marked already and is a directory, mark and queue

To get children you need: String[] directories = file.list().
To make sure you are queuing directories and not files
call file.isDirectory() and enqueue only directories.

You do not need to do marking before queuing as you won't have circular reference between directories.

Edit:

Here is recursive breadth first search, you can modify it into iterative with the pseudo code above.

import java.io.File;
import java.util.LinkedList;
import java.util.Queue;

public class BFSRecursive {

public static void main(String[] args) {

    File file = new File("D:/Tomcat");

    Queue<File> files = new LinkedList<>();
    files.add(file);
    bfs(files);

}

private static void bfs(Queue<File> files) {

    if (files.isEmpty())
        return;

    File file = files.poll();
    System.out.println(file.getName());

    String[] directories = file.list();

    for(String child: directories) {
        File childFile = new File(file.getAbsolutePath() +"/"+ child);

        if (childFile.isDirectory())
            files.add(childFile);
    }

    bfs(files);
  }
}

Breadth First Directory Listing

How can BFS apply to directory structure? Both, BFS and DFS concepts are about tree data structures (directory can be a tree too). Assuming you understand tree depth, BFS is basically visiting all nodes in order from lowest depth to greatest. Stack is to DFS as Queue is to BFS.

I'm not sure if there is a "for-dummies" implementation. I think the concept is as simple as I've explained. Wikipedia should provide the missing information.

What doubt do you have about your implementaion? Like I said, the only diffence between DFS and BFS is using Stack or Queue.

---

Related Topics