Patterns for structure · Chapter 14

Composite pattern

Treat a single object and a whole tree of objects the same way through one interface. Full Java and Python code, cycles, deep trees, caching sizes and when Visitor fits better.

IntermediateInterview priority: Medium50 min
On this page
  1. The problem: a type check at every node
  2. The idea: one interface for one thing and for many
  3. Build it step by step
  4. Extending it: a new kind of node
  5. Modern forms: sealed types and pattern matching
  6. Where this breaks
  7. Composite, Decorator, Chain of Responsibility: how they differ
  8. When not to use it
  9. Real uses
  10. In the interview
  11. Quiz

The problem: a type check at every node

A storage app shows how much space each folder uses. Folders hold files and other folders, to any depth. The first version walks the tree and checks the type of everything it meets:

long sizeOf(Object x) {
    if (x instanceof File f) {
        return f.bytes();
    } else if (x instanceof Folder d) {
        long total = 0;
        for (Object child : d.children()) total += sizeOf(child);
        return total;
    }
    throw new IllegalArgumentException("Unknown item: " + x);
}

It works. Then the team adds a tree printer, a search and a "count files" report, and each one copies the same instanceof ladder. Then product asks for zip archives that behave like folders. Now every one of those methods needs another else if, and the one somebody forgets throws at run time on the first zip it meets.

A tree, and the type checks that walk it

  1. Lots of things are trees: folders inside folders, boxes inside boxes, menus inside menus, teams inside departments. And we keep asking the same question of any part of the tree: how big is it?
  2. Without a pattern, code that walks the tree keeps asking “are you a file or a folder?”, and every new kind of item, like a zip archive, means another if/else in every place that walks the tree.

The underlying issue: the code that uses the tree has to know every kind of node, and the knowledge of "how a folder computes its size" lives outside the folder, copied into every caller.

The idea: one interface for one thing and for many

The Composite pattern gives every node in the tree the same interface. A single thing (a leaf, like a file) answers directly. A container (a composite, like a folder) answers by asking each of its children the same question and combining their answers. The caller asks the root once and never checks a type.

File and Folder share one interface; Folder holds Items

  1. The composite pattern gives every part one interface, Item, with size(). A File, called a leaf, returns its own size. A Folder, the composite, returns the sum of its children’s size(). The caller never needs to know which it has.

The four roles:

RoleIn this exampleResponsibility
Component (interface)ItemThe operations every node supports: size(), show()
LeafFileA node with no children; does the work itself
CompositeFolderHolds a list of components (leaves or composites) and delegates to them
Clientthe storage screenTalks only to Item, so one call covers a single file or a whole tree

The key detail on the class diagram is the arrow from Folder back to Item: a folder holds items, not files. That one choice is what lets folders nest inside folders to any depth.

Build it step by step

1. The component interface. Everything a caller may ask of any node.

2. The leaf. It answers from its own data.

3. The composite. It stores children as the interface type and loops over them. It does not know or care which children are folders.

4. The client builds a tree and asks the root.

Sizes are in MB to match the figures.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

// 1. The component
public interface Item {
    String name();
    long size();                    // MB
    void show(String indent);       // print this node and everything under it
}

// 2. The leaf
public final class File implements Item {
    private final String name;
    private final long size;

    public File(String name, long size) { this.name = name; this.size = size; }

    public String name() { return name; }
    public long size() { return size; }
    public void show(String indent) { System.out.println(indent + name + "  " + size + " MB"); }
}

// 3. The composite
public final class Folder implements Item {
    private final String name;
    private final List<Item> children = new ArrayList<>();

    public Folder(String name) { this.name = name; }

    public Folder add(Item child) { children.add(child); return this; }   // returns this for chaining
    public boolean remove(Item child) { return children.remove(child); }
    public List<Item> children() { return Collections.unmodifiableList(children); }

    public String name() { return name; }

    public long size() {
        long total = 0;
        for (Item child : children) total += child.size();   // file or folder: same call
        return total;
    }

