On this page

Composite

Composite is the pattern behind every tree you've ever clicked through: folders that contain files and other folders, UI panels that contain buttons and other panels, departments that contain people and other departments. It gives the single thing (a file) and the group of things (a folder) one shared interface, so code that asks "how big is this?" doesn't need to know which one it's holding.

The structural patterns overview introduces Composite with a short TypeScript example. This page goes further: the type-switch code that Composite replaces, a full file-system implementation with parent pointers, cycle checks and cached sizes, the long-running argument about where add and remove belong, the sealed-type alternative that modern Java and TypeScript make attractive, and what happens when a tree is deeper than your call stack. If you're preparing for the file system design interview, this is the pattern at its centre.

Intent

Compose objects into tree structures and let clients treat individual objects and compositions of objects uniformly.

Unpacking that:

  • Tree structures. Some objects (composites) contain other objects, which may themselves be composites. Others (leaves) contain nothing.
  • Uniformly. Leaves and composites share an interface. A client can call size() on a file or on a whole drive and get a sensible answer either way.
  • Recursion does the work. A composite answers by asking its children and combining their answers. Each child does the same, down to the leaves.

The design payoff is that the client's code stays the same size no matter how deep the tree is, and adding a new kind of node doesn't mean editing every function that walks the tree.

The problem

Here's a first attempt at a file-system model for a backup tool. Files and folders are separate classes with nothing in common, so every operation has to check what it's holding.

import java.util.*;

class FileEntry {
    final String name; final long bytes;
    FileEntry(String name, long bytes) { this.name = name; this.bytes = bytes; }
}

class FolderEntry {
    final String name;
    final List<Object> contents = new ArrayList<>();   // files OR folders, so: Object
    FolderEntry(String name) { this.name = name; }
}

class BackupPlanner {
    static long totalBytes(Object node) {
        if (node instanceof FileEntry f) return f.bytes;
        if (node instanceof FolderEntry d) {
            long sum = 0;
            for (Object child : d.contents) sum += totalBytes(child);
            return sum;
        }
        throw new IllegalArgumentException("unknown node " + node);
    }

    static int countFiles(Object node) {                // the same type switch, again
        if (node instanceof FileEntry) return 1;
        if (node instanceof FolderEntry d) {
            int n = 0;
            for (Object child : d.contents) n += countFiles(child);
            return n;
        }
        throw new IllegalArgumentException("unknown node " + node);
    }
}

class Demo {
    public static void main(String[] args) {
        FolderEntry home = new FolderEntry("home");
        FolderEntry docs = new FolderEntry("docs");
        docs.contents.add(new FileEntry("cv.pdf", 120));
        home.contents.add(docs);
        home.contents.add(new FileEntry("todo.txt", 5));
        home.contents.add("oops, a String");          // compiles fine: the list holds Object

        assert BackupPlanner.countFiles(docs) == 1;
        assert BackupPlanner.totalBytes(docs) == 120;
        try {
            BackupPlanner.totalBytes(home);
            throw new AssertionError("expected the bad child to blow up");
        } catch (IllegalArgumentException expected) { }
        System.out.println("before: every operation repeats the type switch, and bad children slip in");
    }
}
class FileEntry:
    def __init__(self, name: str, size: int) -> None:
        self.name, self.size = name, size


class FolderEntry:
    def __init__(self, name: str) -> None:
        self.name = name
        self.contents: list[object] = []          # files OR folders


def total_bytes(node: object) -> int:
    if isinstance(node, FileEntry):
        return node.size
    if isinstance(node, FolderEntry):
        return sum(total_bytes(c) for c in node.contents)
    raise TypeError(f"unknown node {node!r}")


def count_files(node: object) -> int:             # the same type switch, again
    if isinstance(node, FileEntry):
        return 1
    if isinstance(node, FolderEntry):
        return sum(count_files(c) for c in node.contents)
    raise TypeError(f"unknown node {node!r}")


home, docs = FolderEntry("home"), FolderEntry("docs")
docs.contents.append(FileEntry("cv.pdf", 120))
home.contents += [docs, FileEntry("todo.txt", 5)]
assert total_bytes(home) == 125
assert count_files(home) == 2
print("before: every operation repeats the type switch")

What's wrong:

  1. The type switch is copied into every operation. totalBytes, countFiles, and soon findLargest, render, permissionsCheck. Each one has the same if file ... else if folder ... else throw skeleton.
  2. Adding a node type means editing all of them. When the backup tool needs symbolic links or zip archives that act like folders, every function grows a new branch. Miss one and you get a runtime IllegalArgumentException in production. That's the opposite of the open/closed principle.
  3. The folder can hold anything. List<Object> is the honest type for "files or folders" when they share nothing, and it lets a String in. The compiler can't help.
  4. Behaviour lives far from data. A file's size rule is in BackupPlanner, not in FileEntry. That's the anaemic model mistake.
  5. No structure rules. Nothing stops a folder from containing itself, or two files with the same name in one folder, or a file appearing in two folders at once.

Structure

classDiagram
    direction TB
    class Client
    class Node {
        <<abstract>>
        -name String
        -parent Directory
        +size() long
        +path() String
        +find(predicate) List
        +render() String
    }
    class File {
        -bytes long
        +size() long
        +resize(bytes)
    }
    class Directory {
        -children Map
        -cachedSize Long
        +size() long
        +add(node)
        +remove(name) Node
        +children() List
    }
    Client --> Node : uses
    Node <|-- File
    Node <|-- Directory
    Directory o--> "0..*" Node : children
    Node --> "0..1" Directory : parent

