Composite pattern

Composite builds a tree out of objects that share one interface. So a whole tree and a single object answer the same questions, in the same way. A folder and a file both have a size. A bundle and a product both have a price. A layout container and a line of text both have a height. The caller asks, and never checks which kind it holds.

You use it every day. In the DOM, an element and a text node are both a Node. In Java’s AWT, Container extends Component. On Android, a ViewGroup is a View. And every compiler holds its program as a syntax tree. This page builds in three steps. First, folder sizes. Then store bundles, with real pricing rules and a tree that people edit. Then a large layout tree that has to stay fast while it changes.

The idea in one picture

Scroll or pinch to zoom, drag to pan

Explorer asks size() and can't tell a single file from a whole tree. A file knows its size; a folder asks its children and adds up.

What makes this hard

• A composite is a component, and has components. The recursion lives inside the composite, once. So callers never write “if it’s a folder, loop. If it’s a file, return”.
• Uniform treatment has a price, and it shows up in one question: where do add and remove go? On the shared interface, every node accepts them and a leaf must refuse at run time. Only on the composite, the compiler stops misuse but callers sometimes have to check the type.
• A tree has invariants the interface can’t express: one parent per node, no cycles, totals that match their children. Most Composite bugs break one of these, not the interface.

The shape

Every composite has the same parts:

• The component is the interface callers use, for example Node with size().
• Leaves implement it directly, for example File. They have no children.
• The composite implements it too, and holds a list of components. Its version of each operation calls the same operation on its children and combines the results.

The general shape

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation

The arrow from Composite back to Component, with a *, is the whole pattern. A composite’s children are components, so a child can be a leaf or another composite, to any depth. The client has one arrow, to the interface, so it can’t tell a leaf from a tree of a thousand nodes.

This diagram puts add and remove only on the composite. The Gang of Four book put them on the component instead, so that every node looks the same. Both are in use, and the Medium level shows what each one costs.

Worked examples

EasyFolder sizesMediumStore bundlesHardA document layout tree

Easy

Folder sizes

• The basic shape
• One interface for leaf and tree
• Recursion in one place

A cloud drive shows the size of every folder in its sidebar and a “storage used” bar for the whole account. Folders hold files and other folders, to any depth. Next quarter the drive adds shortcuts: a link to a file somewhere else, which takes 1 KB and must not count its target’s size.

Without the pattern

File and Folder are unrelated classes, and each operation walks the tree by asking every item what it is:

JExplorer.javaPylink.pyC#Program.csGolink.goTSlink.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

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

// Two unrelated classes. Nothing in the types says a folder holds files and folders.
class File {
    final String name;
    final int kb;
    File(String name, int kb) { this.name = name; this.kb = kb; }
}

class Folder {
    final String name;
    // Object, because there is no common type. Anything can go in, even a String.
    final List<Object> items = new ArrayList<>();
    Folder(String name) { this.name = name; }
}

// Added later: a shortcut stores a path, not a copy, so it takes 1 KB on disk.
class Link {
    final String name;
    Link(String name) { this.name = name; }
}

class Explorer {
    // Every operation re-implements the walk and asks each item "what are you?".
    static int size(Object item) {
        if (item instanceof File f) return f.kb;
        if (item instanceof Folder d) {
            int total = 0;
            for (Object child : d.items) total += size(child);
            return total;
        }
        // Link was added after this was written, and nobody updated it.
        throw new IllegalArgumentException("unknown item type " + item.getClass().getSimpleName());
    }

    // A second operation, a second copy of the same branching and the same recursion.
    static int countFiles(Object item) {
        if (item instanceof File || item instanceof Link) return 1;
        if (item instanceof Folder d) {
            int total = 0;
            for (Object child : d.items) total += countFiles(child);
            return total;
        }
        throw new IllegalArgumentException("unknown item type " + item.getClass().getSimpleName());
    }
}

class Main {
    public static void main(String[] args) {
        Folder docs = new Folder("docs");
        docs.items.add(new File("resume.pdf", 120));
        docs.items.add(new File("taxes-2025.pdf", 840));
        Folder home = new Folder("home");
        home.items.add(docs);
        home.items.add(new File("notes.txt", 4));

        System.out.println("home: " + Explorer.size(home) + " KB, " + Explorer.countFiles(home) + " files"); // home: 964 KB, 3 files

        // The new type works in the one function that was updated...
        home.items.add(new Link("resume.lnk"));
        System.out.println("files: " + Explorer.countFiles(home)); // files: 4

        // ...and fails at run time in the one that was missed.
        try {
            Explorer.size(home);
        } catch (IllegalArgumentException e) {
            System.out.println("size failed: " + e.getMessage()); // size failed: unknown item type Link
        }
    }
}

Every operation repeats the same branching and the same recursion. A folder holds a list of Object, so the compiler can’t stop a string going in. When Link arrived, countFiles was updated and size was missed, and the bug only appears when a user with a shortcut opens the sidebar.

With Composite

Give files and folders one interface, Node. A file returns its own size. A folder returns the sum of its children’s sizes, and it doesn’t care what kind of node each child is:

Easy: a folder is a node that holds nodes

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation

Add and delete files and watch every folder above them change. The right panel lists the size() calls that one home.size() makes, each folder in the order it returned:

Selected: home/

Add a 500 KB file hereDeleteReset

Explorer

What home.size() did, folders in the order they returned

Click a name to select it. Folders open and close with the arrow.

JMain.javaPyfolder.pyC#Program.csGofolder.goTSfolder.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

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

// The component: what a file and a folder have in common. Callers only ever hold a Node,
// so they treat one file and a whole tree of folders the same way.
interface Node {
    String name();

