Practice 9 — Trees

Skills: 8

Reading: the Notes sections of Class 23 and Class 24

Trees and Hierarchical Data

Trees are hierarchical data -- data that nest sub-entities within a larger entity. Consider a file system where folders contain files and other folders. A table represents flat rows. While you can include a "parent folder" field in each row, you lose the nesting structure.

A File System Table Example

Here's a file system table:

filesystem_table = table(
    ["name", "type", "parent", "size"],
    [
        ["Documents", "folder", "", 0],
        ["Photos", "folder", "", 0],
        ["resume.pdf", "file", "Documents", 150],
        ["notes.txt", "file", "Documents", 25],
        ["School", "folder", "Documents", 0],
        ["homework.doc", "file", "School", 75],
        ["vacation.jpg", "file", "Photos", 500],
        ["family.jpg", "file", "Photos", 300],
    ],
)

What happens if we want to calculate the total size of the Documents folder including all subfolders?

While tables are great for flat data, they make representing and processing hierarchical (tree) data hard. The recursive nature of trees (folders contain folders contain folders...) suggests we need a recursive data structure.

Defining a Recursive Datatype for File System Trees

Data Definition

Define a new datatype called FileTree:

from dataclasses import dataclass

@dataclass
class File:
    name: str
    size: int

@dataclass
class Folder:
    name: str
    contents: "list[FileTree]"

FileTree = File | Folder

We have two variants: files (with name and size) and folders (with name and list of contents).

Example

Build a simple file system tree:

resume = File("resume.pdf", 150)
notes = File("notes.txt", 25)
homework = File("homework.doc", 75)
vacation_pic = File("vacation.jpg", 500)
family_pic = File("family.jpg", 300)

school_folder = Folder("School", [homework])
docs_folder = Folder("Documents", [resume, notes, school_folder])
photos_folder = Folder("Photos", [vacation_pic, family_pic])

root = Folder("Root", [docs_folder, photos_folder])

Discovering Recursive Functions on Trees

Notice that a FileTree can be either a file (base case) or a folder containing a list of other FileTrees (recursive case).

Example

• For a file, count is 1
• For a folder, count is 1 (for the folder itself) plus the count of each item in contents

Design a function count_items that counts all items in a file tree:

def count_items(ft: FileTree) -> int:
    match ft:
        case File(n, s):
            pass  # YOUR CODE HERE
        case Folder(n, contents):
            pass  # YOUR CODE HERE

def test_count_items():
    assert count_items(resume) == 1
    assert count_items(school_folder) == 2

def count_items_list(fts: list[FileTree]) -> int:
    match fts:
        case []:
            pass  # YOUR CODE HERE
        case [first, *rest]:
            pass  # YOUR CODE HERE

Traversing Trees Recursively

Design a function that returns only file names (not folder names):

def list_files_only(ft: FileTree) -> list[str]:
    match ft:
        case File(n, s):
            pass  # YOUR CODE HERE
        case Folder(n, contents):
            pass  # YOUR CODE HERE

def test_list_files_only():
    assert list_files_only(resume) == ["resume.pdf"]
    assert list_files_only(docs_folder) == ["resume.pdf", "notes.txt", "homework.doc"]

You'll also need to design a helper function list_files_only_list that processes a list of file trees.

Transforming Trees

for loops require linear data (lists) because they process elements sequentially. Trees have branching structure, so you must reconstruct the structure recursively.

Design a function that keeps only files larger than a certain size:

def keep_large_files(ft: FileTree, min_size: int) -> FileTree:
    match ft:
        case File(n, s):
            pass  # YOUR CODE HERE
        case Folder(n, contents):
            pass  # YOUR CODE HERE

You'll also need to design a helper function keep_large_files_list that processes a list of file trees.

Wrap-Up

• How is processing trees different from processing lists?
• Why can't we use for loops on trees?