Directory is a Node and also contains Nodes. That recursive "is-a and has-many" relationship is the heart of the pattern. The parent pointer going the other way is optional, but most real trees need it: to compute a path, to invalidate cached values, to bubble events upward, or to enforce "one parent only".

When the client calls size() on the root, the call fans out down the tree and the answers are summed on the way back up:

sequenceDiagram
    participant C as Client
    participant H as home (Directory)
    participant D as docs (Directory)
    participant F1 as cv.pdf (File)
    participant F2 as notes.txt (File)
    participant P as photos (Directory)
    participant F3 as beach.jpg (File)
    C->>H: size()
    H->>D: size()
    D->>F1: size()
    F1-->>D: 120
    D->>F2: size()
    F2-->>D: 30
    D-->>H: 150
    H->>P: size()
    P->>F3: size()
    F3-->>P: 2000
    P-->>H: 2000
    H-->>C: 2150

Participants

ParticipantIn the exampleResponsibility
ComponentNodeDeclares the operations shared by leaves and composites (size, find, render) and, optionally, holds shared state such as the name and parent.
LeafFileHas no children. Implements each operation directly.
CompositeDirectoryStores child components. Implements each operation by delegating to its children and combining the results. Owns the rules about which children are allowed.
ClientThe backup planner, a UIWorks through the component interface. Doesn't care whether it's holding a leaf or a whole subtree.

Implementation

The implementation below models a small file system. It goes beyond the textbook version in four ways, each of which an interviewer is likely to ask about:

  • Parent pointers so a node knows its path and a directory can tell its ancestors that something changed.
  • Structure rules enforced in Directory.add: unique names per directory, a node has at most one parent (adding it elsewhere moves it), and a directory can't be placed inside itself or any of its descendants.
  • Cached sizes with invalidation that walks up the parent chain, so asking for the size of a large tree twice doesn't walk it twice.
  • Child management only on Directory, the type-safe choice. The uniform alternative is discussed after the code.
import java.util.*;
import java.util.function.Predicate;

abstract class Node {
    private final String name;
    private Directory parent;

    Node(String name) {
        if (name.isBlank() || name.contains("/")) throw new IllegalArgumentException("bad name: " + name);
        this.name = name;
    }

    String name() { return name; }
    Optional<Directory> parent() { return Optional.ofNullable(parent); }
    void setParent(Directory parent) { this.parent = parent; }   // only Directory calls this

    String path() { return (parent == null ? "" : parent.path()) + "/" + name; }

    // Tell every ancestor that a size below it changed.
    void invalidateUpwards() { if (parent != null) parent.invalidateUpwards(); }

    abstract long size();
    abstract void collect(Predicate<Node> match, List<String> out);
    abstract void render(StringBuilder out, String indent);

    final List<String> find(Predicate<Node> match) {
        List<String> out = new ArrayList<>();
        collect(match, out);
        return out;
    }

    final String render() {
        StringBuilder sb = new StringBuilder();
        render(sb, "");
        return sb.toString();
    }
}

final class File extends Node {
    private long bytes;

    File(String name, long bytes) { super(name); this.bytes = bytes; }

    @Override long size() { return bytes; }

    void resize(long bytes) {
        this.bytes = bytes;
        invalidateUpwards();
    }

    @Override void collect(Predicate<Node> match, List<String> out) {
        if (match.test(this)) out.add(path());
    }

    @Override void render(StringBuilder out, String indent) {
        out.append(indent).append(name()).append(" (").append(bytes).append(")\n");
    }
}

final class Directory extends Node {
    static int recomputations = 0;                       // lets the demo prove the cache works
    private final SortedMap<String, Node> children = new TreeMap<>();
    private Long cachedSize;

    Directory(String name) { super(name); }

    void add(Node child) {
        if (children.containsKey(child.name())) {
            throw new IllegalArgumentException(child.name() + " already exists in " + path());
        }
        for (Directory d = this; d != null; d = d.parent().orElse(null)) {
            if (d == child) throw new IllegalArgumentException("cannot put " + child.path() + " inside itself");
        }
        child.parent().ifPresent(old -> old.remove(child.name()));   // one parent only: adding moves
        children.put(child.name(), child);
        child.setParent(this);
        invalidateUpwards();
    }

    Node remove(String name) {
        Node child = children.remove(name);
        if (child == null) throw new NoSuchElementException(name + " not in " + path());
        child.setParent(null);
        invalidateUpwards();
        return child;
    }

    List<Node> children() { return List.copyOf(children.values()); }

    @Override long size() {
        if (cachedSize == null) {
            recomputations++;
            long sum = 0;
            for (Node child : children.values()) sum += child.size();
            cachedSize = sum;
        }
        return cachedSize;
    }

    @Override void invalidateUpwards() {
        cachedSize = null;
        super.invalidateUpwards();
    }

    @Override void collect(Predicate<Node> match, List<String> out) {
        if (match.test(this)) out.add(path());
        for (Node child : children.values()) child.collect(match, out);
    }

    @Override void render(StringBuilder out, String indent) {
        out.append(indent).append(name()).append("/\n");
        for (Node child : children.values()) child.render(out, indent + "  ");
    }
}

class Demo {
    static void expectFailure(Runnable action) {
        try { action.run(); } catch (IllegalArgumentException expected) { return; }
        throw new AssertionError("expected IllegalArgumentException");
    }