    // Size in KB. A file knows its own; a folder asks its children.
    int size();

    void print(String indent);
}

// A leaf: no children. Its size is a stored number.
class File implements Node {
    private final String name;
    private final int kb;
    File(String name, int kb) { this.name = name; this.kb = kb; }
    public String name() { return name; }
    public int size() { return kb; }
    public void print(String indent) { System.out.println(indent + name + " " + kb + " KB"); }
}

// A new kind of leaf is one class. Every operation on the tree works with it unchanged.
class Shortcut implements Node {
    private final String name;
    Shortcut(String name) { this.name = name; }
    public String name() { return name; }
    public int size() { return 1; } // stores a path, not a copy of the target
    public void print(String indent) { System.out.println(indent + name + " 1 KB"); }
}

// The composite: it IS a Node and HAS Nodes. Its size is the sum of its children's, and it
// doesn't care whether a child is a file, a shortcut or another folder.
class Folder implements Node {
    private final String name;
    private final List<Node> children = new ArrayList<>();
    Folder(String name) { this.name = name; }

    // Child management lives on the composite only: a file can't be asked to hold anything.
    Folder add(Node child) { children.add(child); return this; }
    void remove(Node child) { children.remove(child); }

    public String name() { return name; }

    // The recursion is here, once, instead of in every caller. Nothing is cached: every call
    // walks the whole subtree, which is fine for a few hundred files (the Hard level fixes it).
    public int size() {
        int total = 0;
        for (Node child : children) total += child.size();
        return total;
    }

    public void print(String indent) {
        System.out.println(indent + name + "/ " + size() + " KB");
        for (Node child : children) child.print(indent + "  ");
    }
}

class Main {
    public static void main(String[] args) {
        File taxes = new File("taxes-2025.pdf", 840);
        Folder docs = new Folder("docs").add(new File("resume.pdf", 120)).add(taxes);
        Folder year = new Folder("2026").add(new File("beach.jpg", 2400)).add(new File("dog.jpg", 1800));
        Folder photos = new Folder("photos").add(year).add(new File("avatar.png", 300));
        File notes = new File("notes.txt", 4);
        Folder home = new Folder("home").add(docs).add(photos).add(notes).add(new Shortcut("resume.lnk"));

        home.print("");
        // home/ 5465 KB
        //   docs/ 960 KB
        //     resume.pdf 120 KB
        //     taxes-2025.pdf 840 KB
        //   photos/ 4500 KB
        //     2026/ 4200 KB
        //       beach.jpg 2400 KB
        //       dog.jpg 1800 KB
        //     avatar.png 300 KB
        //   notes.txt 4 KB
        //   resume.lnk 1 KB

        // One file or a whole folder: the caller asks the same question the same way.
        for (Node n : List.of(notes, photos)) {
            System.out.println(n.name() + ": " + n.size() + " KB");
        }
        // notes.txt: 4 KB
        // photos: 4500 KB

        // A change deep in the tree shows up in every ancestor, because sizes are computed, not stored.
        year.add(new File("sunset.jpg", 2100));
        System.out.println("after adding sunset.jpg: home " + home.size() + " KB"); // after adding sunset.jpg: home 7565 KB
        docs.remove(taxes);
        System.out.println("after deleting taxes-2025.pdf: home " + home.size() + " KB"); // after deleting taxes-2025.pdf: home 6725 KB
    }
}

What to notice

• Callers hold a Node. notes.size() and photos.size() are the same call. Code that shows a size, sorts by size or checks a quota works for one file or a whole tree without a branch.
• The recursion is written once. Folder.size() is the only place that loops over children. In the version without the pattern, every operation had its own copy.
• A new kind of node is one class. Shortcut implements Node, and size, print and anything written later handle it with no edits. That is the open-closed principle applied to a tree.
• Only folders have add and remove. A file can’t be asked to hold anything, because the method isn’t there. The Medium level looks at the other choice.
• Sizes are computed, never stored. So they can’t go stale. A change deep in the tree shows up in every ancestor, with no code to update them. The cost is time. print calls size() on every folder, so each file is summed once for every folder above it. That’s fine for a few hundred files, and too slow for a large tree. That’s the Hard level’s problem.

TradeoffComputing sizes on demand

We gain

No stored totals to keep in sync. Adding, removing or moving a file can’t leave a folder showing the wrong size, and there’s no update code to forget.

We give up

Every call walks the whole subtree. Asking each folder for its size, as a sidebar does, walks the same files again and again. Large or often-read trees need caching, and caching brings invalidation.

Interviewer

Design the classes for a file browser. Folders hold files and other folders, and we need to show the size of any folder.

What they are testing

Whether you give files and folders one interface with size(). Whether you put the loop over children in the folder. And whether you keep callers free of type checks. The red flag is an instanceof chain in a helper. So is a size field on each folder, updated by hand from every place that adds a file.

Say this out loud

Files and folders share one interface, Node, with size(). A file returns its own size. A folder holds a list of Nodes, and returns the sum of their sizes. It doesn’t care whether a child is a file or another folder. Callers ask any node the same way.

Medium

Store bundles

• Real rules over the tree
• Transparency or safety
• Parent pointers and moves
• Refusing cycles
• New operations without new methods

An electronics store sells bundles. A merchandiser builds them in an admin tool. A “Home office” bundle holds a laptop, a “Desk setup” bundle, an “Accessories” bundle and a gift card. Each bundle has its own discount. The pricing rules are real ones:

• Gift cards and extended warranties are never discounted. Warranties are priced by the insurer, and a discounted gift card is free money.
• Discounts don’t stack. An item gets the discount of the innermost bundle it’s in. The outer bundle discounts only what nobody below it has discounted.

Merchandisers move items between bundles all day, by dragging them in the admin tool.

Without the pattern

Take the Easy level’s shape and use it as is: an interface, a leaf, and a composite that sums its children and applies its discount:

JMain.javaPybundle.pyC#Program.csGobundle.goTSbundle.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

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

// The Easy shape, carried over: an interface, a leaf and a composite that sums its children.
interface Item { long cents(); }

class Product implements Item {
    private final long cents;
    Product(long cents) { this.cents = cents; }
    public long cents() { return cents; }
}

class Bundle implements Item {
    private final String name;
    private final int percentOff;
    final List<Item> items = new ArrayList<>();
    Bundle(String name, int percentOff) { this.name = name; this.percentOff = percentOff; }

    // Two real rules are already wrong here: excluded items (gift cards) get discounted too,
    // and an outer bundle discounts what an inner bundle already discounted.
    public long cents() {
        long sum = 0;
        for (Item item : items) sum += item.cents();
        return sum * (100 - percentOff) / 100;
    }

    // No checks and no parent pointer: any item can be added anywhere, any number of times.
    Bundle add(Item item) { items.add(item); return this; }
    public String toString() { return name; }
}

class Main {
    static String money(long cents) { return String.format("$%d.%02d", cents / 100, cents % 100); }

    public static void main(String[] args) {
        Product keyboard = new Product(8000);
        Bundle desk = new Bundle("Desk setup", 5).add(new Product(30000)).add(keyboard).add(new Product(4900));
        Bundle accessories = new Bundle("Accessories", 15).add(new Product(4000)).add(new Product(2000));
        Bundle office = new Bundle("Home office", 10)
                .add(new Product(120000)).add(desk).add(accessories).add(new Product(5000));

        // The store's rules give $1591.00. Stacked discounts and a discounted gift card lose $53.31.
        System.out.println("total: " + money(office.cents())); // total: $1537.69

        // Moving the keyboard: with no parent pointer, the admin tool must search the catalog for
        // the keyboard's old bundle. This one forgot, so the keyboard is now in both bundles.
        accessories.add(keyboard);
        System.out.println("after the move: " + money(office.cents())); // after the move: $1598.89

        // Nothing stops a bundle going inside its own child. The next cents() call recurses
        // forever and ends in a stack overflow, on the product page, not in the admin tool.
        desk.add(office);
        System.out.println("accepted: " + desk + " now holds " + office + ", which holds " + desk);
        // accepted: Desk setup now holds Home office, which holds Desk setup
    }
}

The shape is right, and three things are still wrong:

• One number can’t carry the rules. cents() returns a single total, so the outer bundle can’t tell which part it may discount. It discounts the gift card and discounts the desk setup a second time. The bundle sells for $1537.69 instead of $1591.00.
• A move leaves the item in two places. Nothing records where an item lives. So the admin tool has to search for the old bundle, and this one forgot. The keyboard is now priced twice.
• A cycle is accepted. A bundle went inside its own sub-bundle, and nothing noticed. The next price lookup recurses forever and crashes the product page, not the admin tool where the mistake was made.

With Composite, and the tree’s rules

Four changes, each one small:

1. Return a value, not a number. quote() returns a Quote with a discountable part and a fixed part. A product puts its price in one or the other. A bundle discounts the discountable part of its children and returns the result as fixed, so no outer bundle can discount it again.
2. Give every node a parent pointer, set only by add. A node has exactly one parent, so add on a node that already has one is a move: it detaches the node first.
3. Check for cycles before changing anything. Walk up from the target bundle through the parent pointers. If the item being added is the target or one of its ancestors, refuse.
4. Write new operations as plain functions over children(), which every node has.

Medium: bundles hold items; every item knows its parent

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation

Try the moves. Each one runs the cycle check first, and the right panel shows the walk up from the target bundle:

MoveReset

Try:Home office into Desk setupDesk setup into itselfKeyboard into AccessoriesAccessories into Desk setup

Price breakdown, per level

Cycle check: walk up from the target

Pick a move. The check runs before anything changes.

Home office total

JMain.javaPybundle.pyC#Program.csGobundle.goTSbundle.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

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

// A price in two parts, because some lines may never be discounted (gift cards, warranties
// priced by an insurer). One number would lose which part an outer bundle may discount.
record Quote(long discountable, long fixed) {
    long total() { return discountable + fixed; }
    Quote plus(Quote o) { return new Quote(discountable + o.discountable, fixed + o.fixed); }
}

// The component. Reading is transparent: every item has children() (a product has none), so a
// walk over the tree needs no type checks. Writing is safe: only Bundle has add().
abstract class Item {
    final String name;
    // Set only by Bundle.add, so it can never disagree with the bundles' child lists.
    Bundle parent;
    Item(String name) { this.name = name; }
    abstract Quote quote();
    abstract String label();
    List<Item> children() { return List.of(); }

    static String money(long cents) { return String.format("$%d.%02d", cents / 100, cents % 100); }
}

// A leaf. Each line in a bundle is its own Product node, so every node has exactly one parent.
// The same SKU in two bundles is two nodes that share catalog data, not one shared node.
class Product extends Item {
    private final long cents;
    private final boolean discountable;
    Product(String name, long cents, boolean discountable) {
        super(name);
        this.cents = cents;
        this.discountable = discountable;
    }
    Quote quote() { return discountable ? new Quote(cents, 0) : new Quote(0, cents); }
    String label() { return name + (discountable ? "" : ", no discount") + ": " + money(cents); }
}

