3.10 Composite and Iterator: trees and traversal

Patterns you will actually be asked for · chapter 28 of 33

Composite and Iterator: trees and traversal

Chapter 3.10 · Part 3, Patterns you will actually be asked for · about 30 minutes

What you need before this chapter: Part 1 in full, especially collections (1.6). Part 2 in full, especially single responsibility (2.4). Chapter 3.5, State, for sealed interfaces and exhaustive switch, which this chapter uses on a recursive structure instead of a fixed set of states.

When you finish this chapter you will be able to:

Recognise when a "this or that" structure held in a general-purpose type is inviting a bug the compiler could have caught
Write a sealed interface with two implementations that can contain each other, forming a tree of any depth in two classes
Implement Iterable so a type works in a for-each loop and with streams, with no extra method calls at the call site
Reproduce ConcurrentModificationException for real, and explain the mechanism that throws it

1. The situation

An in-memory file system needs to answer one question: given a directory, what is inside it. A directory is a name mapped to whatever is under that name, so a Map is the obvious way to hold one.

final class DirectoryNode {
    private final TreeMap<String, Object> children = new TreeMap<>();

    void addChild(String name, Object node) {
        children.put(name, node);
    }

    List<String> childNames() {
        return List.copyOf(children.keySet());
    }
}

Object as the value type is an honest description of the actual problem: a child can be a file, holding text, or another directory, holding more children of its own.

2. Naive code that is fine

javac Step1.java
java Step1

[notes.txt, photos]

For listing names, this already works, and Object costs nothing here because childNames never looks inside a child at all.

3. Watch where it goes, and the real cost

Reading a child back out means asking what it actually is before doing anything with it, since Object remembers nothing about its own contents.

static String describe(Object child) {
    if (child instanceof String) return "file";
    if (child instanceof DirectoryNode) return "directory";
    throw new IllegalStateException("unknown child type: " + child.getClass());
}

Nothing stops a third kind of value from ending up in the same map.

root.addChild("size-cache", 42);
System.out.println(describe(root.child("size-cache")));

javac Step2.java
java Step2

file
directory
Exception in thread "main" java.lang.IllegalStateException: unknown child type: class java.lang.Integer
	at Step2.describe(Step2.java:21)
	at Step2.main(Step2.java:35)

The 42 compiled without a single warning, because addChild takes an Object, and an int boxes into one without complaint. The mistake only became visible when describe finally ran, months of possible use later, on whichever caller happened to hit that particular child first.

4. The move

Give files and directories a common type that names exactly the two things a node can be, and closes the door on anything else.

sealed interface Node permits FileNode, DirectoryNode {}

final class FileNode implements Node {
    private String content;

    FileNode(String content) { this.content = content; }

    String content() { return content; }
}

final class DirectoryNode implements Node {
    private final TreeMap<String, Node> children = new TreeMap<>();

    void addChild(String name, Node node) {
        children.put(name, node);
    }

    Node child(String name) { return children.get(name); }
}

javac Step3.java
java Step3

[notes.txt, photos]
file
directory

DirectoryNode holds Node children, and each of those children can itself be a DirectoryNode holding more children, which is what lets a tree of any depth live in exactly two classes. sealed closes the set: nothing outside FileNode and DirectoryNode can ever implement Node, so the compiler guarantees there is no third kind to worry about, rather than a runtime check discovering one after the fact. Try section 3's mistake again.

root.addChild("size-cache", 42);

javac Step3Bad.java

Step3Bad.java:21: error: incompatible types: int cannot be converted to Node
        root.addChild("size-cache", 42);
                                    ^

This is the Composite pattern: FileNode is a leaf, DirectoryNode is a container that can hold more leaves or more containers, and both answer to the one type a caller actually needs to hold onto. corpus/file-system's own reference solution uses exactly this shape: a sealed interface Node, a FileNode, and a DirectoryNode, with one class, Nodes, holding the single switch that asks what kind a node is.

5. What modern Java changes here

The original catalogue answers "what kind of node is this" with one virtual method every node type overrides, so a caller can ask node.operation() without checking which kind it has. Node above takes a different route: nothing forces every question about a node to become a method on Node itself. A switch over the sealed type answers it instead, in the one place that needs to ask.

static String describe(Node node) {
    return switch (node) {
        case FileNode f -> "file";
        case DirectoryNode d -> "directory";
    };
}