    public static void main(String[] args) {
        Directory home = new Directory("home");
        Directory docs = new Directory("docs");
        Directory photos = new Directory("photos");
        File cv = new File("cv.pdf", 120);
        File notes = new File("notes.txt", 30);
        File beach = new File("beach.jpg", 2_000);
        home.add(docs);
        home.add(photos);
        docs.add(cv);
        docs.add(notes);
        photos.add(beach);

        // Uniform treatment: one call, any depth, leaf or subtree.
        assert home.size() == 2_150;
        assert cv.size() == 120;
        assert cv.path().equals("/home/docs/cv.pdf");
        assert home.find(n -> n.name().endsWith(".jpg")).equals(List.of("/home/photos/beach.jpg"));

        // Caching: a second call recomputes nothing. A change recomputes only its ancestors.
        int before = Directory.recomputations;
        assert home.size() == 2_150 && Directory.recomputations == before;
        notes.resize(80);
        assert home.size() == 2_200;
        assert Directory.recomputations == before + 2 : "docs and home only, photos stays cached";

        // Structure rules.
        expectFailure(() -> docs.add(new File("cv.pdf", 1)));          // duplicate name
        expectFailure(() -> docs.add(home));                            // ancestor into descendant
        expectFailure(() -> docs.add(docs));                            // into itself

        // Adding to a new parent moves the node and fixes both sizes.
        photos.add(notes);
        assert notes.path().equals("/home/photos/notes.txt");
        assert docs.size() == 120 && photos.size() == 2_080 && home.size() == 2_200;

        assert home.render().equals("""
                home/
                  docs/
                    cv.pdf (120)
                  photos/
                    beach.jpg (2000)
                    notes.txt (80)
                """);
        System.out.print(home.render());
    }
}
from __future__ import annotations

from abc import ABC, abstractmethod
from collections.abc import Callable


class Node(ABC):
    def __init__(self, name: str) -> None:
        if not name.strip() or "/" in name:
            raise ValueError(f"bad name: {name!r}")
        self.name = name
        self.parent: Directory | None = None      # only Directory sets this

    def path(self) -> str:
        return (self.parent.path() if self.parent else "") + "/" + self.name

    def invalidate_upwards(self) -> None:
        if self.parent is not None:
            self.parent.invalidate_upwards()

    @abstractmethod
    def size(self) -> int: ...

    @abstractmethod
    def _collect(self, match: Callable[[Node], bool], out: list[str]) -> None: ...

    @abstractmethod
    def _render(self, out: list[str], indent: str) -> None: ...

    def find(self, match: Callable[[Node], bool]) -> list[str]:
        out: list[str] = []
        self._collect(match, out)
        return out

    def render(self) -> str:
        out: list[str] = []
        self._render(out, "")
        return "".join(out)


class File(Node):
    def __init__(self, name: str, size: int) -> None:
        super().__init__(name)
        self._size = size

    def size(self) -> int:
        return self._size

    def resize(self, size: int) -> None:
        self._size = size
        self.invalidate_upwards()

    def _collect(self, match: Callable[[Node], bool], out: list[str]) -> None:
        if match(self):
            out.append(self.path())

    def _render(self, out: list[str], indent: str) -> None:
        out.append(f"{indent}{self.name} ({self._size})\n")


class Directory(Node):
    recomputations = 0                           # lets the demo prove the cache works

    def __init__(self, name: str) -> None:
        super().__init__(name)
        self._children: dict[str, Node] = {}
        self._cached_size: int | None = None

    def add(self, child: Node) -> None:
        if child.name in self._children:
            raise ValueError(f"{child.name} already exists in {self.path()}")
        d: Directory | None = self
        while d is not None:
            if d is child:
                raise ValueError(f"cannot put {child.path()} inside itself")
            d = d.parent
        if child.parent is not None:              # one parent only: adding moves
            child.parent.remove(child.name)
        self._children[child.name] = child
        child.parent = self
        self.invalidate_upwards()

    def remove(self, name: str) -> Node:
        child = self._children.pop(name)          # KeyError if missing
        child.parent = None
        self.invalidate_upwards()
        return child

    def children(self) -> list[Node]:
        return [self._children[k] for k in sorted(self._children)]

    def size(self) -> int:
        if self._cached_size is None:
            Directory.recomputations += 1
            self._cached_size = sum(c.size() for c in self._children.values())
        return self._cached_size

    def invalidate_upwards(self) -> None:
        self._cached_size = None
        super().invalidate_upwards()

    def _collect(self, match: Callable[[Node], bool], out: list[str]) -> None:
        if match(self):
            out.append(self.path())
        for child in self.children():
            child._collect(match, out)

    def _render(self, out: list[str], indent: str) -> None:
        out.append(f"{indent}{self.name}/\n")
        for child in self.children():
            child._render(out, indent + "  ")


def expect_failure(action: Callable[[], object]) -> None:
    try:
        action()
    except ValueError:
        return
    raise AssertionError("expected ValueError")


if __name__ == "__main__":
    home, docs, photos = Directory("home"), Directory("docs"), Directory("photos")
    cv, notes, beach = File("cv.pdf", 120), File("notes.txt", 30), File("beach.jpg", 2_000)
    home.add(docs)
    home.add(photos)
    docs.add(cv)
    docs.add(notes)
    photos.add(beach)

    assert home.size() == 2_150 and cv.size() == 120
    assert cv.path() == "/home/docs/cv.pdf"
    assert home.find(lambda n: n.name.endswith(".jpg")) == ["/home/photos/beach.jpg"]

    before = Directory.recomputations
    assert home.size() == 2_150 and Directory.recomputations == before
    notes.resize(80)
    assert home.size() == 2_200
    assert Directory.recomputations == before + 2, "docs and home only, photos stays cached"

    expect_failure(lambda: docs.add(File("cv.pdf", 1)))
    expect_failure(lambda: docs.add(home))
    expect_failure(lambda: docs.add(docs))

    photos.add(notes)
    assert notes.path() == "/home/photos/notes.txt"
    assert (docs.size(), photos.size(), home.size()) == (120, 2_080, 2_200)

    assert home.render() == (
        "home/\n"
        "  docs/\n"
        "    cv.pdf (120)\n"
        "  photos/\n"
        "    beach.jpg (2000)\n"
        "    notes.txt (80)\n"
    )
    print(home.render(), end="")
