In Robert Sedgewick's Algorithms book there's this exercise:

A folder is a list of files and folders. Write a program that takes the name of a folder as a command-line argument and prints out all of the files contained in that folder, with the contents of each folder recursively listed (indented) under that folder’s name. Hint: Use a queue.

Now I don't understand why I should use a queue for this. I can directly print it without first adding to the queue and dequeuing it later. Does it have any benefit that I cannot spot or is it just to strengthen my skills working with queues?

UPDATE: After so many answers and comments, I'm still confused as to how to print folders and files and subfolders the way the author wants. Please, could someone tell me if he wants something like this:

  folder1                folder2          file3.txt folder4
   folder1_1 file1_1.txt  folder2_1                  file4_1.txt
    folder1_1_1            file2_1_1.txt

If that's the case, then


There are two options to traverse a tree what a filesystem traditionally is.

  1. Traverse it using recursion.
  2. Use loops and a stack or queue to keep track of the remaining nodes to process

Recursion often incurs the overhead of method calls so Martin Fowler suggests to prefer iteration over recursion.

With a stack you keep track of the current node and all ancestors you're currently in. Push a node (folder) onto it when jumping in and pop the folder when there're no more folders inside the current one. This is equivalent to depth-first search.

With a queue you keep track of the folders you still need to jump into, hence the next level below the current one. It's breadth-first search which Wikipedia has a good description for.

| improve this answer | |
  • 1
    For those who may not be sure, using recursion implies using a stack is thus depth first. Also some language implementations may perform tail call optimization, which can eliminate the function call overhead in certain situations. – 8bittree Nov 29 '17 at 18:06
| improve this answer | |
  • 1
    Hey, thanks for that but let's make it a bit more clear. To collect files and folders to a queue don't I still have to recursively look for them in the given directory and add them as I come across one? So I was curious, why to add them to a queue and then deque them one by one if I can immediately print them. – Mikayil Abdullayev Nov 29 '17 at 6:46
  • 2
    You get a different order if you use a queue. "Because Files Depth Traversal First Is Way A To Silly Display" – Caleth Nov 29 '17 at 9:21
  • 1
    I like this answer more than I should. Well done! – T. Sar Nov 29 '17 at 12:01
  • 1
    For such a silly display, depth first seems to do pretty good job of representing which files and directories belong to which directories. I'm not so sure breadth first has a similarly useful property in this context. – 8bittree Nov 29 '17 at 18:00

As this is an exercises question I won't answer directly, just provide a hint (as @CandiedOrange's hint is a bit cryptic).

There are two basic ways to traverse a tree: depth-first and breadth-first. Think which one is preferred in this situation and about their implementations.

If you are set on getting a direct answer instead please comment and I'll edit in more details.

| improve this answer | |
  • I'd appreciate it if you provided the details you mentioned. – Mikayil Abdullayev Nov 29 '17 at 9:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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