Practice: adding up a folder tree

record Folder(String name, List<Integer> files, List<Folder> folders) {}

int totalSize(Folder folder) {
    int size = 0;
    for (int file : folder.files()) {
        size += file;
    }
    for (Folder inner : folder.folders()) {
        size += totalSize(inner);
    }
    return size;
}

void main() {
    Folder root = new Folder("root", List.of(10, 20), List.of(
            new Folder("docs", List.of(100), List.of()),
            new Folder("images", List.of(300, 40), List.of(
                    new Folder("raw", List.of(1000), List.of())))));
    IO.println(totalSize(root));
}

Its own files, plus whatever each folder inside reports. No base case is written out: a folder with no folders inside simply never enters the second loop.

record Folder(String name, List<Integer> files, List<Folder> folders) {}

int fileCount(Folder folder) {
    int count = folder.files().size();
    for (Folder inner : folder.folders()) {
        count += fileCount(inner);
    }
    return count;
}

void main() {
    Folder root = new Folder("root", List.of(10, 20), List.of(
            new Folder("docs", List.of(100), List.of()),
            new Folder("images", List.of(300, 40), List.of(
                    new Folder("raw", List.of(1000), List.of())))));
    IO.println(fileCount(root));
}

The same shape as step 1, with size() in place of adding the sizes up. Most recursive methods over a tree look like this.

record Folder(String name, List<Integer> files, List<Folder> folders) {}

int depth(Folder folder) {
    int deepest = 0;
    for (Folder inner : folder.folders()) {
        int innerDepth = depth(inner);
        if (innerDepth > deepest) {
            deepest = innerDepth;
        }
    }
    return 1 + deepest;
}

void main() {
    Folder root = new Folder("root", List.of(10, 20), List.of(
            new Folder("docs", List.of(100), List.of()),
            new Folder("images", List.of(300, 40), List.of(
                    new Folder("raw", List.of(1000), List.of())))));
    IO.println(depth(root));
}

One for this folder, plus the deepest of what is inside—not how many are inside. On this tree those two happen to agree everywhere, so Check's wide and deep cases are there to pull them apart.

record Folder(String name, List<Integer> files, List<Folder> folders) {}

ArrayList<String> folderNames(Folder folder) {
    ArrayList<String> names = new ArrayList<>();
    names.add(folder.name());
    for (Folder inner : folder.folders()) {
        names.addAll(folderNames(inner));
    }
    return names;
}

void main() {
    Folder root = new Folder("root", List.of(10, 20), List.of(
            new Folder("docs", List.of(100), List.of()),
            new Folder("images", List.of(300, 40), List.of(
                    new Folder("raw", List.of(1000), List.of())))));
    IO.println(folderNames(root));
}

This folder first, then each subtree in full: addAll puts every name a folder inside gives back on the end. The version that lists only the folders one level down misses raw entirely.

record Folder(String name, List<Integer> files, List<Folder> folders) {}

int fileCount(Folder folder) {
    int count = folder.files().size();
    for (Folder inner : folder.folders()) {
        count += fileCount(inner);
    }
    return count;
}

int largestFile(Folder folder) {
    int biggest = 0;
    for (int size : folder.files()) {
        if (size > biggest) {
            biggest = size;
        }
    }
    for (Folder inner : folder.folders()) {
        int innerBiggest = largestFile(inner);
        if (innerBiggest > biggest) {
            biggest = innerBiggest;
        }
    }
    return biggest;
}

void main() {
    Folder root = new Folder("root", List.of(10, 20), List.of(
            new Folder("docs", List.of(100), List.of()),
            new Folder("images", List.of(300, 40), List.of(
                    new Folder("raw", List.of(1000), List.of())))));
    if (fileCount(root) > 0) {
        IO.println(largestFile(root));
    } else {
        IO.println("No files");
    }
}

Start at 0, and let every file of its own and every folder's answer beat it. A folder inside with no files answers 0, which beats nothing. Starting at 0 is safe because the caller has checked that a file exists somewhere: a tree with no files would answer 0 as well, the same as a tree whose only file is empty, and only the caller's fileCount(root) > 0 tells those apart.

record Folder(String name, List<Integer> files, List<Folder> folders) {}

Folder findFolder(Folder folder, String name) {
    if (folder.name().equals(name)) {
        return folder;
    }
    for (Folder inner : folder.folders()) {
        Folder found = findFolder(inner, name);
        if (found != null) {
            return found;
        }
    }
    return null;
}

void main() {
    Folder root = new Folder("root", List.of(10, 20), List.of(
            new Folder("docs", List.of(100), List.of()),
            new Folder("images", List.of(300, 40), List.of(
                    new Folder("raw", List.of(1000), List.of())))));
    IO.println(findFolder(root, "raw"));
    IO.println(findFolder(root, "nowhere"));
}

Stop as soon as something is found, and keep looking otherwise: null from a folder inside means "not in there," so the loop goes on to the next one. Names compare with .equals. Checking only the folders one level down finds docs and images but never raw, which is two levels down.

record Folder(String name, List<Integer> files, List<Folder> folders) {}

ArrayList<Integer> allSizes(Folder folder) {
    ArrayList<Integer> sizes = new ArrayList<>(folder.files());
    for (Folder inner : folder.folders()) {
        sizes.addAll(allSizes(inner));
    }
    return sizes;
}

void main() {
    Folder root = new Folder("root", List.of(10, 20), List.of(
            new Folder("docs", List.of(100), List.of()),
            new Folder("images", List.of(300, 40), List.of(
                    new Folder("raw", List.of(1000), List.of())))));
    IO.println(allSizes(root));
}

new ArrayList<>(folder.files()) copies the folder's own sizes into a new list that can grow; the folder's own list, made by List.of, cannot, and should not. Then each folder inside adds its sizes on the end, in step 4's order.

record Folder(String name, List<Integer> files, List<Folder> folders) {}

int totalSize(Folder folder) {
    int size = 0;
    for (int file : folder.files()) {
        size += file;
    }
    for (Folder inner : folder.folders()) {
        size += totalSize(inner);
    }
    return size;
}

ArrayList<String> sizeReport(Folder folder) {
    ArrayList<String> lines = new ArrayList<>();
    lines.add(folder.name() + ": " + totalSize(folder));
    for (Folder inner : folder.folders()) {
        lines.addAll(sizeReport(inner));
    }
    return lines;
}

void main() {
    Folder root = new Folder("root", List.of(10, 20), List.of(
            new Folder("docs", List.of(100), List.of()),
            new Folder("images", List.of(300, 40), List.of(
                    new Folder("raw", List.of(1000), List.of())))));
    for (String line : sizeReport(root)) {
        IO.println(line);
    }
}

Two recursions working together: sizeReport walks the tree, and totalSize walks each subtree again to add it up. Slow on a big tree, and perfectly clear on this one.