import assert from "node:assert/strict";

abstract class Node {
  parent: Directory | null = null; // only Directory sets this

  constructor(readonly name: string) {
    if (!name.trim() || name.includes("/")) throw new RangeError(`bad name: ${name}`);
  }

  path(): string {
    return (this.parent ? this.parent.path() : "") + "/" + this.name;
  }

  invalidateUpwards(): void {
    this.parent?.invalidateUpwards();
  }

  abstract size(): number;
  abstract collect(match: (n: Node) => boolean, out: string[]): void;
  abstract renderInto(out: string[], indent: string): void;

  find(match: (n: Node) => boolean): string[] {
    const out: string[] = [];
    this.collect(match, out);
    return out;
  }

  render(): string {
    const out: string[] = [];
    this.renderInto(out, "");
    return out.join("");
  }
}

class File extends Node {
  constructor(name: string, private bytes: number) {
    super(name);
  }
  size(): number {
    return this.bytes;
  }
  resize(bytes: number): void {
    this.bytes = bytes;
    this.invalidateUpwards();
  }
  collect(match: (n: Node) => boolean, out: string[]): void {
    if (match(this)) out.push(this.path());
  }
  renderInto(out: string[], indent: string): void {
    out.push(`${indent}${this.name} (${this.bytes})\n`);
  }
}

class Directory extends Node {
  static recomputations = 0; // lets the demo prove the cache works
  private readonly kids = new Map<string, Node>();
  private cachedSize: number | null = null;

  add(child: Node): void {
    if (this.kids.has(child.name)) {
      throw new RangeError(`${child.name} already exists in ${this.path()}`);
    }
    for (let d: Directory | null = this; d; d = d.parent) {
      if (d === child) throw new RangeError(`cannot put ${child.path()} inside itself`);
    }
    child.parent?.remove(child.name); // one parent only: adding moves
    this.kids.set(child.name, child);
    child.parent = this;
    this.invalidateUpwards();
  }

  remove(name: string): Node {
    const child = this.kids.get(name);
    if (!child) throw new RangeError(`${name} not in ${this.path()}`);
    this.kids.delete(name);
    child.parent = null;
    this.invalidateUpwards();
    return child;
  }

  children(): Node[] {
    return [...this.kids.keys()].sort().map((k) => this.kids.get(k)!);
  }

  size(): number {
    if (this.cachedSize === null) {
      Directory.recomputations++;
      this.cachedSize = this.children().reduce((sum, c) => sum + c.size(), 0);
    }
    return this.cachedSize;
  }

  override invalidateUpwards(): void {
    this.cachedSize = null;
    super.invalidateUpwards();
  }

  collect(match: (n: Node) => boolean, out: string[]): void {
    if (match(this)) out.push(this.path());
    for (const c of this.children()) c.collect(match, out);
  }

  renderInto(out: string[], indent: string): void {
    out.push(`${indent}${this.name}/\n`);
    for (const c of this.children()) c.renderInto(out, indent + "  ");
  }
}

const home = new Directory("home");
const docs = new Directory("docs");
const photos = new Directory("photos");
const cv = new File("cv.pdf", 120);
const notes = new File("notes.txt", 30);
const beach = new File("beach.jpg", 2_000);
home.add(docs);
home.add(photos);
docs.add(cv);
docs.add(notes);
photos.add(beach);

assert.equal(home.size(), 2_150);
assert.equal(cv.path(), "/home/docs/cv.pdf");
assert.deepEqual(home.find((n) => n.name.endsWith(".jpg")), ["/home/photos/beach.jpg"]);

const before = Directory.recomputations;
assert.equal(home.size(), 2_150);
assert.equal(Directory.recomputations, before);
notes.resize(80);
assert.equal(home.size(), 2_200);
assert.equal(Directory.recomputations, before + 2, "docs and home only, photos stays cached");

assert.throws(() => docs.add(new File("cv.pdf", 1)), RangeError);
assert.throws(() => docs.add(home), RangeError);
assert.throws(() => docs.add(docs), RangeError);

photos.add(notes);
assert.equal(notes.path(), "/home/photos/notes.txt");
assert.deepEqual([docs.size(), photos.size(), home.size()], [120, 2_080, 2_200]);

assert.equal(
  home.render(),
  "home/\n  docs/\n    cv.pdf (120)\n  photos/\n    beach.jpg (2000)\n    notes.txt (80)\n",
);
process.stdout.write(home.render());

Walking through the decisions

Who owns the parent pointer. The parent link is set in exactly one place, Directory.add, and cleared in exactly one place, Directory.remove. If clients could set parent directly, the two directions of the relationship would drift apart: a node would claim a parent that doesn't list it as a child. In Java the setter is package-private. In Python and TypeScript it's public by necessity, and the comment is the guard. In a larger codebase you'd hide it behind a module boundary.

"Add" means "move". A node in a tree has one parent. Rather than throwing when you add a node that already has a parent, add detaches it from the old one first. That matches how file systems behave (mv) and keeps the invariant without extra client code. Some domains want the opposite (a UI framework might throw to catch bugs), and either is fine as long as it's deliberate. What's never fine is silently letting a node sit in two parents, because then path() and size invalidation are wrong.