    public void show(String indent) {
        System.out.println(indent + name + "/");
        for (Item child : children) child.show(indent + "  ");
    }
}

// 4. The client
public class Demo {
    public static void main(String[] args) {
        Folder photos = new Folder("Photos").add(new File("a.jpg", 3)).add(new File("b.jpg", 2));
        Folder docs   = new Folder("Docs").add(new File("cv.pdf", 1)).add(new File("notes.txt", 1));
        Folder home   = new Folder("Home").add(photos).add(docs).add(new File("song.mp3", 4));

        System.out.println(home.size());     // 11
        System.out.println(photos.size());   // 5: any subtree works the same way
        home.show("");
    }
}

Watch the recursion

One call on the root walks the whole tree

  1. Ask Home for its size and watch the recursion: each folder asks its children, files answer right away, and the totals add up on the way back.

home.size() calls photos.size(), which calls a.jpg (3) and b.jpg (2) and returns 5. docs.size() returns 1 + 1 = 2. song.mp3 returns 4. Home adds them: 5 + 2 + 4 = 11. Every node is visited exactly once, so the cost is O(n) for n nodes, and the call stack is as deep as the tree (here 3 frames).

Nothing in Folder.size() mentions files. Add a zip type, a symbolic link or a cloud placeholder, and Folder still works unchanged, as long as the new class implements Item.

Extending it: a new kind of node

A zip archive holds items like a folder but reports its compressed size. It is one new class:

public final class Zip implements Item {
    private final String name;
    private final List<Item> children = new ArrayList<>();
    private final double ratio;                       // e.g. 0.5 = half the size

    public Zip(String name, double ratio) { this.name = name; this.ratio = ratio; }
    public Zip add(Item child) { children.add(child); return this; }

    public String name() { return name; }
    public long size() {
        long raw = 0;
        for (Item c : children) raw += c.size();
        return Math.round(raw * ratio);
    }
    public void show(String indent) {
        System.out.println(indent + name + " (zip)");
        for (Item c : children) c.show(indent + "  ");
    }
}

File, Folder and every caller of size() are untouched: the open/closed principle again. Note that Zip and Folder now share the child-list code. If you get a third container type, pull that into an abstract Container base class.

Where do add and remove go?

This is the classic design question in Composite, and interviewers like it.

ChoiceHowGood atWeak at
Safety (used above)add/remove exist only on FolderThe compiler stops you adding a child to a fileTo add a child you must hold a Folder, not an Item, so some callers need a cast or a type check
Transparencyadd/remove on Item; File throws UnsupportedOperationExceptionEvery node looks identical, so a tree editor never checks typesA mistake that the compiler could have caught becomes a run-time exception

The original Gang of Four book leaned towards transparency; most modern code, and most interviewers, prefer safety, because a type error found at compile time is cheaper than one found in production. Java's own collections show the transparency cost: List.of(...) returns a list whose add throws at run time.

Modern forms: sealed types and pattern matching

When the set of node types is fixed and you keep adding operations (size, count, search, export to JSON), you can turn the design around. Java 21 sealed interfaces with records, or Python dataclasses with match, let one function handle each kind of node, and the compiler checks that you handled them all.

import java.util.List;

sealed interface Node permits Leaf, Branch {}
record Leaf(String name, long size) implements Node {}
record Branch(String name, List<Node> children) implements Node {}

final class Sizes {
    static long size(Node n) {
        return switch (n) {                    // exhaustive: no default needed
            case Leaf l   -> l.size();
            case Branch b -> b.children().stream().mapToLong(Sizes::size).sum();
        };
    }
}

This is the same tree, built the other way round. It is the well-known trade-off sometimes called the expression problem:

  • Classic Composite (methods on each class): adding a new node type is one new class; adding a new operation means editing every class.
  • Sealed types + switch (or the Visitor pattern in older Java): adding a new operation is one new function; adding a new node type means editing every switch (the compiler tells you where).

