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

algorithm, data-structures, language-agnostic

Solution

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
 }

Problem

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?

Original source