The cycle check walks up, not down. To stop docs.add(home), the code walks from the target directory up through its ancestors and checks whether the node being added is one of them. That's O(depth). Checking the other way (searching the subtree being added for the target) is O(subtree size), which is much worse for big folders. Without this check, size() on a cyclic tree recurses forever.

Cached aggregates need invalidation, and the parent pointer provides it. Directory.size() caches its total. When a file is resized or a child is added or removed, invalidateUpwards clears the cache on every ancestor and nothing else. The demo proves the effect: after resizing notes.txt, only docs and home recompute, while photos keeps its cached value. Without parent pointers, you'd have to throw away every cache in the tree on every change, or not cache at all.

Sorted children make output deterministic. TreeMap in Java and sorted keys in Python and TypeScript mean render() produces the same string every time, which makes the tree easy to test. If insertion order matters in your domain (UI widgets usually do), use an ordered list instead and give add an optional index.

Operations on leaves are trivially correct. File.size() returns its bytes. File.collect checks only itself. There's no if anywhere that asks "am I a file or a directory?" The polymorphic call does that job.

Uniform interface vs type safety

The biggest design decision in Composite is where child-management methods (add, remove, children) go. There are two schools, and the original GoF book itself discusses the tension.

Type-safe design (what the implementation above uses): only the composite has add and remove. A leaf can't be asked to hold children, and the compiler catches the mistake. The cost is that clients sometimes need to know which kind of node they hold before they can add to it.

Uniform (transparent) design: the component interface declares add, remove and children. Leaves inherit versions that throw (or do nothing). Clients can treat every node identically, which is convenient for generic tree builders, serializers and editors. The cost is that leaf.add(x) compiles and fails at runtime, which also bends the Liskov substitution principle: a Label is a Widget that can't do something every Widget claims to do.

The UI-tree example below shows both side by side. The TypeScript version uses @ts-expect-error to prove that the type-safe design really does reject the bad call at compile time (if the line ever compiled, tsc would fail on the unused directive).

import java.util.*;

// Uniform: every Widget claims to manage children.
interface Widget {
    String draw();
    default void add(Widget child) { throw new UnsupportedOperationException(getClass().getSimpleName() + " has no children"); }
    default List<Widget> children() { return List.of(); }
}

record Label(String text) implements Widget {
    public String draw() { return "Label(" + text + ")"; }
}

final class Panel implements Widget {
    private final List<Widget> kids = new ArrayList<>();
    @Override public void add(Widget child) { kids.add(child); }
    @Override public List<Widget> children() { return List.copyOf(kids); }
    public String draw() {
        StringJoiner j = new StringJoiner(", ", "Panel[", "]");
        kids.forEach(k -> j.add(k.draw()));
        return j.toString();
    }
}

// Type-safe: only containers have add().
interface View { String draw(); }
record Text(String text) implements View { public String draw() { return "Text(" + text + ")"; } }
final class Stack implements View {
    private final List<View> kids = new ArrayList<>();
    void add(View child) { kids.add(child); }
    public String draw() {
        StringJoiner j = new StringJoiner(", ", "Stack[", "]");
        kids.forEach(k -> j.add(k.draw()));
        return j.toString();
    }
}

class Demo {
    // A generic builder is easy with the uniform design: no type checks needed.
    static void attachAll(Widget parent, List<Widget> kids) { kids.forEach(parent::add); }

    public static void main(String[] args) {
        Panel root = new Panel();
        attachAll(root, List.of(new Label("Name"), new Label("Email")));
        assert root.draw().equals("Panel[Label(Name), Label(Email)]");

        // ...but a mistake compiles and fails at runtime.
        try {
            attachAll(new Label("oops"), List.of(new Label("child")));
            throw new AssertionError("expected UnsupportedOperationException");
        } catch (UnsupportedOperationException expected) { }

        // Type-safe: new Text("x").add(...) would not compile. Clients must hold a Stack to add.
        Stack form = new Stack();
        form.add(new Text("Name"));
        View asView = form;                        // still usable uniformly for drawing
        assert asView.draw().equals("Stack[Text(Name)]");

        // When you only have a View, you have to ask (the GoF "getComposite" idea, via pattern matching).
        if (asView instanceof Stack s) s.add(new Text("Email"));
        assert form.draw().equals("Stack[Text(Name), Text(Email)]");
        System.out.println("uniform vs type-safe ok");
    }
}
import assert from "node:assert/strict";

// Uniform: every Widget claims to manage children.
abstract class Widget {
  abstract draw(): string;
  add(_child: Widget): void {
    throw new Error(`${this.constructor.name} has no children`);
  }
}
class Label extends Widget {
  constructor(readonly text: string) {
    super();
  }
  draw(): string {
    return `Label(${this.text})`;
  }
}
class Panel extends Widget {
  private readonly kids: Widget[] = [];
  override add(child: Widget): void {
    this.kids.push(child);
  }
  draw(): string {
    return `Panel[${this.kids.map((k) => k.draw()).join(", ")}]`;
  }
}

// Type-safe: only containers have add().
interface View {
  draw(): string;
}
class Text implements View {
  constructor(readonly text: string) {}
  draw(): string {
    return `Text(${this.text})`;
  }
}
class Stack implements View {
  private readonly kids: View[] = [];
  add(child: View): void {
    this.kids.push(child);
  }
  draw(): string {
    return `Stack[${this.kids.map((k) => k.draw()).join(", ")}]`;
  }
}

const attachAll = (parent: Widget, kids: Widget[]) => kids.forEach((k) => parent.add(k));

const root = new Panel();
attachAll(root, [new Label("Name"), new Label("Email")]);
assert.equal(root.draw(), "Panel[Label(Name), Label(Email)]");
assert.throws(() => attachAll(new Label("oops"), [new Label("child")]), /has no children/);