Pick by asking which will change more often. A UI toolkit gains widget types often: classic Composite. A compiler's syntax tree has a fixed grammar and gains passes (type check, optimise, print): sealed types or Visitor.

Where this breaks

// Iterative walk: no recursion depth limit. Requires knowing which nodes have children.
static long totalSize(Item root) {
    long total = 0;
    Deque<Item> stack = new ArrayDeque<>();
    Set<Item> seen = Collections.newSetFromMap(new IdentityHashMap<>());   // guards cycles and sharing
    stack.push(root);
    while (!stack.isEmpty()) {
        Item node = stack.pop();
        if (!seen.add(node)) continue;
        if (node instanceof Folder f) f.children().forEach(stack::push);
        else total += node.size();
    }
    return total;
}

Notice the trade: the iterative version is robust, but the type check is back. A common compromise is to give Item a children() method that returns an empty list for leaves, so the walker never needs instanceof.

Caching sizes in a big tree

Recomputing size() walks the whole subtree, O(n). For a tree of 2 million files shown in a UI that refreshes every second, that is too slow. Store a cached size in each folder and keep it correct:

  • Each node keeps a parent pointer.
  • When a file is added, removed or resized, walk up the parent chain and adjust each ancestor's cached total by the difference (or mark them dirty and recompute lazily on the next read).
  • That update costs O(depth) instead of O(n) per read.

The cost is new invariants: the parent pointer and the parent's child list must always agree, and moving a node means updating both old and new ancestors. Concurrent edits need a lock over the path, or a single writer thread. This is exactly what file-system quota trackers and IDE project views do.

Composite, Decorator, Chain of Responsibility: how they differ

All three put objects inside objects that share an interface, so they look alike on a class diagram.

CompositeDecoratorChain of Responsibility
HoldsMany childrenExactly one wrapped objectOne next handler
PurposeTreat a group like a single item; combine resultsAdd behaviour around one objectPass a request along until someone handles it
A call goes toEvery child, results combinedThe wrapped object, with extra work before or afterOne handler at a time; usually stops at the first that handles it
ShapeA treeA line of wrappersA line of handlers
ExampleFolder size, UI panel layoutBufferedInputStream(new FileInputStream(f))Middleware, approval levels

Two more relatives: Iterator is often paired with Composite to walk the tree without exposing its structure, and Interpreter is Composite applied to a grammar (an expression (2 + 3) * 4 is a tree of number leaves and operator composites).

When not to use it

Real uses

  • UI toolkits: in Java Swing, Container extends Component, so a JPanel can hold buttons and other panels; Android's ViewGroup extends View. Layout and drawing recurse down the tree.
  • The browser DOM: every element is a Node, and elements contain nodes. React and other UI libraries render component trees the same way.
  • Test frameworks: JUnit 3's TestSuite and TestCase both implement Test, so a suite of suites runs with one run() call.
  • Compilers and query engines: syntax trees and query plans are composites of operator nodes.
  • Business data: bills of materials (a car is parts and sub-assemblies), org charts (sum a department's salaries), product bundles (a bundle's price is the sum of its items and sub-bundles).

In the interview

Your turn: an expression tree

Build a calculator that evaluates (2 + 3) * 4 from a tree. Sketch the classes and write evaluate(). Then say what you would change to support -x (one operand) and how you would add a print() that produces ((2 + 3) * 4).

Compare with our answer
public interface Expr {
    double evaluate();
    String print();
}

public record Num(double value) implements Expr {
    public double evaluate() { return value; }
    public String print() { return String.valueOf(value); }
}

public record BinOp(char op, Expr left, Expr right) implements Expr {
    public double evaluate() {
        double a = left.evaluate(), b = right.evaluate();
        return switch (op) {
            case '+' -> a + b;
            case '-' -> a - b;
            case '*' -> a * b;
            case '/' -> {
                if (b == 0) throw new ArithmeticException("division by zero");
                yield a / b;
            }
            default -> throw new IllegalArgumentException("Unknown operator: " + op);
        };
    }
    public String print() { return "(" + left.print() + " " + op + " " + right.print() + ")"; }
}