// The composite: a bundle holds products and other bundles, and has its own discount.
class Bundle extends Item {
    private final int percentOff;
    private final List<Item> items = new ArrayList<>();
    Bundle(String name, int percentOff) { super(name); this.percentOff = percentOff; }

    // Read-only view: callers can walk the children but can't bypass add().
    @Override List<Item> children() { return Collections.unmodifiableList(items); }

    Quote subtotal() {
        Quote sum = new Quote(0, 0);
        for (Item item : items) sum = sum.plus(item.quote());
        return sum;
    }

    // Discounts don't stack: once this bundle discounts something, the result is fixed, so an
    // outer bundle can't discount it again. The innermost bundle's discount wins.
    Quote quote() {
        Quote s = subtotal();
        return new Quote(0, s.discountable() * (100 - percentOff) / 100 + s.fixed());
    }

    String label() {
        return name + " (" + percentOff + "% off " + money(subtotal().discountable()) + "): " + money(quote().total());
    }

    // Adds a child, moving it if it already has a parent. Every check runs before anything
    // changes, so a refused add leaves the tree exactly as it was.
    Bundle add(Item item) {
        // Cycle check: walk up from here. If the item is this bundle or one of its ancestors,
        // it would end up inside itself and quote() would never return. With parent pointers
        // this costs O(depth); without them it means searching the item's whole subtree.
        for (Bundle b = this; b != null; b = b.parent) {
            if (b == item) {
                throw new IllegalArgumentException(item == this
                        ? name + " can't contain itself"
                        : item.name + " already contains " + name);
            }
        }
        // One parent at a time: detach from the old bundle, or the item would be priced twice.
        if (item.parent != null) item.parent.items.remove(item);
        item.parent = this;
        items.add(item);
        return this;
    }
}

class Main {
    // A new operation over the tree is a plain function: it only needs label() and children().
    static void breakdown(Item item, String indent) {
        System.out.println(indent + item.label());
        for (Item child : item.children()) breakdown(child, indent + "  ");
    }

    // Parent pointers answer "where is this?" without searching from the root.
    static String path(Item item) {
        String path = item.name;
        for (Bundle b = item.parent; b != null; b = b.parent) path = b.name + " > " + path;
        return path;
    }

    public static void main(String[] args) {
        Product keyboard = new Product("Keyboard", 8000, true);
        Bundle desk = new Bundle("Desk setup", 5)
                .add(new Product("Monitor", 30000, true))
                .add(keyboard)
                .add(new Product("Extended warranty", 4900, false));
        Bundle accessories = new Bundle("Accessories", 15)
                .add(new Product("Mouse", 4000, true))
                .add(new Product("USB-C cable", 2000, true));
        Bundle office = new Bundle("Home office", 10)
                .add(new Product("Laptop", 120000, true))
                .add(desk)
                .add(accessories)
                .add(new Product("Gift card", 5000, false));

        breakdown(office, "");
        // Home office (10% off $1200.00): $1591.00
        //   Laptop: $1200.00
        //   Desk setup (5% off $380.00): $410.00
        //     Monitor: $300.00
        //     Keyboard: $80.00
        //     Extended warranty, no discount: $49.00
        //   Accessories (15% off $60.00): $51.00
        //     Mouse: $40.00
        //     USB-C cable: $20.00
        //   Gift card, no discount: $50.00

        // Both refusals happen before anything changes.
        for (Runnable attempt : List.<Runnable>of(() -> office.add(office), () -> desk.add(office))) {
            try {
                attempt.run();
            } catch (IllegalArgumentException e) {
                System.out.println("refused: " + e.getMessage());
            }
        }
        // refused: Home office can't contain itself
        // refused: Home office already contains Desk setup

        // A move is one add: the keyboard leaves Desk setup and gets 15% off instead of 5%.
        accessories.add(keyboard);
        System.out.println(path(keyboard)); // Home office > Accessories > Keyboard
        System.out.println("Desk setup: " + Item.money(desk.quote().total())); // Desk setup: $334.00
        System.out.println("Home office: " + Item.money(office.quote().total())); // Home office: $1583.00
    }
}

Transparency or safety

Where add lives is a real design choice, and the two options fail in different ways:

	add on the component (transparent)	add only on the composite (safe)
Every node looks the same	Yes: code can call add on any item	No: code must know it holds a bundle
A leaf asked to add	Throws at run time	Doesn’t compile
Code that builds or edits trees	No casts	Needs the bundle type, or a check
Liskov substitution	Broken: a product can’t do what an item promises	Kept

This page splits the difference. Reading is transparent: every item has children(), and a product returns an empty list, so a function can walk any tree without checking types. Writing is safe: only Bundle has add, so nobody can add to a product. Code that edits trees, like the admin tool, already knows it holds a bundle, because that’s what it lets people drop items into.

What to notice

• The value carries the rules. Quote keeps “may be discounted” and “may not” apart all the way up the tree. A composite often needs a richer result than its leaves return: a range, a breakdown, a set of permissions.
• The check comes before the change. add walks up, decides, and only then detaches and attaches. A refused move leaves the tree exactly as it was, so the admin tool can show an error and nothing needs undoing.
• Parent pointers make the check cheap. Walking up costs one step per level. Without them, checking “is the target inside this item?” means searching the item’s whole subtree.
• One parent per node. The same SKU in two bundles is two Product nodes, which share catalog data. Sharing one node between two parents would make it a graph, not a tree. Its parent pointer couldn’t be right for both. And a total over the tree would count it twice.
• New operations are plain functions. breakdown and path aren’t methods on Item. They only need label(), children() and parent, so adding a CSV export or a “find excluded items” report doesn’t touch the classes. When an operation needs different code per node type for many node types, that’s the job of the Visitor pattern, described under “Commonly confused with”.