const form = new Stack();
form.add(new Text("Name"));
const asView: View = form;
assert.equal(asView.draw(), "Stack[Text(Name)]");
if (asView instanceof Stack) asView.add(new Text("Email"));
assert.equal(form.draw(), "Stack[Text(Name), Text(Email)]");

// Never called: exists to prove the type-safe design rejects this at compile time.
function wontCompile(t: Text): void {
  // @ts-expect-error Text has no add() method
  t.add(new Text("child"));
}
void wontCompile;
console.log("uniform vs type-safe ok");

How to choose:

PreferWhen
Type-safeThe tree is built by application code that knows what it's building (most domain models, file systems, org charts). Bugs caught at compile time are worth a cast or pattern match in the few places that need one.
UniformGeneric code builds or edits trees without knowing node kinds: deserializers, drag-and-drop editors, tree-manipulation libraries. The DOM is uniform: every Node has appendChild, and calling it on a text node throws a HierarchyRequestError at runtime.
A middle pathGive the component a safe query such as asContainer(): Optional<Container> (GoF calls this getComposite). Clients ask once and get a typed handle, without a blind cast.

The sealed-type alternative

Composite puts each operation's logic inside the node classes. That makes adding a new node type easy (write one class) and adding a new operation hard (edit every class). Languages with sealed types or tagged unions and exhaustive pattern matching make the opposite trade attractive: keep the nodes as plain data, write each operation as one function with a switch, and let the compiler complain if a case is missing. This is the classic expression problem, and neither side is always right.

import java.util.*;

// Java 21+: a closed set of node types, and switches the compiler checks for completeness.
sealed interface Entry permits FileEntry, DirEntry {}
record FileEntry(String name, long bytes) implements Entry {}
record DirEntry(String name, List<Entry> children) implements Entry {}

final class Ops {
    static long size(Entry e) {
        return switch (e) {
            case FileEntry f -> f.bytes();
            case DirEntry d -> d.children().stream().mapToLong(Ops::size).sum();
        };   // adding a third record type makes this a compile error until it's handled
    }

    static int depth(Entry e) {   // a new operation is one new function, no class edits
        return switch (e) {
            case FileEntry f -> 1;
            case DirEntry d -> 1 + d.children().stream().mapToInt(Ops::depth).max().orElse(0);
        };
    }
}

class Demo {
    public static void main(String[] args) {
        Entry tree = new DirEntry("home", List.of(
                new DirEntry("docs", List.of(new FileEntry("cv.pdf", 120))),
                new FileEntry("todo.txt", 5)));
        assert Ops.size(tree) == 125;
        assert Ops.depth(tree) == 3;
        System.out.println("sealed alternative ok");
    }
}
from dataclasses import dataclass


@dataclass(frozen=True)
class FileEntry:
    name: str
    size: int


@dataclass(frozen=True)
class DirEntry:
    name: str
    children: tuple["Entry", ...]


type Entry = FileEntry | DirEntry       # Python 3.12 type alias; mypy/pyright check exhaustiveness


def size(e: Entry) -> int:
    match e:
        case FileEntry(size=s):
            return s
        case DirEntry(children=kids):
            return sum(size(k) for k in kids)


def depth(e: Entry) -> int:
    match e:
        case FileEntry():
            return 1
        case DirEntry(children=kids):
            return 1 + max((depth(k) for k in kids), default=0)


tree = DirEntry("home", (DirEntry("docs", (FileEntry("cv.pdf", 120),)), FileEntry("todo.txt", 5)))
assert size(tree) == 125
assert depth(tree) == 3
print("sealed alternative ok")
import assert from "node:assert/strict";

type Entry =
  | { kind: "file"; name: string; bytes: number }
  | { kind: "dir"; name: string; children: Entry[] };

function size(e: Entry): number {
  switch (e.kind) {
    case "file":
      return e.bytes;
    case "dir":
      return e.children.reduce((s, c) => s + size(c), 0);
    default: {
      const unreachable: never = e; // compile error if a new kind isn't handled
      return unreachable;
    }
  }
}

const depth = (e: Entry): number =>
  e.kind === "file" ? 1 : 1 + Math.max(0, ...e.children.map(depth));

const tree: Entry = {
  kind: "dir",
  name: "home",
  children: [
    { kind: "dir", name: "docs", children: [{ kind: "file", name: "cv.pdf", bytes: 120 }] },
    { kind: "file", name: "todo.txt", bytes: 5 },
  ],
};
assert.equal(size(tree), 125);
assert.equal(depth(tree), 3);
console.log("sealed alternative ok");

Notice this looks a lot like the "before" code, and that's worth thinking about. What made the before code bad wasn't the type switch itself. It was the open-ended Object type with a throw for unknown cases, so a missing branch was a runtime failure. With a sealed hierarchy, the compiler proves every switch is complete. Use the sealed style when the set of node kinds is small and stable and operations keep growing (compilers and ASTs are the textbook case). Use classic Composite when node kinds keep growing, or when nodes carry behaviour and invariants of their own, like Directory.add above. When you need many operations over a class-based Composite, the Visitor pattern is the object-oriented way to get the sealed-style benefits.

Deep trees and the call stack

Every recursive method on a composite uses one stack frame per level. File systems and UI trees are rarely more than a few dozen levels deep, so this doesn't matter. But some trees are deep: a comment thread with tens of thousands of nested replies, a linked chain of managers in a badly imported HR dataset, a parse tree built from machine-generated input. Then recursion fails: RecursionError in Python (the default limit is 1,000 frames), RangeError: Maximum call stack size exceeded in JavaScript, StackOverflowError in Java.

