Print all the files in a given folder and sub-folders without using recursion/stack

Question

I recently had an interview with a reputable company for the position of Software Developer and this was one of the questions asked:

"Given the following methods:

List subDirectories(String directoryName){ ... }; 
List filesInDirectory(String directoryName) { ... };

As the names suggest, the first method returns a list of names of immediate sub-directories in the input directory ('directoryName') and the second method returns a list of names of all files in this folder.

Print all the files in the file system."

I thought about it and gave the interview a pretty obvious recursive solution. She then told me to do it without recursion. Since recursion makes use of the call stack, I told her I will use an auxillary stack instead, at which point point she told me not to use a stack either. Unfortunately, I wasn't able to come up with a solution. I did ask how it can be done without recursion/stack, but she wouldn't say.

How can this be done?

Answer 1

You want to use a queue and a BFS algorithm.

I guess some pseudo-code would be nice:

files = filesInDirectory("/")
foreach (file in files) {
   fileQ.append(file)
}

dirQ = subDirectories("/")
while (dirQ != empty) {
   dir = dirQ.pop
   files = filesInDirectory(dir)
   foreach (file in files) {
      fileQ.append(file)
   }
   dirQ.append(subDirectories(dir))
}

 while (fileQ != empty) {
   print fileQ.pop
 }

Answer 2

If I understood correctly, immediate sub-directories are only the directories in that folder. I mean if I=we have these three paths /home/user, /home/config and /home/user/u001, we can say that both user and config are immediate subdirectories of /home/, but u001 isn't. The same applies if user, and u001 are files (user is immediate while u001 isn't).

So you don't really need recursion or stack to return a list of immediate subdirectories or files.

EDIT: I thought that the OP wanted to implement the subDirectories() and filesInDirectories() functions.

So, you can do something like to print all files (kind of pseudocode):

List subd = subDirectories(current_dir);
List files = filesInDirectories(current_dir);

foreach (file in files) {
    print file.name();
}

while (!subd.empty()) {
    dir = subd.pop();

    files = filesInDirectory(dir.name());

    foreach (file in files) {
        print file.name();
    }

    subd.append(subDirectories(dir.path()));
}