TradeoffParent pointers

We gain

Cycle checks and “where is this item?” cost one step per level instead of a search from the root. A move can detach the item from its old bundle without looking for it.

We give up

There are two links per edge, and they must always agree. So every change has to go through add. A node can have only one parent, which rules out sharing a subtree. That’s exactly why the Hard level’s immutable tree has to drop parent pointers.

Common mistake

Putting add() on the component and letting leaves throw

It looks tidy. Every node has add, remove and getChild, and Product.add throws “unsupported”. But now every caller of add has to know which nodes really support it. That is the type check the pattern was meant to remove, moved to run time. Keep writes on the composite. Or, if the interface must be the same for all nodes, give the component an isComposite() or asBundle() method. Then callers can ask, instead of catching.

Interviewer

A merchandiser dragged the “Home office” bundle into its own “Desk setup” bundle. The admin tool accepted it, and every product page that shows the bundle crashed. How do you fix it?

What they are testing

Whether you refuse the cycle when the bundle is edited. You walk up parent pointers from the target, before changing anything. And whether you also handle moves, so an item has one parent. The red flag is catching the stack overflow at pricing time, or adding a depth counter to quote(). That hides a broken tree, instead of preventing one.

Hard

A document layout tree

• Cached totals with dirty flags
• Invalidation that stops early
• Deep trees without recursion
• Immutable trees with shared parts
• Readers on other threads

A web document editor keeps its page as a layout tree: the document holds sections, sections hold paragraphs, paragraphs hold lines. Every block has a height, and a container’s height is its padding plus its children’s heights. The editor needs the document’s height for the scrollbar and each block’s position for drawing, after every keystroke. At 60 frames a second there are about 16 ms per frame for everything, and a long document has tens of thousands of blocks.

Two more facts make it harder. A background job (the spell checker, a PDF export, the code that syncs with other editors) reads the tree while the user types. And documents come from users: pasted HTML can nest blocks thousands of levels deep.

Why recomputing is too slow

The Easy level’s size() walks every block below it on every call. Typing one character into a line changes one height, then recomputes all of them. Worse, the Easy level’s print asks every folder for its size, so each leaf is summed once for every ancestor. Both are fine for a sidebar of a few hundred files and far too slow for a layout that has to finish inside a frame.

Dirty flags: cache, then invalidate upwards

Keep each container’s height in a field, and a dirty flag that means “this cache may be wrong”. The tree keeps one invariant: if a block is dirty, every ancestor is dirty too.

• An edit marks upwards and stops early. When a line’s height changes, its paragraph is marked dirty, then the section, then the document. The walk stops at the first block that is already dirty, because by the invariant everything above it is dirty too. Ten keystrokes in one paragraph before the next frame cost one walk to the root and nine walks of one step.
• A read recomputes only dirty blocks. Layout starts at the root. It goes down only into dirty containers, and reads the cached height of every clean child. One edit costs the path from the line to the root, plus one cached read per child of each block on that path.

This is how UI toolkits do it. Android’s View.requestLayout() walks up through the parents the same way. It stops early when a parent has already asked for layout. Browsers mark boxes as needing layout, and lay out only those on the next frame.

Wrap a line, then lay out, in each of the three modes. In “Dirty flags”, edit two lines in the same paragraph before laying out and watch the second edit mark nothing:

No cacheDirty flagsImmutable

Lay outReset

Document

§1

§2

§3

§4

Blocks touched by the last layout

0

Recomputed

0

Read as-is

0

Marked dirty by the last edit

0

Hard: cached heights, dirty flags, and an immutable twin

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation

Two edits, then one layout on the next frame

Scroll or pinch to zoom, drag to pan

JMain.javaPyfrozen.pyC#Program.csGofrozen.goTSfrozen.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.concurrent.atomic.AtomicReference;

// Counts the work one layout pass does, so full and incremental layout can be compared.
final class Work {
    int recomputed; // containers whose height was summed again
    int read;       // children whose height was used as-is: a line, or a clean container's cache
    public String toString() { return "(" + recomputed + " recomputed, " + read + " read)"; }
}

// The component: any block in a document's layout tree. Its height in pixels is cached, and
// `dirty` means the cache may be stale. Invariant: if a block is dirty, so is every ancestor.
abstract class Block {
    Container parent;
    int height;
    boolean dirty;
}

// A leaf. Its height is set from outside (a line wraps when text is typed), never computed.
final class Line extends Block {
    Line(int px) { height = px; }

    // Returns how many blocks this edit newly marked dirty.
    int setHeight(int px) {
        height = px;
        return parent == null ? 0 : parent.markDirty();
    }
}

// The composite: its height is its padding plus its children's, recomputed only when dirty.
// Not thread-safe: reading height() can write the cache. Keep the tree on one thread, as UI
// toolkits do, or share the immutable version below.
final class Container extends Block {
    final int padding;
    final List<Block> children = new ArrayList<>();
    Container(int padding) { this.padding = padding; dirty = true; } // nothing computed yet

    Container add(Block child) {
        child.parent = this;
        children.add(child);
        markDirty();
        return this;
    }

    // Walk up, marking each block dirty, and stop at the first that already is: by the
    // invariant, everything above it is dirty too. Ten edits in one paragraph cost one walk.
    int markDirty() {
        int marked = 0;
        for (Container c = this; c != null && !c.dirty; c = c.parent) {
            c.dirty = true;
            marked++;
        }
        return marked;
    }

