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

Your 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 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. Object costs you nothing here. childNames never looks inside a child.

3. Watch where it goes, and the real cost

Reading a child back out means asking what it actually is first. 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());
}

Now notice what nothing is stopping. A third kind of value can end 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)

That 42 compiled without a single warning. addChild takes an Object. 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 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 everything 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

Look at what makes this work.

DirectoryNode holds Node children, and each of those children can itself be a DirectoryNode holding more children. That 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 — 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);
                                    ^

That 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 holds.

corpus/file-system's own reference solution uses exactly this shape — a sealed interface Node, a FileNode, a DirectoryNode, and 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 say node.operation() without checking what it has.

Node 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, 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 makes that switch exhaustive — the exact mechanism chapter 3.5 introduced on an enum. The compiler refuses to build the method if a case is missing, and refuses again the moment a third Node implementation exists anywhere without a matching case.

So how do you choose between the two? 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, where you do not want a new method forced onto Node for every caller that 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 is a Map from name to content. That is the whole design.

Build a Node hierarchy in case directories arrive later and you have written a guess dressed as design. This app's grading standard scores it over-engineered (premature interface), the same tag every earlier chapter's speculative interface earned.

Your 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. That 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 free too. Iterable already supplies a default spliterator(), and so StreamSupport.stream(root.spliterator(), false) works with no further code. That is how the .filter(n -> n instanceof FileNode).count() call above counted the files.

Now the cost hiding underneath that convenience. Watch it fire.

TreeMap keeps an internal counter of every structural change made to it. Each iterator it hands out remembers that counter's value at the moment it was created, and checks it has not moved on every call to next().

So 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 moves the counter. The very next call to next() notices the mismatch and throws.

That is not a bug in TreeMap, and not a bug 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.

Your fix is simple: never mutate the collection you are for-each-ing over. Collect what needs adding into a separate list, then add it once the loop has finished.

Why this matters in an interview

Composite is one of the few patterns where your interviewer's real question is not "did you build the tree correctly". Most candidates manage that.

The real question is whether you made the illegal states unrepresentable. sealed answers that directly.

Iterator gets graded on a different axis. Do you know that the convenience of for-each comes with a rule about not mutating what you are walking? Can you say why, instead of 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 →