public record Neg(Expr inner) implements Expr {          // one operand: still a composite
    public double evaluate() { return -inner.evaluate(); }
    public String print() { return "-" + inner.print(); }
}

// Client
Expr e = new BinOp('*', new BinOp('+', new Num(2), new Num(3)), new Num(4));
System.out.println(e.evaluate());   // 20.0
System.out.println(e.print());      // ((2.0 + 3.0) * 4.0)

A strong answer mentions: one Expr interface · numbers as leaves and operators as composites holding Expr children (not Num) · recursion in evaluate() with no type checks · a unary operator as a composite with one child · division by zero and unknown operators handled · that adding many new operations (print, simplify, differentiate) is where Visitor or sealed types start to pay off.

Composite on one page
  • Intent: let clients treat one object and a tree of objects the same way, through one interface.
  • Roles: Component interface · Leaf (no children, answers directly) · Composite (holds List<Component>, delegates and combines) · Client (talks only to Component).
  • The key arrow: a composite holds components, not leaves, so trees nest to any depth.
  • Cost: one call on the root is O(n) nodes and O(depth) stack frames.
  • Safety vs transparency: add() only on the composite (compile-time safe, the usual choice) or on every node (uniform, leaves throw).
  • Breaks on: cycles (reject in add()), shared children (double counting; use a seen-set), very deep trees (explicit stack), big trees read often (cached sizes updated up the parent chain).
  • Expression problem: classic Composite makes new node types cheap; sealed types/Visitor make new operations cheap.
  • Seen in: Swing Container, Android ViewGroup, the DOM, JUnit TestSuite, syntax trees, bills of materials.
Your turn: the requirement changes

Your file-system model now holds 2 million files. The UI shows the size of every visible folder and refreshes once a second, and users move folders around by dragging. Recomputing size() on each refresh is too slow, and one user crashed the app by dropping a folder into its own subfolder. What do you change?

Compare with our answer
  • Give every node a parent pointer, set in add() and cleared in remove().
  • Cache each folder's total. On add, remove or resize, walk up the parents and apply the size difference: O(depth) per change, O(1) per read.
  • A move is a remove from the old parent (subtract up the old chain) and an add to the new parent (add up the new chain).
  • In add(), walk up from the target folder through its parents; if you reach the folder being moved, reject the move as a cycle.
  • If edits can come from several threads, serialise them (one writer, or a lock), because a half-applied update leaves ancestors with wrong totals.

A strong answer mentions: parent pointers · cached totals updated by the difference up the chain · moves as remove plus add · cycle check by walking ancestors · O(depth) updates and O(1) reads · a note on thread safety.

Interactive labPractise it: grow the tree and add a new kind of itemOpens in the ByteAtlas lab. Your progress is saved in this browser.
Check what stuck

1. A UI framework has buttons, text boxes and panels, and panels can contain any widget, including other panels. Every widget must layout() and draw(). Which design fits best?

2. A team puts add(Item) on the Item interface so a tree editor can treat every node alike. What is the main cost of this choice?

3. A user drags their Projects folder into Projects/Archive. The next call to projects.size() crashes with a stack overflow. What is the right fix?

4. A product catalogue models bundles as composites of products and smaller bundles. One gift card is in two different bundles inside the same holiday mega-bundle, and its price is counted twice. What is happening?

5. A compiler's syntax tree has a fixed set of node types, but the team adds a new pass (type check, optimise, pretty-print, lint) every few weeks. Which structure makes those changes cheapest?

6. A folder view shows the size of every folder in a tree of 2 million files and refreshes every second. What is the best way to make it fast?

7. Which pair describes the difference between Composite and Decorator?

Score 60% or more and the lesson is marked complete.

Passing the quiz also marks it complete. Progress is saved in this browser only.