    // Reading the height recomputes only what changed since the last read.
    int height(Work w) {
        if (dirty) layout(this, false, w);
        return height;
    }

    // One layout pass. full = recompute every container (what a tree with no cache does);
    // otherwise only dirty containers, reading clean children's cached heights.
    // Iterative, with an explicit stack: recursion would overflow the thread's stack on a deep
    // enough tree, and the depth of a document is decided by whoever wrote it.
    static void layout(Container root, boolean full, Work w) {
        Deque<Container> stack = new ArrayDeque<>();
        Deque<Container> order = new ArrayDeque<>(); // parents end up after their children
        stack.push(root);
        while (!stack.isEmpty()) {
            Container c = stack.pop();
            order.push(c);
            for (Block child : c.children) {
                if (child instanceof Container k && (full || k.dirty)) stack.push(k);
                else w.read++;
            }
        }
        for (Container c : order) {
            int sum = c.padding;
            for (Block child : c.children) sum += child.height;
            c.height = sum;
            c.dirty = false;
            w.recomputed++;
        }
    }
}

// The immutable alternative. A block never changes once built, so its height is computed once,
// in the constructor, from children that are already final. No dirty flags, no parent
// pointers (a shared block has many parents), and any number of threads can read it.
record Frozen(int padding, List<Frozen> kids, int height) {
    static Frozen line(int px) { return new Frozen(0, List.of(), px); }

    static Frozen box(int padding, List<Frozen> kids) {
        int h = padding;
        for (Frozen k : kids) h += k.height;
        return new Frozen(padding, List.copyOf(kids), h);
    }

    // An edit copies the path from the root to the changed line and shares everything else:
    // depth + 1 new blocks. The old root is untouched, so whoever holds it keeps a whole view.
    Frozen withLine(int[] path, int px) {
        Frozen[] chain = new Frozen[path.length];
        Frozen at = this;
        for (int i = 0; i < path.length; i++) {
            chain[i] = at;
            at = at.kids.get(path[i]);
        }
        Frozen fresh = line(px);
        for (int i = path.length - 1; i >= 0; i--) {
            List<Frozen> kids = new ArrayList<>(chain[i].kids);
            kids.set(path[i], fresh);
            fresh = box(chain[i].padding, kids);
        }
        return fresh;
    }
}

class Main {
    // 8 sections of 10 paragraphs of 6 lines. Paddings: document 40, section 24, paragraph 8.
    static final int SECTIONS = 8, PARAGRAPHS = 10, LINES = 6;

    static Frozen frozenDoc() {
        List<Frozen> sections = new ArrayList<>();
        for (int s = 0; s < SECTIONS; s++) {
            List<Frozen> paragraphs = new ArrayList<>();
            for (int p = 0; p < PARAGRAPHS; p++) {
                List<Frozen> lines = new ArrayList<>();
                for (int l = 0; l < LINES; l++) lines.add(Frozen.line(20));
                paragraphs.add(Frozen.box(8, lines));
            }
            sections.add(Frozen.box(24, paragraphs));
        }
        return Frozen.box(40, sections);
    }

    public static void main(String[] args) {
        Container doc = new Container(40);
        Line[][][] lines = new Line[SECTIONS][PARAGRAPHS][LINES];
        int blocks = 1;
        for (int s = 0; s < SECTIONS; s++) {
            Container section = new Container(24);
            for (int p = 0; p < PARAGRAPHS; p++) {
                Container paragraph = new Container(8);
                for (int l = 0; l < LINES; l++) paragraph.add(lines[s][p][l] = new Line(20));
                section.add(paragraph);
                blocks += 1 + LINES;
            }
            doc.add(section);
            blocks++;
        }
        System.out.println(blocks + " blocks"); // 569 blocks

        Work w = new Work();
        Container.layout(doc, true, w);
        System.out.println("full layout: " + doc.height + " px " + w); // full layout: 10472 px (89 recomputed, 480 read)

        // Two edits in one paragraph. The second finds its ancestors already dirty and stops.
        System.out.println("line 3.5.2 wraps to 40 px: " + lines[2][4][1].setHeight(40) + " blocks marked dirty");
        // line 3.5.2 wraps to 40 px: 3 blocks marked dirty
        System.out.println("line 3.5.3 wraps to 40 px: " + lines[2][4][2].setHeight(40) + " blocks marked dirty");
        // line 3.5.3 wraps to 40 px: 0 blocks marked dirty

        // Only the path to the root is recomputed; its siblings are read from their caches.
        w = new Work();
        System.out.println("incremental layout: " + doc.height(w) + " px " + w); // incremental layout: 10512 px (3 recomputed, 22 read)
        w = new Work();
        System.out.println("nothing changed: " + doc.height(w) + " px " + w); // nothing changed: 10512 px (0 recomputed, 0 read)
        w = new Work();
        Container.layout(doc, true, w);
        System.out.println("full layout again: " + doc.height + " px " + w); // full layout again: 10512 px (89 recomputed, 480 read)

        // Immutable version: readers take a snapshot; a writer builds a new root and publishes it
        // atomically. With several writers, use updateAndGet so no edit is lost.
        Frozen v1 = frozenDoc();
        AtomicReference<Frozen> current = new AtomicReference<>(v1);
        Frozen reader = current.get();
        Frozen v2 = v1.withLine(new int[] {2, 4, 1}, 40);
        current.set(v2);
        System.out.println("section 1 shared: " + (v2.kids().get(0) == v1.kids().get(0))
                + ", section 3 shared: " + (v2.kids().get(2) == v1.kids().get(2)));
        // section 1 shared: true, section 3 shared: false
        System.out.println("reader still sees " + reader.height() + " px, new readers see " + current.get().height() + " px");
        // reader still sees 10472 px, new readers see 10492 px

        // A pathological document: 100000 containers nested in a chain. The iterative layout
        // handles it; a recursive one would overflow the stack long before the bottom.
        Container deep = new Container(1);
        Container at = deep;
        for (int i = 1; i < 100_000; i++) {
            Container next = new Container(1);
            at.add(next);
            at = next;
        }
        at.add(new Line(20));
        System.out.println("100000 levels deep: " + deep.height(new Work()) + " px"); // 100000 levels deep: 100020 px
    }
}