The fix is to traverse with an explicit stack (or queue). Here's an org chart, where each person's "cost" is their own salary plus everyone under them, computed both ways:

from __future__ import annotations

from dataclasses import dataclass, field


@dataclass(eq=False)
class Person:
    name: str
    salary: int
    reports: list[Person] = field(default_factory=list)

    def cost_recursive(self) -> int:
        return self.salary + sum(r.cost_recursive() for r in self.reports)

    def cost_iterative(self) -> int:
        total, stack = 0, [self]
        while stack:
            p = stack.pop()
            total += p.salary
            stack.extend(p.reports)
        return total

    def headcount(self) -> int:
        count, stack = 0, [self]
        while stack:
            p = stack.pop()
            count += 1
            stack.extend(p.reports)
        return count


ceo = Person("Mira", 300, [
    Person("Dev", 200, [Person("Ana", 100), Person("Bo", 100)]),
    Person("Kai", 180, [Person("Lu", 90)]),
])
assert ceo.cost_recursive() == ceo.cost_iterative() == 970
assert ceo.headcount() == 6
assert ceo.reports[0].cost_iterative() == 400        # any subtree works the same way

# A pathological 5,000-level chain, e.g. from a bad data import.
top = Person("p0", 1)
cur = top
for i in range(1, 5_000):
    nxt = Person(f"p{i}", 1)
    cur.reports.append(nxt)
    cur = nxt

try:
    top.cost_recursive()
    raise AssertionError("expected RecursionError")
except RecursionError:
    pass
assert top.cost_iterative() == 5_000
print("org chart ok: recursion fails at depth 5,000, the explicit stack doesn't")
import assert from "node:assert/strict";

class Person {
  readonly reports: Person[] = [];
  constructor(readonly name: string, readonly salary: number) {}

  withReports(...people: Person[]): this {
    this.reports.push(...people);
    return this;
  }

  costRecursive(): number {
    return this.salary + this.reports.reduce((s, r) => s + r.costRecursive(), 0);
  }

  costIterative(): number {
    let total = 0;
    const stack: Person[] = [this];
    while (stack.length) {
      const p = stack.pop()!;
      total += p.salary;
      for (const r of p.reports) stack.push(r);
    }
    return total;
  }
}

const ceo = new Person("Mira", 300).withReports(
  new Person("Dev", 200).withReports(new Person("Ana", 100), new Person("Bo", 100)),
  new Person("Kai", 180).withReports(new Person("Lu", 90)),
);
assert.equal(ceo.costRecursive(), 970);
assert.equal(ceo.costIterative(), 970);

// A pathological 200,000-level chain.
const top = new Person("p0", 1);
let cur = top;
for (let i = 1; i < 200_000; i++) {
  const next = new Person(`p${i}`, 1);
  cur.reports.push(next);
  cur = next;
}
assert.throws(() => top.costRecursive(), RangeError);
assert.equal(top.costIterative(), 200_000);
console.log("org chart ok: recursion overflows, the explicit stack doesn't");

Two notes. First, raising Python's recursion limit with sys.setrecursionlimit only moves the problem and can crash the interpreter if the C stack runs out first. Second, the iterative version doesn't preserve the order in which children are visited. For sums and counts that's irrelevant. For rendering, push children in reverse order or use a deque. If you want iteration to be a reusable capability rather than code inside each operation, give the composite an iterator that yields every node, and let operations be simple loops over it.

Real-world uses

Java

  • AWT and Swing. java.awt.Container extends java.awt.Component and holds other components, so a Panel can contain buttons and other panels, and layout and painting recurse through the tree. Swing's JComponent extends Container, which is why, unusually, almost every Swing widget can technically hold children. That's the uniform design, with its usual trade-off.
  • javax.swing.tree.TreeNode and DefaultMutableTreeNode model the data behind a JTree as a composite of nodes with parent pointers.

The browser and React

  • The DOM is the composite most developers use daily. Every Node has childNodes, parentNode and appendChild, and Element and Text nodes share that interface. Operations like textContent recurse through the subtree. The DOM takes the uniform approach: calling appendChild on a text node throws at runtime.
  • DOM event bubbling walks the parent pointers from the target element up to the document, giving each ancestor a chance to handle the event. That's a chain of responsibility running along a composite's parent links.
  • React element trees. A component returns elements, which may be host elements (div) or other components, each with children. React renders the tree recursively, and the React internals page shows how the fiber architecture walks it iteratively so the work can be interrupted, which is the explicit-stack idea from above applied at scale.

Python

  • The ast module. ast.parse returns a tree of ast.AST nodes, where statements contain expressions which contain other expressions. ast.walk iterates every node, and ast.NodeVisitor provides the visitor that usually accompanies such trees.
  • xml.etree.ElementTree. Each Element holds child elements and supports iteration (iter()) over the whole subtree.

Everywhere else

  • Scene graphs in game engines and 3D tools: a group node's transform applies to all its children.
  • Build systems and task runners, where a composite task runs its subtasks.
  • Permission and menu trees, organisational charts, bills of materials (a bicycle is made of a frame and wheels, a wheel is made of a rim and spokes).

When NOT to use it

When the structure isn't really a tree. If a "child" can have several parents (a file hard-linked into two folders, an employee with two managers, a task with several prerequisites), you have a graph. Parent pointers, cached aggregates and cycle checks all assume one parent per node. Model it as a graph with explicit edges, and use graph traversal with a visited set.

When the hierarchy is fixed and shallow. A Country has States, which have Citys, always exactly three levels, and each level has different data and behaviour. Forcing them into one Node interface hides useful differences and invites nonsense like a city containing a country. Plain classes with typed collections (Country.states, State.cities) are clearer.