sealed is what turns that switch exhaustive, the exact mechanism chapter 3.5 introduced on an enum. The compiler refuses to build this method if a case is missing, and refuses to build it at all once a third Node implementation exists anywhere without a matching case. Virtual dispatch suits an operation every node type genuinely has to answer, the way du() walking to a total size does. Pattern matching suits a question asked occasionally from outside the hierarchy, with no new method forced onto Node for every caller that only ever asks it once.

6. When naming it is wrong

A file system with a fixed depth known in advance, or with no subdirectories at all, does not need a common interface. A flat list of files and nothing more is a Map from name to content, in full. Building a Node hierarchy in case directories arrive later is a guess dressed as design, and this app's grading standard scores that guess as over-engineered (premature interface), the same tag every earlier chapter's speculative interface has earned.

The threshold: reach for this once a real recursive structure exists, where a container can hold another container of the same kind, and code needs to treat a leaf and a container the same way for at least one operation. A structure that is provably flat, with nesting nobody has asked for, does not meet that bar.

Your turn

Write sizeOf(Node): the total size of a file, or the sum of everything inside a directory, recursively.

The answer.

static long sizeOf(Node node) {
    return switch (node) {
        case FileNode f -> f.content().length();
        case DirectoryNode d -> {
            long total = 0;
            for (Node child : d.children()) {
                total += sizeOf(child);
            }
            yield total;
        }
    };
}

javac Step4.java
java Step4

total size: 23

The DirectoryNode case calls sizeOf on each of its own children, including any that are themselves directories, which is what lets one method answer the question at any depth without knowing in advance how deep the tree goes.

Going deeper

Node above needed a getter to expose its children to a for loop. There is a better way: implement java.lang.Iterable, and the language's own for-each syntax starts working on DirectoryNode directly, with no method call at the site that uses it.

final class DirectoryNode implements Node, Iterable<Node> {
    private final TreeMap<String, Node> children = new TreeMap<>();

    void addChild(String name, Node node) {
        children.put(name, node);
    }

    @Override
    public Iterator<Node> iterator() {
        return children.values().iterator();
    }
}

for (Node child : root) {
    System.out.println("saw: " + child.getClass().getSimpleName());
}

javac Step5.java
java Step5

saw: FileNode
saw: DirectoryNode
saw: FileNode
file count: 2

Streams come along for free too. Iterable already supplies a default spliterator(), so StreamSupport.stream(root.spliterator(), false) works with no further code, which is how the .filter(n -> n instanceof FileNode).count() call above counted the files.

This convenience has a real cost hiding underneath it, and it is worth seeing the cost fire for real. TreeMap keeps an internal counter of every structural change made to it. Each iterator it hands out remembers the counter's value at the moment it was created, and checks that the value has not moved every time next() is called. Mutate the directory while a for-each loop is still walking it.

for (Node child : root) {
    System.out.println("visiting a child");
    root.addChild("c.txt", new FileNode("c"));
}

javac Step6Bad.java
java Step6Bad

visiting a child
Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.TreeMap$PrivateEntryIterator.nextEntry(TreeMap.java:1521)
	at java.base/java.util.TreeMap$ValueIterator.next(TreeMap.java:1566)
	at Step6Bad.main(Step6Bad.java:30)

The first child prints, then addChild inside the loop body moves the counter, and the very next call to next() notices the mismatch and throws. This is not a bug in TreeMap or in DirectoryNode. It is a deliberate trade a "fail-fast" iterator makes: rather than silently walking a structure that changed shape underneath it, possibly skipping an entry or visiting one twice with no sign anything went wrong, it stops immediately and loudly. The fix is never to mutate the collection you are for-each-ing over. Collect what needs adding into a separate list first, then add it once the loop has finished.

Why this matters in an interview

Composite is one of the few patterns where the interviewer's real question is not "did you build the tree correctly," which most candidates manage, but "did you make the illegal states unrepresentable," which sealed answers directly. Iterator is graded on a different axis. Do you know the convenience of for-each comes with a rule about not mutating what you are walking, and can you say why, rather than only knowing that a stack trace with ConcurrentModificationException in it means something went wrong somewhere?

Next: Part 3 is complete. Chapter 4.1, Reading a vague prompt without panicking, starts Part 4. The patterns in this part and the SOLID habits from Part 2 stop being separate topics there. They become the toolkit you reach into during a full, timed design round.

← 3.9 Singleton, and why interviewers hope you avoid it · All chapters · 4.1 Reading a vague prompt without panicking →