What to notice

• The invariant is what makes the early stop safe. Say something marks a block dirty without marking its ancestors. Then the walk can stop below a clean ancestor. The document shows a stale height, with no error. That’s why markDirty is the only way to set the flag, and add calls it too.
• The work follows the path, not the document. Take two edits in one paragraph of a 569-block document. Layout recomputed 3 containers, and reused 22 cached heights. A full layout recomputes 89 and reads 480. On a document ten times bigger, with the same depth, the incremental cost barely moves.
• Layout doesn’t recurse. The pass keeps its own stack, in a list. A recursive walk uses one call frame per level. A pasted document 100,000 levels deep overflows the stack. Java throws StackOverflowError. Python stops at its recursion limit (1000 by default). .NET kills the process. A loop moves the depth onto the heap. Also cap nesting where documents come in. Refusing a document nested 10,000 deep at import is kinder than laying it out.
• Reading writes. height() fills the cache, so two threads that only read can still race on the same fields. A mutable tree with lazy caches belongs to one thread, which is why UI toolkits make you touch views only on the UI thread. Locking every read works, but serializes the readers you wanted to run in parallel.
• The immutable tree is the other answer. A Frozen block never changes, so its height is computed once, when it’s built. An edit builds a new line, a new paragraph, a new section and a new document (4 blocks). It shares the other 565 with the old version. A reader holding the old root keeps a whole, consistent document, for as long as it likes. The writer publishes the new root with one atomic reference swap (AtomicReference, atomic.Pointer, Volatile.Write). No reader ever sees half an edit.
• Immutable trees drop parent pointers. Section 1 is shared by both versions, so it has two parents. Anything that needs “where am I?” carries the path from the root as it walks down, instead of following parent pointers up.
• Sums can skip the recompute. For a pure sum, an edit could add its difference (+20 px) to each ancestor directly. That breaks for anything subtraction can’t undo, like a maximum width, or “any child has an error”. So dirty flags are the general tool.

TradeoffDirty flags vs. an immutable tree

We gain

Dirty flags update in place, with no allocation. They keep parent pointers, for cheap upward walks. An immutable tree gives every reader a consistent snapshot, without locks. It makes undo and “compare with the previous version” nearly free. And it has no invalidation to get wrong.

We give up

Dirty flags tie the tree to one thread. They depend on an invariant that one careless setter can break. An immutable tree allocates a new node per level on every edit. It can’t have parent pointers. And “update this block” becomes “rebuild the path and publish a new root”.

Interviewer

Our editor gets sluggish on long documents. Profiling shows most of each frame goes to recomputing heights after a keystroke. Meanwhile the PDF export, which runs on a worker thread, sometimes prints a page with half an edit in it. Fix both.

What they are testing

Whether you cache heights, mark dirty up to the root with an early stop, and recompute only the dirty path. Then, whether you see that the export problem is a reader racing a writer. You solve it by keeping the tree on one thread, and handing the exporter an immutable snapshot (or by making the tree persistent). The red flag is invalidating the whole tree on every edit. So is adding a lock around each height read.

Say this out loud

Each container caches its height, with a dirty flag. I keep one invariant: a dirty block has dirty ancestors. An edit walks up marking dirty, and stops at the first dirty one. Layout goes down only into dirty containers, with a loop, and reads clean children from cache. For readers on other threads, I’d use an immutable tree. An edit copies the path to the root, shares the rest, and swaps the root atomically.

Tradeoffs

TradeoffComposite vs. checking types at each step

We gain

Callers treat one object and a whole tree the same way. The recursion is written once, in the composite. New node types are new classes, and existing operations handle them without edits.

We give up

The interface has to fit every node. So it tends toward what all nodes can do. Child management ends up either unsafe on leaves, or missing from the interface. The tree’s rules (one parent, no cycles, correct totals) aren’t in the types. They must be enforced by hand.

Use Composite when the data is a part-whole hierarchy of unknown depth, and callers want to treat a part and a whole alike. Examples are files, UI elements, bundles, org units and expressions. Skip it when the structure is fixed and shallow: an order always has lines, and lines never hold orders. Also skip it when leaves and containers have little in common. A shared interface full of methods that half the nodes can’t honor is worse than two plain classes.

In each language

Language	Usual form	Built in
Java	An interface or abstract class; a sealed interface (Java 17) when the node types are fixed	AWT’s Container extends Component, Swing’s JComponent, javax.swing.tree.TreeNode
Python	An ABC or duck typing; a frozen dataclass for immutable nodes	ast.AST nodes walked with ast.walk and ast.NodeVisitor, xml.etree.ElementTree.Element
C#	An interface or abstract class; ImmutableArray for persistent children	WPF’s visual tree, System.Linq.Expressions.Expression trees, Roslyn’s immutable syntax trees
Go	A small interface and a struct holding a slice of it; a type switch when node kinds are closed	go/ast with ast.Inspect, html.Node in golang.org/x/net/html
TypeScript	An interface and classes, or a discriminated union with a kind field	The DOM’s Node, Element and Text; React element trees

