Composite pattern

12 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

A composite lets a group of objects be treated through the same interface as a single object. A folder answers size() like a file does; a bundle answers price() like a product does; a group of rate limiters answers allow() like one limiter does.
The structure is a tree: leaves do real work, composites hold children and combine their answers (sum, max, all, any, first match). Callers stop writing if isinstance(x, Folder) branches because the recursion lives inside the composite.
The hard parts are not the recursion: they are tree invariants (no cycles, one parent), aggregates that are expensive to recompute, and trees deep enough to blow the stack.
At runtime a composite chases pointers: one allocation and one indirect call per node. Fine for thousands of nodes; at millions, real systems flatten the tree into arrays.
Agents write composites readily but skip the invariants: no cycle check, no parent pointer, aggregates recomputed on every call. Review those first.

How it works

The problem

An online shop sells products and bundles. A "home office kit" is a desk, a chair and a "cable pack", and the cable pack is itself a bundle of three cables with its own 10% discount. The first version stores bundles as lists of product IDs, so the cart, the invoice and the tax code each grow a special case for one level of nesting. When marketing creates a bundle of bundles of bundles, three of them get the price wrong.

The composite answer: one Sellable interface with price(). Product implements it directly; Bundle asks each child and combines the answers. Callers never ask what kind of thing they hold.

class Bundle:
    def __init__(self, name, discount_pct):
        self.name, self.discount_pct, self.children = name, discount_pct, []

    def add(self, child):
        self.children.append(child)

    def price(self):
        total = sum(c.price() for c in self.children)
        return total * (100 - self.discount_pct) // 100

Uniform interface versus safe interface

Put add and remove on the shared interface and callers treat every node identically, but add on a leaf must fail at runtime. Put them only on the composite and the type system stops you adding a child to a leaf. Most modern code keeps reads (price, size, render) on the shared interface and building on the concrete composite. The DOM is the well-known exception: every Node has appendChild, and calling it on a text node throws HierarchyRequestError.

Combining rules are the design

How a parent combines its children encodes business meaning. A folder's size is a sum. A health group is healthy if all children are, or if a quorum is. A composite rate limiter (see Design a Rate Limiter) allows a request only if every child does, and must decide about tokens already spent by children that said yes. Write the rule down, including the empty case: is an empty bundle free, is an empty health group healthy? Most bugs live in the empty and partially failed cases.

Tree invariants

A composite that accepts any child can become a graph by accident. A bundle that contains itself recurses until the stack overflows; a cable pack added to two kits changes both when edited for one. A robust add enforces:

No cycles: the child must not be this node or any of its ancestors.
One parent: a node already attached elsewhere must be detached first. If you truly want one subtree in many places, you have a directed acyclic graph with parent lists, and must decide whether a shared leaf counts once or once per path.
Unique names among siblings when children are addressed by name, as in file paths.

A parent pointer makes the first two checks cheap: walk up from self looking for child, costing the tree's depth rather than its size. The DOM refuses to insert an ancestor into its own descendant the same way.

Cached aggregates

Recomputing price() across a 5,000-node tree on every page view is wasteful when the tree changes hourly. Cache each composite's aggregate and invalidate upward: when a child changes, mark the parent dirty, and its parent, up to the root. Reads recompute only dirty subtrees. Browser layout marks boxes "needs layout" up the ancestor chain the same way, and Merkle trees rehash only the changed path.

Reviewing agent-written code

Asked to "support nested bundles", an agent usually adds a recursive price() and nothing else. Check that add rejects cycles and double attachment, that the empty case is defined, that depth is capped, and that hot aggregates are cached with upward invalidation. Leftover isinstance checks in callers mean the interface is missing an operation.

The same shape elsewhere

Composite is the fan-out shape as an object: one request goes to every child and the answers fold back up. Linux cgroups v2 has the same shape: a parent's memory limit bounds its children, and usage is charged up the hierarchy. So do query planners, whose AND and OR nodes combine child predicates.