When leaves and composites share almost nothing. The pattern pays off when there are meaningful operations that make sense on both. If the only shared method is getName(), the uniform interface is a fiction, and clients will be type-checking anyway.

When the operations change much more often than the node types. Every new operation means editing every node class. If new reports and analyses arrive weekly while the node kinds never change, the sealed-type style or a visitor fits better.

When performance depends on flat data. Millions of tiny node objects, each with a list of children and a parent pointer, use a lot of memory and scatter data across the heap. Game engines and databases often store trees as flat arrays (parent index arrays, nested sets, adjacency lists in tables) for cache locality and bulk operations. Sharing immutable leaf objects with Flyweight helps when many leaves are identical.

Costs to keep in mind: recursion depth on unusual inputs, the invariants you now own (one parent, no cycles, unique names), cache invalidation if you cache aggregates, and the uniform-versus-safe decision, which is easy to make implicitly and hard to change later.

PatternRelationship to CompositeKey difference
DecoratorAlso recursive composition through a shared interfaceA decorator has exactly one child and adds behaviour. A composite has many children and aggregates them.
IteratorCommonly used to walk a compositeIterator separates how to traverse from the tree, so operations become loops.
VisitorCommonly used to add operations to a compositeVisitor moves operations out of node classes, making new operations cheap and new node types expensive.
Chain of ResponsibilityOften runs along a composite's parent pointersEvent bubbling: a request travels up the tree until some ancestor handles it.
FlyweightShares identical leavesLeaves that are shared can't hold a parent pointer, so parent context has to be passed in as extrinsic state.
InterpreterA grammar's syntax tree is a compositeInterpreter adds the meaning: each node evaluates itself, combining its children's results.
BuilderBuilds complex composites step by stepBuilder is about construction, Composite about the resulting structure.
CommandA macro command is a composite of commandsExecuting the macro executes each child command.

The smell that suggests it

  • The same instanceof or isinstance switch in several functions, each walking a nested structure and handling "single item" and "group of items" separately. The before code above is the canonical case.
  • Collections typed as Object, any or a union, because the "contains files or folders" relationship has no shared type.
  • Code that special-cases the top level: "if it's one item, do X, if it's a list, loop and do X on each". The client is doing the composite's job.
  • Hand-rolled recursion repeated across features. One function sums sizes recursively, another collects names recursively, another renders recursively, each re-implementing the walk.
  • Nested data with an unbounded depth that the domain describes in recursive terms: "a category can contain products and other categories", "a group can contain users and other groups".

If you notice yourself adding add to a class that should never have children just to satisfy an interface, that's the opposite smell: the uniform design has leaked into a place it doesn't belong.

Interview questions

  1. "Where would you put add and remove: on the component or only on the composite?" It's a trade-off between uniformity and safety. On the component (uniform), generic code can build any tree without type checks, but leaf.add() compiles and fails at runtime, which bends Liskov substitution. On the composite only (type-safe), misuse is a compile error but clients need to know they hold a composite to add children. For domain models, prefer type-safe. For generic tree editors and deserializers, uniform can be worth it. A middle path is a safe asComposite() query.

  2. "How do you prevent cycles?" In add, walk from the target composite up its parent chain and reject the operation if the node being added is the target itself or one of its ancestors. That costs O(depth). It relies on each node having exactly one parent, which add also enforces by detaching a node from its old parent.

  3. "Directory sizes are slow to compute on a huge tree. What would you do?" Cache each directory's aggregate and invalidate it upward through parent pointers whenever something below changes. Only the path from the changed node to the root is invalidated, so repeated queries are O(1) and a change costs O(depth). Alternatively, maintain the totals eagerly by propagating the delta upward on every change.

  4. "Design a file system with files, directories and symbolic links." Composite with Node as the component, File and Directory as leaf and composite. A symlink is a leaf that stores a target path, and its size() is usually the link's own size, not the target's, to avoid double counting and cycles through links. Name lookup resolves links with a hop limit (operating systems typically fail after a fixed number of nested links, such as 40 on Linux). See the full file system case study.

  5. "How is Composite different from Decorator?" Both implement the component interface and hold components. A decorator holds exactly one and adds behaviour around it. A composite holds many and combines their results. A decorator's identity is "the same thing, plus something". A composite's is "a group that acts like one thing".

  6. "Your tree can be 100,000 levels deep. What breaks?" Recursive operations overflow the call stack. Rewrite traversals with an explicit stack or queue, or expose an iterator over all nodes so each operation becomes a loop. Recursive toString or equals methods break the same way, as can a debugger that tries to print the tree.

  7. "When would you choose a sealed interface with pattern matching over Composite?" When the set of node types is small and stable and new operations keep being added, as in compilers and query planners. The compiler checks that every switch is exhaustive, and adding an operation is one function. Composite is better when node types grow, or when nodes need their own behaviour and invariants.

  8. "How would you model an org chart where some employees report to two managers?" That's no longer a tree, so Composite's single-parent assumption breaks. Model reporting lines as a graph (or keep one primary manager as the tree and store dotted-line relationships separately). Aggregations like headcount must then avoid double counting, typically with a visited set.

  9. "Give a real example of Composite you've used." The DOM (Node, Element, appendChild, event bubbling along parents), React component trees, Swing's Container and Component, Python's ast nodes, scene graphs, and file systems themselves.

  10. "What invariants does a composite own, and how do you test them?" One parent per node, no cycles, consistent parent and child links, unique child names if the domain requires it, and correct cached aggregates. Test each with small trees: add then check both sides of the link, try to create a cycle and expect an error, move a node and check both old and new parent aggregates, and resize a leaf and check every ancestor's total.