Roslyn, the C# compiler, is a well-known large example of the Hard level’s immutable tree. An edit produces a new syntax tree that shares most of its nodes with the old one. The old one stays valid, for anyone still using it.

Commonly confused with

Pattern	Looks like Composite because	The difference
Decorator	Both hold children of their own interface and forward calls	A decorator holds exactly one inner object and adds behavior to it. A composite holds many and combines their results.
Chain of responsibility	A request travels through linked objects; it often runs up a composite’s parent pointers	A chain passes one request along until a handler takes it. A composite asks all of its children and combines the answers. The logging framework uses both on the same logger tree.
Interpreter	Its expression tree is a composite	Interpreter is a composite with a purpose: each node type is a grammar rule, and evaluate is the operation. Every interpreter uses Composite; most composites aren’t interpreters.
Iterator	Both are about walking a collection	An iterator walks a structure without exposing its shape. A composite is the shape. A tree iterator (depth-first, breadth-first) is often how callers walk a composite.
Visitor	It walks a composite and does something per node	Visitor adds operations to a fixed set of node types without editing them, by double dispatch: one visitX method per type. Composite gives the tree; Visitor gives new operations over it. Compilers use both.

Common mistake

A composite that's really a graph

A node shared by two parents, or a reference from a child back to an ancestor, turns the tree into a graph. Totals count the shared part twice, recursive operations may never end, and parent pointers can’t be right. Either enforce one parent and no cycles in add, or make the sharing explicit with immutable nodes and no parent pointers.

Where it shows up

On this site:

• Logging framework: loggers form a tree by name, and settings on a branch apply to everything below it.
• Strategy: a shipping rule that holds one rule per zone nests like a composite, and the whole tree is itself a ShippingRate.
• File system: files and directories as a composite tree, with paths and permissions.

In real systems, you’ll find composites in:

• The DOM, and every UI toolkit (Android’s ViewGroup, AWT and Swing, WPF).
• Syntax trees in compilers and linters.
• Scene graphs in game engines. Moving a parent moves everything attached to it.
• Bills of materials in manufacturing.
• Organization trees in cloud accounts. AWS service control policies attached to an organizational unit apply to every account below it.

Interview questions

Interviewer asksWhere should add() and remove() go, the component or the composite?

On the component, every node looks the same. But a leaf has to throw. That breaks Liskov substitution, and moves the type check to run time. On the composite, misuse doesn’t compile. But code that edits trees needs the composite type. A good middle ground is transparent reads (every node has children(), empty for a leaf) and safe writes (only the composite has add).

Interviewer asksHow do you stop someone adding a node to its own descendant?

Check in add, before changing anything: walk up from the target through parent pointers, and refuse if you meet the node being added. That costs one step per level. Without parent pointers, search the node’s subtree for the target instead. Also make adding a node that already has a parent a move, so a node can’t end up in two places.

Interviewer asksHow do you add a new operation over every kind of node?

If it’s core to what a node is, add a method to the component, and implement it per class. If it only needs the shared interface and the children, write a plain function that walks the tree. Say it needs different code per node type, and there are many such operations over a stable set of types. Then use Visitor, which keeps each operation in one class.

Interviewer asksThe tree is huge and the total is read on every change. What do you do?

Cache each node’s total with a dirty flag. On a change, mark ancestors dirty up to the root, stopping at the first already dirty one. On a read, recompute only dirty nodes and use the cache for the rest, so the cost follows the depth, not the size. Traverse iteratively so deep trees can’t overflow the stack, and if other threads read the tree, give them immutable snapshots.

Interviewer asksCan a node have two parents?

Not in a tree with parent pointers. The pointer can’t be right for both, and totals count the node twice. Sometimes the data really is shared, like a component used in two assemblies. Then either copy it into each place, or switch to immutable nodes without parent pointers. There, sharing is safe, because nothing changes in place.

Mid-level covers

Gives leaves and composites one interface. Keeps the recursion inside the composite, and type checks out of callers. Chooses on purpose where add lives. Keeps one parent per node. Refuses cycles before changing the tree. Adds operations as functions over children().

Senior adds

Also caches totals with dirty flags and a stated invariant. Stops invalidation early. Uses loops, not recursion, for untrusted depth. Knows that lazy caches make reads write. Reaches for an immutable tree, with structural sharing and atomic publication, when readers run on other threads.

Recap

Decision	We chose	We gave up
Leaf and tree	One interface; the composite sums its children	An interface that has to fit every node
Where add lives	Writes on the composite, reads (children()) on everything	Code that edits trees needs the composite type
Pricing rules	A Quote value with discountable and fixed parts	A plain number at each level
Where a node lives	A parent pointer set only by add; adding is moving	Shared subtrees
Cycles	Refused in add, before anything changes	One walk up the tree per add
Big trees	Cached totals, dirty flags, early stop	An invariant that one bad setter breaks
Deep trees	Iterative traversal with an explicit stack	Code that reads less naturally than recursion
Other readers	Immutable nodes, path copying, atomic root swap	An allocation per level on each edit, and parent pointers

Further reading

• Decorator, the one-child cousin of Composite
• Liskov substitution, and why a leaf that throws on add breaks it
• Logging framework, a composite logger tree with inherited settings
• Erich Gamma, Richard Helm, Ralph Johnson and John Vlissides, Design Patterns, the Composite chapter
• Chris Okasaki, Purely Functional Data Structures, for the path copying behind the Hard level’s immutable tree