Discussion 8: File System Trees

In lecture, we focused primarily on binary trees defined by a single node type. However, many trees include multiple types of nodes, with differing numbers of children possible for each node type. This even includes trees that can have an arbitrarily large number of children for some nodes. File systems are one example of this kind of tree. They have two types of nodes: folders and files. Files are always leaf nodes in your file system – them having no children – while folders can have any number of children. In this discussion, we’ll explore how to implement recursive methods over a tree structure that operates like your computer’s file system.

Learning Outcomes

  1. Given a parent class, use inheritance to develop one or more child subclasses.
  2. Identify parent, child, root, leaf, ancestor, and descendant nodes in a tree.
  3. Write recursive methods on general and binary trees.

Reminder: Discussion Guidelines

The work that you complete in discussion serves as a formative assessment tool; it offers the opportunity to assess your understanding of the material and for our course staff to get a “pulse” on how things are going, so we can make adjustments in future classes. Your grade in discussion is based on your attendance, active participation, and completion of that day’s activity. More information about the grading and expectations can be found in the syllabus.

Since discussion activities are not graded for correctness, we do not restrict what resources you may use to complete them, which include notes, books, unrestricted conversations with other students, internet searches, and the use of large language models or other generative AI. We advise you to be pragmatic about your use of these resources and think critically about whether they are enhancing your learning. Discussion activities are intended to serve as “strength training” for programming tasks we will expect on assignments and exams (and that you will encounter in future courses and careers), and their main benefit comes from thinking critically to “puzzle” them out.

Exercise 1: Warmup: Code Reading, Base and Recursive Cases
Download Starter Code download
For this discussion, you'll be submitting your code. You may find it useful to examine the starter code in detail, and consider how your recursive methods are likely to function given the behavior of the three classes you'll start off working with (FileSystemNode, File, and Folder). The following questions will not be submitted, but talking through them in your group for each method that you write will help offer direction for your coding.
(a)
What behaviors distinguish Files from Folders? Which of these behaviors are likely relevant to recursive methods on FileSystemNodes?
(b)
What do you think a likely base case is for a file system, for any given function? How would you implement such a base case?
(c)
What do you think a likely recursive case is for a file system, for any given function? How would you implement such a recursive case? In particular, how would you implement the recursive call(s)?
Exercise 2: Implementing Recursive Methods
(a)
The first method you should implement is fileCount(). Determine its base and recursive cases, and write them in the appropriate classes. Use the provided unit tests in FileCountTest.java to check the correctness of your implementation.
(b)
The second method you’ll be implementing is size(). Its base case is already written for you in the File class. Note how it automatically adjusts based on the size of the file’s contents. Complete the definition of this method by writing the Folder.size() method. Use the provided unit tests in SubtreeSizeTest.java to check the correctness of your implementation.
(c)
The final method you’ll implement is getFile(). Think carefully about how to parse its input in each class, and what to do with that input in the recursive case. This is a more complex recursive method than the previous two, though the code itself is still not very long. Use the provided unit tests in GetFileTest.java to check the correctness of your implementation.
Exercise 3: (Bonus Challenge) Implementing getPathFromName()
If you finish early, an additional method you can complete is getPathFromName(). Unlike getFile(), this method's input doesn't need to be specially parsed. However, it has the most complex recursive case of any of these methods. Carefully consider how you can utilize the return value to make your recursion work correctly, ignoring paths that don't lead to the correct file. Use the provided unit tests in GetPathTest.java to check the correctness of your implementation.

With all four of those recursive methods written, you might also be curious about how to use them as a client. The Simulation class contains a pre-constructed example file system, along with a list of three files by name. Utilizing some of the methods you have written, you can see that it's possible to print out the paths, sizes, and contents of each of those three files in only a few lines of code.

Submission

At the end of class, your group’s primary author should upload the following files to Gradescope:

  1. File.java
  2. Folder.java

Make sure that all other members of the group are tagged on the submission.