Down the stack

Layer 1The contract

Every operation on the shared interface means the same for a group as for a leaf, with a documented combining rule and result for zero children. The structure is finite and acyclic, each node has one parent (or a declared sharing model), and a read after a mutation reflects it. A cache must be invisible: price() returns exactly what a fresh recursive computation would.

Layer 2The mechanism

The data structure is a node with a child list and usually a parent pointer. The DOM's Node exposes parentNode, firstChild, lastChild, previousSibling and nextSibling: children form a doubly linked list, so insertion and removal are O(1). React's Fiber nodes use child, sibling and return pointers, which let React walk the tree with a loop instead of recursion, so rendering can pause and resume between nodes.

Since Go 1.20 an error can implement Unwrap() []error, and errors.Join(a, b) returns one. errors.Is and errors.As traverse the resulting tree in pre-order, depth first, calling Unwrap at each node: a composite in the standard library.

Layer 3The machine

Each node is a separate heap allocation. A Go node with a name string (16 bytes), a child slice (24), a parent pointer (8) and a cached int (8) is 56 bytes, rounded to the 64-byte size class, plus the slice's backing array. A CPython node with a __dict__ is over 200 bytes; __slots__ brings it to roughly 70. Nodes are allocated at different times, so siblings rarely share a cache line, and walking a million nodes pays roughly a DRAM miss per node, 80 to 100 ns: about 0.1 s per full walk, against a few milliseconds to scan the same data packed in an array.

Each child call is an indirect call: a Go itab lookup, a C++ or Java vtable call, or a V8 property access that stays fast while the call site sees few node shapes. Recursion costs a stack frame per level. CPython's default recursion limit is 1,000, so a 1,500-deep tree raises RecursionError; goroutine stacks start at a few KB and grow by copying, so Go survives deep trees but pays for each growth.

Concurrency adds a cost. Upward invalidation touches every ancestor, so per-node locks force writers to lock a path in a fixed order to avoid deadlock. Many systems take one lock for the whole tree, or make it immutable and copy the changed path, so readers traverse an old version without locks.

Why it's built this way

Business objects nest, so code that handles one level of nesting breaks on the next.
Recursion inside the node type removes nesting from every caller, at the cost of an indirect call per node.
Arbitrary children can form cycles, so add checks invariants via a parent pointer, at a cost proportional to depth.
Recomputing aggregates costs a cache miss per node, so composites cache and invalidate upward along the same pointers.
At millions of nodes pointer chasing dominates, so hot paths flatten trees into arrays.

Diagram

sequenceDiagram
  participant C as Cart
  participant K as "Kit (0%)"
  participant P as "Cable pack (10%)"
  participant D as Desk
  participant X as Cables
  C->>K: price()
  K->>K: cache dirty
  K->>D: price()
  D-->>K: 25000
  K->>P: price()
  P->>X: price() each
  X-->>P: 3 x 1500
  P->>P: 4500 x 90% = 4050, cache
  P-->>K: 4050
  K->>K: 29050, cache
  K-->>C: 29050
  C->>K: price() again
  K-->>C: 29050 (cached)

Worked example

A B2B catalogue holds 40,000 products and 6,000 bundles, nested up to 6 levels. The storefront renders bundle prices at 3,000 requests a second, about 20 bundles per page.

Without caching, pricing a bundle walks its subtree. The median subtree is 60 nodes and the largest 9,000; at roughly 100 ns per node in Go, that is 6 us and 0.9 ms. A page listing several large kits takes up to 18 ms in pricing alone, and those are the pages the sales team demos.

With cached aggregates, a read is one dirty-flag check, under 10 ns. Writes are rare (about 200 price changes an hour from the ERP feed), and each marks at most 6 ancestors dirty, or the 300 kits that share a popular cable pack. Each dirty kit recomputes on its next read by summing direct children, most still cached.

