Composite pattern
Treat a single object and a whole tree of objects the same way through one interface. Full Java and Python code, cycles, deep trees, caching sizes and when Visitor fits better.
On this page
- The problem: a type check at every node
- The idea: one interface for one thing and for many
- Build it step by step
- Extending it: a new kind of node
- Modern forms: sealed types and pattern matching
- Where this breaks
- Composite, Decorator, Chain of Responsibility: how they differ
- When not to use it
- Real uses
- In the interview
- Quiz
The problem: a type check at every node
A storage app shows how much space each folder uses. Folders hold files and other folders, to any depth. The first version walks the tree and checks the type of everything it meets:
long sizeOf(Object x) {
if (x instanceof File f) {
return f.bytes();
} else if (x instanceof Folder d) {
long total = 0;
for (Object child : d.children()) total += sizeOf(child);
return total;
}
throw new IllegalArgumentException("Unknown item: " + x);
}
It works. Then the team adds a tree printer, a search and a "count files" report, and each one copies the same instanceof ladder. Then product asks for zip archives that behave like folders. Now every one of those methods needs another else if, and the one somebody forgets throws at run time on the first zip it meets.
A tree, and the type checks that walk it
- Lots of things are trees: folders inside folders, boxes inside boxes, menus inside menus, teams inside departments. And we keep asking the same question of any part of the tree: how big is it?
- Without a pattern, code that walks the tree keeps asking “are you a file or a folder?”, and every new kind of item, like a zip archive, means another if/else in every place that walks the tree.
The underlying issue: the code that uses the tree has to know every kind of node, and the knowledge of "how a folder computes its size" lives outside the folder, copied into every caller.
The idea: one interface for one thing and for many
The Composite pattern gives every node in the tree the same interface. A single thing (a leaf, like a file) answers directly. A container (a composite, like a folder) answers by asking each of its children the same question and combining their answers. The caller asks the root once and never checks a type.
File and Folder share one interface; Folder holds Items
- The composite pattern gives every part one interface, Item, with size(). A File, called a leaf, returns its own size. A Folder, the composite, returns the sum of its children’s size(). The caller never needs to know which it has.
The four roles:
| Role | In this example | Responsibility |
|---|---|---|
| Component (interface) | Item | The operations every node supports: size(), show() |
| Leaf | File | A node with no children; does the work itself |
| Composite | Folder | Holds a list of components (leaves or composites) and delegates to them |
| Client | the storage screen | Talks only to Item, so one call covers a single file or a whole tree |
The key detail on the class diagram is the arrow from Folder back to Item: a folder holds items, not files. That one choice is what lets folders nest inside folders to any depth.
Build it step by step
1. The component interface. Everything a caller may ask of any node.
2. The leaf. It answers from its own data.
3. The composite. It stores children as the interface type and loops over them. It does not know or care which children are folders.
4. The client builds a tree and asks the root.
Sizes are in MB to match the figures.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// 1. The component
public interface Item {
String name();
long size(); // MB
void show(String indent); // print this node and everything under it
}
// 2. The leaf
public final class File implements Item {
private final String name;
private final long size;
public File(String name, long size) { this.name = name; this.size = size; }
public String name() { return name; }
public long size() { return size; }
public void show(String indent) { System.out.println(indent + name + " " + size + " MB"); }
}
// 3. The composite
public final class Folder implements Item {
private final String name;
private final List<Item> children = new ArrayList<>();
public Folder(String name) { this.name = name; }
public Folder add(Item child) { children.add(child); return this; } // returns this for chaining
public boolean remove(Item child) { return children.remove(child); }
public List<Item> children() { return Collections.unmodifiableList(children); }
public String name() { return name; }
public long size() {
long total = 0;
for (Item child : children) total += child.size(); // file or folder: same call
return total;
}
public void show(String indent) {
System.out.println(indent + name + "/");
for (Item child : children) child.show(indent + " ");
}
}
// 4. The client
public class Demo {
public static void main(String[] args) {
Folder photos = new Folder("Photos").add(new File("a.jpg", 3)).add(new File("b.jpg", 2));
Folder docs = new Folder("Docs").add(new File("cv.pdf", 1)).add(new File("notes.txt", 1));
Folder home = new Folder("Home").add(photos).add(docs).add(new File("song.mp3", 4));
System.out.println(home.size()); // 11
System.out.println(photos.size()); // 5: any subtree works the same way
home.show("");
}
}from abc import ABC, abstractmethod
# 1. The component
class Item(ABC):
def __init__(self, name: str):
self.name = name
@abstractmethod
def size(self) -> int: ... # MB
@abstractmethod
def show(self, indent: str = "") -> None: ...
# 2. The leaf
class File(Item):
def __init__(self, name: str, size: int):
super().__init__(name)
self._size = size
def size(self) -> int:
return self._size
def show(self, indent: str = "") -> None:
print(f"{indent}{self.name} {self._size} MB")
# 3. The composite
class Folder(Item):
def __init__(self, name: str):
super().__init__(name)
self._children: list[Item] = []
def add(self, child: Item) -> "Folder":
self._children.append(child)
return self # allows chaining
def remove(self, child: Item) -> None:
self._children.remove(child)
@property
def children(self) -> tuple[Item, ...]:
return tuple(self._children) # read-only view
def size(self) -> int:
return sum(child.size() for child in self._children) # file or folder: same call
def show(self, indent: str = "") -> None:
print(f"{indent}{self.name}/")
for child in self._children:
child.show(indent + " ")
# 4. The client
photos = Folder("Photos").add(File("a.jpg", 3)).add(File("b.jpg", 2))
docs = Folder("Docs").add(File("cv.pdf", 1)).add(File("notes.txt", 1))
home = Folder("Home").add(photos).add(docs).add(File("song.mp3", 4))
print(home.size()) # 11
print(photos.size()) # 5
home.show()Watch the recursion
One call on the root walks the whole tree
- Ask Home for its size and watch the recursion: each folder asks its children, files answer right away, and the totals add up on the way back.
home.size() calls photos.size(), which calls a.jpg (3) and b.jpg (2) and returns 5. docs.size() returns 1 + 1 = 2. song.mp3 returns 4. Home adds them: 5 + 2 + 4 = 11. Every node is visited exactly once, so the cost is O(n) for n nodes, and the call stack is as deep as the tree (here 3 frames).
Nothing in Folder.size() mentions files. Add a zip type, a symbolic link or a cloud placeholder, and Folder still works unchanged, as long as the new class implements Item.
Extending it: a new kind of node
A zip archive holds items like a folder but reports its compressed size. It is one new class:
public final class Zip implements Item {
private final String name;
private final List<Item> children = new ArrayList<>();
private final double ratio; // e.g. 0.5 = half the size
public Zip(String name, double ratio) { this.name = name; this.ratio = ratio; }
public Zip add(Item child) { children.add(child); return this; }
public String name() { return name; }
public long size() {
long raw = 0;
for (Item c : children) raw += c.size();
return Math.round(raw * ratio);
}
public void show(String indent) {
System.out.println(indent + name + " (zip)");
for (Item c : children) c.show(indent + " ");
}
}class Zip(Item):
def __init__(self, name: str, ratio: float):
super().__init__(name)
self._children: list[Item] = []
self._ratio = ratio # e.g. 0.5 = half the size
def add(self, child: Item) -> "Zip":
self._children.append(child)
return self
def size(self) -> int:
return round(sum(c.size() for c in self._children) * self._ratio)
def show(self, indent: str = "") -> None:
print(f"{indent}{self.name} (zip)")
for c in self._children:
c.show(indent + " ")File, Folder and every caller of size() are untouched: the open/closed principle again. Note that Zip and Folder now share the child-list code. If you get a third container type, pull that into an abstract Container base class.
Where do add and remove go?
This is the classic design question in Composite, and interviewers like it.
| Choice | How | Good at | Weak at |
|---|---|---|---|
| Safety (used above) | add/remove exist only on Folder | The compiler stops you adding a child to a file | To add a child you must hold a Folder, not an Item, so some callers need a cast or a type check |
| Transparency | add/remove on Item; File throws UnsupportedOperationException | Every node looks identical, so a tree editor never checks types | A mistake that the compiler could have caught becomes a run-time exception |
The original Gang of Four book leaned towards transparency; most modern code, and most interviewers, prefer safety, because a type error found at compile time is cheaper than one found in production. Java's own collections show the transparency cost: List.of(...) returns a list whose add throws at run time.
Modern forms: sealed types and pattern matching
When the set of node types is fixed and you keep adding operations (size, count, search, export to JSON), you can turn the design around. Java 21 sealed interfaces with records, or Python dataclasses with match, let one function handle each kind of node, and the compiler checks that you handled them all.
import java.util.List;
sealed interface Node permits Leaf, Branch {}
record Leaf(String name, long size) implements Node {}
record Branch(String name, List<Node> children) implements Node {}
final class Sizes {
static long size(Node n) {
return switch (n) { // exhaustive: no default needed
case Leaf l -> l.size();
case Branch b -> b.children().stream().mapToLong(Sizes::size).sum();
};
}
}from dataclasses import dataclass, field
@dataclass(frozen=True)
class Leaf:
name: str
size: int
@dataclass(frozen=True)
class Branch:
name: str
children: list = field(default_factory=list)
def size(node) -> int:
match node:
case Leaf(size=s):
return s
case Branch(children=kids):
return sum(size(k) for k in kids)
case _:
raise TypeError(f"unknown node {node!r}")This is the same tree, built the other way round. It is the well-known trade-off sometimes called the expression problem:
- Classic Composite (methods on each class): adding a new node type is one new class; adding a new operation means editing every class.
- Sealed types + switch (or the Visitor pattern in older Java): adding a new operation is one new function; adding a new node type means editing every switch (the compiler tells you where).
Pick by asking which will change more often. A UI toolkit gains widget types often: classic Composite. A compiler's syntax tree has a fixed grammar and gains passes (type check, optimise, print): sealed types or Visitor.
Where this breaks
// Iterative walk: no recursion depth limit. Requires knowing which nodes have children.
static long totalSize(Item root) {
long total = 0;
Deque<Item> stack = new ArrayDeque<>();
Set<Item> seen = Collections.newSetFromMap(new IdentityHashMap<>()); // guards cycles and sharing
stack.push(root);
while (!stack.isEmpty()) {
Item node = stack.pop();
if (!seen.add(node)) continue;
if (node instanceof Folder f) f.children().forEach(stack::push);
else total += node.size();
}
return total;
}def total_size(root: Item) -> int:
total, stack, seen = 0, [root], set()
while stack:
node = stack.pop()
if id(node) in seen: # guards cycles and shared children
continue
seen.add(id(node))
if isinstance(node, Folder):
stack.extend(node.children)
else:
total += node.size()
return totalNotice the trade: the iterative version is robust, but the type check is back. A common compromise is to give Item a children() method that returns an empty list for leaves, so the walker never needs instanceof.
Caching sizes in a big tree
Recomputing size() walks the whole subtree, O(n). For a tree of 2 million files shown in a UI that refreshes every second, that is too slow. Store a cached size in each folder and keep it correct:
- Each node keeps a parent pointer.
- When a file is added, removed or resized, walk up the parent chain and adjust each ancestor's cached total by the difference (or mark them dirty and recompute lazily on the next read).
- That update costs O(depth) instead of O(n) per read.
The cost is new invariants: the parent pointer and the parent's child list must always agree, and moving a node means updating both old and new ancestors. Concurrent edits need a lock over the path, or a single writer thread. This is exactly what file-system quota trackers and IDE project views do.
Composite, Decorator, Chain of Responsibility: how they differ
All three put objects inside objects that share an interface, so they look alike on a class diagram.
| Composite | Decorator | Chain of Responsibility | |
|---|---|---|---|
| Holds | Many children | Exactly one wrapped object | One next handler |
| Purpose | Treat a group like a single item; combine results | Add behaviour around one object | Pass a request along until someone handles it |
| A call goes to | Every child, results combined | The wrapped object, with extra work before or after | One handler at a time; usually stops at the first that handles it |
| Shape | A tree | A line of wrappers | A line of handlers |
| Example | Folder size, UI panel layout | BufferedInputStream(new FileInputStream(f)) | Middleware, approval levels |
Two more relatives: Iterator is often paired with Composite to walk the tree without exposing its structure, and Interpreter is Composite applied to a grammar (an expression (2 + 3) * 4 is a tree of number leaves and operator composites).
When not to use it
Real uses
- UI toolkits: in Java Swing,
ContainerextendsComponent, so aJPanelcan hold buttons and other panels; Android'sViewGroupextendsView. Layout and drawing recurse down the tree. - The browser DOM: every element is a
Node, and elements contain nodes. React and other UI libraries render component trees the same way. - Test frameworks: JUnit 3's
TestSuiteandTestCaseboth implementTest, so a suite of suites runs with onerun()call. - Compilers and query engines: syntax trees and query plans are composites of operator nodes.
- Business data: bills of materials (a car is parts and sub-assemblies), org charts (sum a department's salaries), product bundles (a bundle's price is the sum of its items and sub-bundles).
In the interview
Build a calculator that evaluates (2 + 3) * 4 from a tree. Sketch the classes and write evaluate(). Then say what you would change to support -x (one operand) and how you would add a print() that produces ((2 + 3) * 4).
Compare with our answer
public interface Expr {
double evaluate();
String print();
}
public record Num(double value) implements Expr {
public double evaluate() { return value; }
public String print() { return String.valueOf(value); }
}
public record BinOp(char op, Expr left, Expr right) implements Expr {
public double evaluate() {
double a = left.evaluate(), b = right.evaluate();
return switch (op) {
case '+' -> a + b;
case '-' -> a - b;
case '*' -> a * b;
case '/' -> {
if (b == 0) throw new ArithmeticException("division by zero");
yield a / b;
}
default -> throw new IllegalArgumentException("Unknown operator: " + op);
};
}
public String print() { return "(" + left.print() + " " + op + " " + right.print() + ")"; }
}
public record Neg(Expr inner) implements Expr { // one operand: still a composite
public double evaluate() { return -inner.evaluate(); }
public String print() { return "-" + inner.print(); }
}
// Client
Expr e = new BinOp('*', new BinOp('+', new Num(2), new Num(3)), new Num(4));
System.out.println(e.evaluate()); // 20.0
System.out.println(e.print()); // ((2.0 + 3.0) * 4.0)from abc import ABC, abstractmethod
import operator
OPS = {"+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.truediv}
class Expr(ABC):
@abstractmethod
def evaluate(self) -> float: ...
@abstractmethod
def print(self) -> str: ...
class Num(Expr):
def __init__(self, value: float):
self.value = value
def evaluate(self) -> float:
return self.value
def print(self) -> str:
return str(self.value)
class BinOp(Expr):
def __init__(self, op: str, left: Expr, right: Expr):
if op not in OPS:
raise ValueError(f"Unknown operator: {op}")
self.op, self.left, self.right = op, left, right
def evaluate(self) -> float:
return OPS[self.op](self.left.evaluate(), self.right.evaluate()) # "/" by 0 raises
def print(self) -> str:
return f"({self.left.print()} {self.op} {self.right.print()})"
class Neg(Expr): # one operand: still a composite
def __init__(self, inner: Expr):
self.inner = inner
def evaluate(self) -> float:
return -self.inner.evaluate()
def print(self) -> str:
return f"-{self.inner.print()}"
e = BinOp("*", BinOp("+", Num(2), Num(3)), Num(4))
print(e.evaluate()) # 20
print(e.print()) # ((2 + 3) * 4)A strong answer mentions: one Expr interface · numbers as leaves and operators as composites holding Expr children (not Num) · recursion in evaluate() with no type checks · a unary operator as a composite with one child · division by zero and unknown operators handled · that adding many new operations (print, simplify, differentiate) is where Visitor or sealed types start to pay off.
- Intent: let clients treat one object and a tree of objects the same way, through one interface.
- Roles: Component interface · Leaf (no children, answers directly) · Composite (holds
List<Component>, delegates and combines) · Client (talks only to Component). - The key arrow: a composite holds components, not leaves, so trees nest to any depth.
- Cost: one call on the root is O(n) nodes and O(depth) stack frames.
- Safety vs transparency:
add()only on the composite (compile-time safe, the usual choice) or on every node (uniform, leaves throw). - Breaks on: cycles (reject in
add()), shared children (double counting; use a seen-set), very deep trees (explicit stack), big trees read often (cached sizes updated up the parent chain). - Expression problem: classic Composite makes new node types cheap; sealed types/Visitor make new operations cheap.
- Seen in: Swing
Container, AndroidViewGroup, the DOM, JUnitTestSuite, syntax trees, bills of materials.
Your file-system model now holds 2 million files. The UI shows the size of every visible folder and refreshes once a second, and users move folders around by dragging. Recomputing size() on each refresh is too slow, and one user crashed the app by dropping a folder into its own subfolder. What do you change?
Compare with our answer
- Give every node a parent pointer, set in
add()and cleared inremove(). - Cache each folder's total. On add, remove or resize, walk up the parents and apply the size difference: O(depth) per change, O(1) per read.
- A move is a remove from the old parent (subtract up the old chain) and an add to the new parent (add up the new chain).
- In
add(), walk up from the target folder through its parents; if you reach the folder being moved, reject the move as a cycle. - If edits can come from several threads, serialise them (one writer, or a lock), because a half-applied update leaves ancestors with wrong totals.
A strong answer mentions: parent pointers · cached totals updated by the difference up the chain · moves as remove plus add · cycle check by walking ancestors · O(depth) updates and O(1) reads · a note on thread safety.
1. A UI framework has buttons, text boxes and panels, and panels can contain any widget, including other panels. Every widget must layout() and draw(). Which design fits best?
Panels contain widgets of any kind, including panels, and both answer the same calls: the textbook Composite. Separate lists or a type-checking renderer must change for every new widget, and making every widget a panel gives leaves children they should never have.
2. A team puts add(Item) on the Item interface so a tree editor can treat every node alike. What is the main cost of this choice?
This is the transparency choice: uniform nodes, but leaves throw UnsupportedOperationException on add. Putting add only on Folder (the safety choice) lets the compiler catch it instead. Performance and recursion are unaffected.
3. A user drags their Projects folder into Projects/Archive. The next call to projects.size() crashes with a stack overflow. What is the right fix?
The tree has become a cycle, so the recursion never ends. A bigger stack only delays the crash, catching it returns a wrong number, and a simple loop over direct children still has to descend. Prevent the cycle at the point it is created.
4. A product catalogue models bundles as composites of products and smaller bundles. One gift card is in two different bundles inside the same holiday mega-bundle, and its price is counted twice. What is happening?
Composite assumes a tree. When the same object appears under two parents, recursion counts it once per parent. Either forbid sharing, or keep a set of visited nodes while summing (as du does with hard links).
5. A compiler's syntax tree has a fixed set of node types, but the team adds a new pass (type check, optimise, pretty-print, lint) every few weeks. Which structure makes those changes cheapest?
With classic Composite, each new operation means editing every node class. When node types are fixed and operations keep growing, one function per operation (sealed types with an exhaustive switch, or Visitor) is the better side of the trade-off.
6. A folder view shows the size of every folder in a tree of 2 million files and refreshes every second. What is the best way to make it fast?
Recomputing is O(n) per refresh no matter which thread does it. Cached totals updated by the difference up the parent chain make each change O(depth) and each read O(1). Rebuilding a map is still a full walk, and a depth limit gives wrong answers.
7. Which pair describes the difference between Composite and Decorator?
Both share an interface with what they contain. A composite aggregates many children (a folder sums its files); a decorator wraps a single object and adds work before or after delegating (a buffered stream around a file stream).
Score 60% or more and the lesson is marked complete.