The rollout found one bug: the ERP feed set a product's price field directly, so nothing marked its parents dirty and kits showed old prices for an hour. The fix made cents private behind set_price(), which walks up the parents, plus a nightly job that recomputes every bundle from scratch and alerts on any mismatch.

Trade-offs

Option	Strengths	Weaknesses	Choose when
Type checks in callers	No new abstraction	Every caller handles nesting; breaks on deeper trees	One level of grouping, never nested
Composite, recomputed each call	Simple, always correct	Cost grows with subtree size on every read	Small trees or rarely read aggregates
Composite with cached aggregates	Reads O(1) after the first	Invalidation bugs; writes cost depth	Large trees read far more than written
Shared subtrees (DAG)	One definition reused in many places	Multiple parents, double counting decisions	Reusable components such as kits or templates
Flattened arrays (parent index, child ranges)	Cache friendly, fast bulk scans	Hard to mutate; loses the object interface	Millions of nodes, bulk analytics, game engines

Pitfalls in production

A cycle introduced by an import, then a stack overflow on every request touching that tree. Fix: check ancestors in add and cap depth at the API.
Mutating a leaf's field directly so cached ancestors go stale. Fix: make aggregated fields private behind methods that invalidate upward, and run a periodic full recompute that compares results.
Undefined empty cases: an empty health group reported healthy, so a misconfigured check with no members passed for months. Fix: decide and test the result for zero children, and often reject empty composites.
Deep recursion on user-supplied trees (nested comments, imported org charts). Fix: iterate with an explicit stack, or reject excess depth.
One node attached to two parents by accident, so a change for one customer edits another's bundle. Fix: enforce one parent, and make sharing an explicit, separate operation.

Leadership lens

In design review, ask for the combining rule, the empty case and the failure case for each operation on the composite. Those three answers are the composite's real specification.
Ask where tree invariants are enforced. If the answer is "the UI prevents it", the import job, the API and the agent writing a migration will not.
Budget for depth and fan-out limits as product decisions. "Bundles may nest 5 deep and hold 500 items" is cheaper than discovering the limit during an outage.
Cached aggregates need an owned invalidation path. Ship a reconciliation job and a mismatch metric with them, not in a follow-up.

Check yourself

Why does a parent pointer make cycle detection in add cheap?
Show answer
Adding child under node creates a cycle only if child is node or one of its ancestors, so walking up from node checks it in time proportional to depth instead of searching the whole subtree.
A health-check composite has no children. What should it return, and why does the question matter?
Show answer
There is no universally right answer, so it must be decided; returning healthy hides misconfiguration, which is why many systems treat an empty group as an error or as unhealthy.
Why must invalidation go upward rather than downward?
Show answer
A change to a node changes the aggregates of the nodes that contain it, which are its ancestors; its descendants' values do not depend on it.
When would you flatten a composite into arrays?
Show answer
When the tree has millions of nodes and hot paths scan it in bulk, so pointer chasing and per-node calls dominate; you keep the object interface at the edges for building and editing.

Watch

Composite Pattern, Design Patterns ep 14 (Christopher Okhravi): the Gang of Four structure and the uniform versus safe interface debate.
The Composite Pattern Explained and Implemented in Java (Geekific): a short build of leaf and composite classes in code.

Free resources

The Composite Pattern (Brandon Rhodes, python-patterns.guide): how the pattern looks in Python, and how duck typing changes the uniform interface question.
Composite (Refactoring Guru): the structure, applicability and relations to other patterns.
Node (MDN): the DOM's composite node, with its parent and sibling pointers and insertion rules.
React Fiber Architecture (Andrew Clark): why a UI tree uses child, sibling and return pointers to traverse without recursion.
errors (Go docs): errors.Join and the depth-first traversal of error trees.
Control Group v2 (Linux kernel docs): a composite in the kernel, with hierarchical limits and accounting.

Open in the interactive app: practice, quiz, mock interview →