9.4.11 — Composite

What the original Gang of Four book says: Compose objects into tree structures to represent part-whole hierarchies. Composite lets clients treat individual objects and compositions of objects uniformly.

What that means when you are actually writing code: When a thing can contain more of the same thing — a folder holds files and folders, a team holds members and teams — give the single item and the container the same interface. Then code that works on the whole works on any part, and it never has to ask whether it is holding one thing or many.

Composite is recursion turned into objects. Every tree you have worked with is one: folders holding files and folders, a web page's elements holding more elements, a nested menu, an org chart, an arithmetic expression built from smaller expressions.

The payoff is specific. Code that walks the tree never asks "is this a single item or a container?", because both answer the same questions, and the recursion happens inside the objects rather than in every piece of code that touches them.

1. The story: the if (isFolder) that spread everywhere

You model a filesystem. A folder contains files; a file has a size. Computing total size looks innocent:

function totalSize(node: File | Folder): number {
  if (node instanceof Folder) {                      // ← the fork
    let sum = 0;
    for (const child of node.children) {
      sum += child instanceof Folder                 // ← the fork again, nested
        ? totalSize(child)
        : child.size;
    }
    return sum;
  }
  return node.size;
}

It works. Then you add countFiles, findByName, permissionsSummary, serialize, render — and every one repeats the same if (isFolder) … recurse … else … leaf skeleton. The type check on "is this a container or a leaf?" is duplicated across every operation, and each new operation is another chance to get the recursion wrong. Add a third node type (a symlink) and you edit every function.

The deeper problem: the client is forced to know the tree's shape. Every caller branches on node kind, so the knowledge "a folder contains children you must recurse into" leaks out of the folder and into every algorithm that touches the tree.

Composite's move: give File and Folder the same interface, and let each node implement each operation for itself — a file returns its own size; a folder asks its children (which may be files or folders — it does not care) and sums. The client calls node.size() and the recursion happens inside the objects.

node.size();          // works whether node is a file or a folder — no fork, no instanceof
node.count();         // same
node.find("x.pdf");   // same

2. Deriving the pattern

Step 1 — The naive code. Separate types for leaf and container, and client code that branches on which it has. Correct when the structure is flat (a list, not a tree) or shallow and fixed.

Step 2 — The force. The data is a part-whole hierarchy — a container can hold both leaves and other containers, to arbitrary depth — and you have operations that must traverse the whole thing. The instanceof forks multiply across operations.

Step 3 — The varies/fixed line.

What varies	whether a node is a leaf or a container (and how deep the nesting goes)
What is fixed	the operations every node must answer — size, render, find, whatever the domain needs

The fixed operations become a shared Component interface. Both Leaf and Composite implement it. The container implements each operation by delegating to its children through the same interface — which is the recursion, now living in the objects rather than in every client.

Step 4 — Binding time. Runtime composition: containers hold a list of Component children, built into a tree at runtime. The tree's shape is data; the operations are polymorphic dispatch (9.2.5 — dispatch replaces the if).

Step 5 — Name it, and name its cost. The name is Composite. The costs:

• The shared interface is either too wide or too narrow. Too wide, and leaves must implement add(child) and remove(child), which make no sense for them. Too narrow, and clients must cast down to reach container-only operations, which partly defeats the point. This is the pattern's central tension (section 6).
• Very deep trees can cause a stack overflow with simple recursion.
• It can be forced onto data that is not really a tree.

The benefit is decisive: uniform client code, new operations without touching the structure, and new node types without touching the operations.

3. The mental model

One sentence: A composite is a set of Russian nesting dolls where every doll — the tiny solid one and every hollow one containing others — responds to the same question, so you can ask "how much do you weigh?" of any doll and it figures out its own answer.

The analogy that makes it stick — the org chart. Ask any employee "what is your total headcount?" An individual contributor answers "1" (a leaf). A manager answers "1, plus the headcount of everyone reporting to me" — and each report answers the same question the same way, whether they are an IC or a manager themselves. You, asking the CEO, get the whole company's headcount from one question, and you never had to know the shape of the org — each node knew how to answer for itself and its subtree.

The recognition trigger. "A folder contains files and folders" · "a team has members and sub-teams" · "a menu has items and sub-menus" · "a shape can be a group of shapes" · "a UI is components containing components" · "an expression is operators applied to expressions." Underneath all of these, the tell has two halves. First, an X can contain other Xs, so the structure holds smaller copies of itself. Second, you want to run one operation over the whole tree in the same way, whatever each node is. If the containing never repeats, meaning a container holds only plain items and never another container, you probably do not need Composite. A plain list is enough.

The one insight that makes Composite click — the container is also a Component. The reason clients stop branching is that a Composite is-a Component, so a container's children list can hold leaves and other containers interchangeably, and a container's implementation of an operation calls the same operation on its children without knowing or caring what they are. The recursion is not in the client; it is in the fact that the container treats its children as Components.

4. Structure

Figure 11 — One interface, a tree of it. Leaf (green) and Composite (amber) both implement Component. A Composite holds a list of Components — which may themselves be leaves or composites — so the tree nests arbitrarily. The client calls an operation on the root; each node answers for itself and containers delegate to their children through the same interface. The recursion lives in the objects, not the client.

Participants:

• Component is the shared interface for leaves and containers. It declares the operations.
• Leaf is a node with no children. It does each operation itself.
• Composite is a node that holds child Components. It does each operation by asking its children and combining their answers. It also manages its list of children.
• Client works with the whole tree through Component, without caring which kind of node it has.

5. The implementation, line by line

// ── The shared interface — leaf and container both implement it (the FIXED part)
interface FsNode {                                        // (1)
  name: string;
  size(): number;                                         //     an operation every node answers
  print(indent?: string): void;
}

// ── Leaf: answers for itself, no children
class FileNode implements FsNode {                        // (2)
  constructor(readonly name: string, private readonly bytes: number) {}
  size() { return this.bytes; }                           //     base case of the recursion
  print(indent = "") { console.log(`${indent}${this.name} (${this.bytes}b)`); }
}

// ── Composite: holds children, delegates to them
class FolderNode implements FsNode {                      // (3)
  private readonly children: FsNode[] = [];               // (4) children are FsNode — leaf OR folder
  constructor(readonly name: string) {}

  add(child: FsNode): this { this.children.push(child); return this; }   // (5) container-only op
  remove(child: FsNode): this { /* … */ return this; }

  size(): number {                                        // (6) recursive case: ask each child
    return this.children.reduce((sum, c) => sum + c.size(), 0);
  }
  print(indent = "") {                                    // (7) delegate the SAME op to children
    console.log(`${indent}${this.name}/`);
    for (const c of this.children) c.print(indent + "  ");
  }
}

1. The FsNode interface is what makes the client uniform. It declares only operations meaningful to every node. Notice add/remove are not here — that is the deliberate design choice of section 6 (the transparency-vs-safety trade). Put only genuinely universal operations in Component.
2. The leaf implements each operation directly — size() returns its own bytes, the base case of the recursion. A leaf has no children and never recurses.
3. The composite implements the same interface — so a FolderNode is substitutable anywhere an FsNode is expected, which is why a folder can be a child of another folder.
4. Children are typed as FsNode, not FileNode. This one line is the pattern: because children are the interface type, a folder's child list holds files and folders interchangeably, and the folder's operations work on them without ever asking which they are.
5. add/remove are container-only, returning this for fluent tree building (root.add(a).add(b)). Where these live — on Composite only, or on Component — is the pattern's key decision (section 6).
6. size() is the recursive case: delegate to children, combine. The folder does not know or care whether each child is a file (returns its bytes) or a folder (recurses into its children). reduce sums whatever each child reports. This is the whole pattern in one line — the container performs the operation by asking its children to perform the same operation.
7. print() shows the same shape for a different operation — delegate to children, combine (here, ordering + indentation). Every new operation follows this template: leaf does it directly, composite delegates and combines. No instanceof anywhere.

Output / behavior:

const root = new FolderNode("root")
  .add(new FileNode("a.txt", 100))
  .add(new FolderNode("sub").add(new FileNode("b.txt", 200)).add(new FileNode("c.txt", 50)));

root.size();   // → 350  — recursion handled by the objects; the caller wrote no loop and no instanceof
root.print();  // root/ \n   a.txt (100b) \n   sub/ \n     b.txt (200b) \n     c.txt (50b)

5.1 Adding operations without touching the structure

Every new tree operation is the same template — leaf answers, composite delegates-and-combines:

interface FsNode { /* … */ count(): number; find(name: string): FsNode | null; }

// Leaf
count() { return 1; }
find(name: string) { return this.name === name ? this : null; }

// Composite
count() { return this.children.reduce((n, c) => n + c.count(), 0); }
find(name: string): FsNode | null {
  if (this.name === name) return this;
  for (const c of this.children) { const hit = c.find(name); if (hit) return hit; }
  return null;
}

Adding count and find touched only the node classes. No calling code changed, and not one instanceof appeared anywhere. That is Composite's real payoff: you can keep adding operations, and the shape of the tree and the list of operations stop being tangled together.

There is one situation where this stops working, and it is worth knowing the name of it. If the operations must live outside the node classes — because the nodes come from a library you cannot edit, or because you do not want a dozen unrelated jobs piled onto them — then you want Visitor instead, which is described in one line in 9.4.1 section 2. Compilers pair a tree with visitors for exactly this reason. Ordinary application code almost never needs to.

5.2 The functional / data spelling

In TypeScript, a tree is often a discriminated union and operations are functions with exhaustive switch — the same pattern without classes:

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

function size(node: FsNode): number {
  switch (node.kind) {                                    // exhaustive — tsc enforces all cases
    case "file":   return node.bytes;
    case "folder": return node.children.reduce((s, c) => s + size(c), 0);   // recurse
  }
}

This trades OOP's "add operations freely" for FP's "add node kinds freely with compiler-checked exhaustiveness" (3.7.3). It is the idiomatic choice when the node set is stable and you prefer operations as standalone functions — common in compilers and interpreters, where the AST is a Composite (3.11).

5.3 Python

from abc import ABC, abstractmethod

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

class File(FsNode):
    def __init__(self, name, bytes_): self.name, self._bytes = name, bytes_
    def size(self): return self._bytes

class Folder(FsNode):
    def __init__(self, name): self.name, self.children = name, []
    def add(self, child): self.children.append(child); return self
    def size(self): return sum(c.size() for c in self.children)   # delegate + combine

6. The core design decision — transparency vs safety

Composite has one famous tension, and interviewers probe it: where do the child-management operations (add, remove, getChild) live?

• Transparent Composite — put add/remove on Component. Every node, leaf included, has add/remove. Benefit: total uniformity — clients treat every node identically and never downcast. Cost: a File now has an add(child) that is meaningless and must throw or no-op — an 9.3.7 LSP violation (a leaf cannot honor the container contract), and a runtime error waiting to happen.
• Safe Composite — put add/remove on Composite only. Leaves genuinely cannot have children added. Benefit: the type system prevents nonsense (file.add(x) does not compile). Cost: clients that hold a Component must check/downcast to Composite before adding children, so uniformity is partial.

GoF leaned transparent (uniformity first); modern typed languages usually lean safe (correctness first) — the section 5 implementation is safe (add/remove on FolderNode only), because in TypeScript a compile error beats a runtime throw. The rule to carry: operations that every node truly answers go on Component; operations only containers can perform go on Composite. size(), print(), find() are universal → Component. add(), remove() are container-only → Composite. This keeps the interface honest (no method a leaf must fake) while preserving uniformity for the operations that matter — the ones clients actually call across the whole tree.

7. Variants and practical concerns

Variant / concern	Shape	Notes
Transparent	add/remove on Component	max uniformity, leaves fake container ops
Safe	add/remove on Composite only	type-safe, partial uniformity — the typed default
With parent pointers	each node knows its parent	enables upward traversal, path(), removal-from-parent; costs a back-reference to maintain
Cached aggregates	composite memoizes size() etc.	fast repeated reads; needs invalidation on mutation
Discriminated-union / data	union + functions	FP spelling; compiler-checked node kinds (5.2)
Iterative traversal	explicit stack/queue instead of recursion	avoids stack overflow on very deep trees

Two practical concerns worth stating in an interview. (1) Deep trees and the stack. Naive recursion (c.size() calling into children) uses the call stack, so a pathologically deep tree can RangeError: Maximum call stack size exceeded. For untrusted or unbounded depth, traverse iteratively with an explicit stack. (2) Cached aggregates and invalidation. If size() is read far more than the tree changes, cache it on each composite and invalidate up the parent chain on mutation — a real optimization for large stable trees (filesystems compute directory sizes this way), but it reintroduces the cache-invalidation problem, so only add it when reads dominate.

8. Where you already use it

What you have used	What contains what
Files and folders	a folder holds files and more folders
A web page's elements	a div holds text, images and more divs
A JSON document	an object holds values, arrays and more objects
A nested menu	a menu item can open another menu
An expression tree in a compiler (3.11)	an operator holds smaller expressions

Folders are the example this pattern was invented from, and the one that proves it. "How big is this folder?" has the same answer shape whether the folder holds three files or three hundred folders each holding more: ask every child how big it is, then add up the answers. The code doing the asking never checks which kind of child it is talking to. That single property — a container answering the same question as the things inside it — is the whole pattern.

9. Pitfalls and misuse

1. Using it when there is no tree. A flat list of items, or a container that holds only leaves (never other containers), does not need Composite — a list and a loop are simpler. Trigger: if "an X contains Xs" is false, reconsider.

2. The transparency LSP violation. add/remove on Component forces leaves to implement meaningless methods that throw.

   Fix: safe Composite — container ops on Composite only (section 6).

3. Stack overflow on deep trees. Naive recursion on unbounded/untrusted depth.

   Fix: iterative traversal with an explicit stack.

4. Cycles. If a node can (accidentally) become its own ancestor, traversal loops forever.

   Fix: it is a tree, not a graph — prevent cycles on add (reject adding an ancestor), or track visited nodes if the structure is genuinely a DAG.

5. Fat Component interface. Cramming container-only and leaf-only operations into one interface so everything must fake half of them (9.3.8 ISP).

   Fix: Component holds only universal operations.

6. Mutable shared children. The same node instance added under two parents (aliasing) — a mutation or a parent-pointer update corrupts both.

   Fix: trees own their children; clone (9.4.5) if a node must appear in two places.

7. Expensive repeated aggregates. Recomputing size() over a huge tree on every read.

   Fix: cache with invalidation, but only when reads dominate (section 7).

10. Composite vs its neighbors

Compared with	Distinction	Choose Composite when
Decorator	Decorator is a single wrapper adding behavior; Composite is a tree of many treated uniformly	the structure is part-whole, not layered
Visitor (9.4.1 section 2)	keeps operations outside the nodes	you can edit the node classes
Iterator	Iterator traverses a structure; Composite is the structure (often iterated)	you are modeling the tree, not just walking it
Chain of Responsibility	a straight line looking for one handler	a branching tree, operated on as a whole
A recursive function over a union of types	the same idea written without classes	you want the operations to be methods

Composite and Decorator are cousins — both build recursive structures of same-interface objects — and the distinction is shape and purpose. A Decorator is a degenerate Composite with exactly one child, used to add behavior by layering; a Composite is a tree with many children, used to represent a part-whole hierarchy operated on uniformly. When you see "same interface, holds one → adding behavior" think Decorator; "same interface, holds many → a hierarchy" think Composite.

11. Interview calibration

The 45-second answer, in the order you would say it:

Composite is for part-whole trees — a folder holds files and folders, a team holds members and teams. Both the leaf and the container implement one Component interface, and the container implements each operation by delegating to its children through that same interface, so the recursion lives in the objects, not the client. The payoff is that client code never branches on 'is this a leaf or a container' — node.size() works on any node — and you can add operations without touching the structure.

The key design decision is transparency versus safety: put add/remove on the Component for total uniformity but then leaves fake those methods (an LSP violation), or put them on the Composite only for type safety at the cost of some downcasting. In typed languages I lean safe — universal operations on Component, container-only operations on Composite. The DOM, React trees, and ASTs are all Composites.

Follow-ups, with the seed of each answer:

• "Transparency vs safety?" — add/remove on Component (uniform, leaves fake it) vs on Composite (type-safe, some downcasting). Typed languages lean safe.
• "How do you add a new operation?" — Add it to Component; leaf answers directly, composite delegates-and-combines. Zero client changes, zero instanceof.
• "Composite vs Decorator?" — Decorator is a one-child wrapper adding behavior; Composite is a many-child tree representing a hierarchy.
• "What about very deep trees?" — Naive recursion can overflow the stack; traverse iteratively for untrusted depth.
• "Where's the FP version?" — A discriminated union plus functions with exhaustive switch — trades open-operations for compiler-checked open-node-kinds.

Recall

• Composite = recursion as objects: a part-whole tree where leaf and container share one Component interface, so client code never branches on "leaf or container." A container implements each operation by delegating the same operation to its children (typed as Component, so they may be leaves or containers interchangeably) and combining results — the recursion lives in the objects.
• The payoff: operations and structure vary independently. A new operation is one method (leaf answers directly; composite delegates-and-combines) with zero client changes and zero instanceof. A new node kind is one class with zero operation changes.
• The core design decision — transparency vs safety: put add/remove on Component (total uniformity, but leaves must fake container ops — an 9.3.7 LSP violation) or on Composite only (type-safe, but clients downcast to add children). Typed languages lean safe: universal ops (size, find, render) on Component; container-only ops (add, remove) on Composite.
• Recognition: "an X contains Xs" (self-similar containment) + "operate over the whole tree uniformly." If containment is not recursive, a list suffices — do not over-apply. Practical concerns: deep trees can overflow the stack (traverse iteratively); prevent cycles (it is a tree, not a graph); cache aggregates only when reads dominate.
• Everywhere: the DOM, React/Vue component trees, the filesystem, ASTs/expression trees (3.11), nested menus, org charts, scene graphs, JSON. FP spelling: a discriminated union + functions with exhaustive switch (open node-kinds instead of open operations). Vs Decorator: Decorator is a one-child wrapper adding behavior; Composite is a many-child hierarchy operated on uniformly.

Self-test: What single line makes a container's children able to be leaves or containers interchangeably? How do you add a new operation, and what does it not require? State the transparency-vs-safety trade and which typed languages prefer. When is Composite the wrong choice? Give the Composite-vs-Decorator distinction in one sentence.

Quiz Bank

FoundationalDerive Composite from instanceof-laden traversal code and state its central payoff.

Naive: separate File and Folder types, and a totalSize(node) that does if (node instanceof Folder) { recurse over children } else { return node.size }. Correct for a flat or shallow fixed structure. Force: the data is a genuine part-whole hierarchy — a folder holds files and folders to arbitrary depth — and you accumulate operations over it (size, count, find, render, serialize).

What breaks: every operation repeats the same if (isContainer) … recurse … else … leaf skeleton, so the "is this a container?" check is duplicated across every function, each new operation is a fresh chance to get the recursion wrong, and adding a third node type edits every function; worse, the client is forced to know the tree's shape because every caller branches on node kind.

Varies/fixed line: what varies is whether a node is a leaf or a container (and how deep it nests); what is fixed is the operations every node must answer. The pattern: one shared Component interface, implemented by both Leaf and Composite.

• The leaf does each operation itself. That is the base case.
• The composite does each operation by asking its children to do the same operation, then combining their answers. That is the recursive case. Its children are typed as Component, so it never has to ask whether a child is a leaf or a container.

The central payoff: operations and structure vary independently. Client code never branches on leaf-vs-container (node.size() works on any node), a new operation is one method per node class with zero client changes and zero instanceof, and a new node kind is one class with zero operation changes.

Cost: the transparency-vs-safety tension over where add/remove live, stack-overflow risk on deep trees, and over-application to data that is not actually a tree.

FoundationalExplain the transparency-versus-safety decision in Composite and which way typed languages lean.

The decision is where the child-management operations (add, remove, getChild) live, and it trades uniformity against type safety. Transparent Composite puts them on the Component interface, so every node — leaves included — has add/remove. The benefit is maximum uniformity: a client holding any Component can attempt to add a child without downcasting, and the code treats all nodes identically. The cost is that a leaf (File) now has an add(child) method that is meaningless — it must throw UnsupportedOperationException or silently no-op — which is a Liskov Substitution violation (9.3.7): a leaf cannot honor the container contract, so substituting a leaf where the code calls add fails at runtime. GoF leaned this way, prioritizing uniformity in an era of less expressive type systems.

Safe Composite puts add/remove on the Composite class only, so leaves genuinely lack them. The benefit is that the type system prevents nonsense — file.add(x) does not compile — and the interface stays honest (no method a leaf must fake). The cost is partial uniformity: a client holding a Component must narrow to Composite before adding children.

Typed languages (TypeScript, Kotlin, Rust, modern Java) lean safe. A compile error is always better than a throw at runtime. And you do not lose the sameness that matters. The operations clients run across the whole tree, such as size, render and find, stay on Component, and every node still answers them. Only the operations that build the tree move to Composite. Clients call those far less often, and usually in code that already knows it is holding a container.

The rule to carry: put operations every node truly answers on Component; put operations only containers can perform on Composite. That keeps the interface free of methods a leaf must fake (9.3.7 ISP + LSP together) while preserving the uniformity that is the pattern's whole point.

AppliedShow that adding a new operation to a Composite needs no changes in calling code, and say honestly what that costs you.

Every new operation follows the same two-line template. The leaf answers for itself. The container asks its children and combines their answers.

To add count(): a File returns 1, and a Folder returns this.children.reduce((n, c) => n + c.count(), 0).

To add find(name): a File returns itself when the name matches and null otherwise. A Folder checks itself, then loops over its children calling the same find, and returns the first hit.

Calling code does not change at all, and it contains no instanceof. Callers write node.count() or node.find(name) and the object they happen to be holding decides what that means. The recursion lives inside the objects, not in the caller.

Now the honest cost, and it is worth getting the direction right because people state it backwards. Putting the operations on the nodes makes it cheap to add a new kind of node: you write one new class, implement the operations it needs, and nothing else in the codebase moves. It makes it expensive to add a new operation: that means opening every single node class and adding a method to each one.

There is also a harder version of the same cost. If you cannot edit the node classes — they belong to a library, or you would rather not pile unrelated jobs onto them — then you cannot add operations this way at all.

That harder version is what the Visitor pattern from 9.4.1 section 2 exists for. Visitor moves each operation out of the nodes and into its own separate object, which then gets handed every node in turn. Now a new operation is one new object and no node class is touched. The cost simply moves: a new kind of node now means editing every operation object you have.

Trading one of these costs for the other is the whole of what people call the expression problem, and no arrangement escapes it. You only get to choose which side hurts.

TypeScript gives you a third option that is usually better than either. Describe the node kinds as a union of types and write each operation as a plain function with a switch over the kinds. Adding an operation is one new function. Adding a node kind is a compile error in every switch until you handle it, which means the compiler hands you the exact list of places to edit instead of leaving you to find them.

So, practically: put the operations on the nodes when your set of node kinds is fairly settled. That is the common case and it is the lighter design. Reach for Visitor only when the operations genuinely have to live outside a node hierarchy you cannot or should not edit. Compilers pair a tree with visitors for exactly that reason, but an ordinary application tree almost never needs it.

InterviewWhen is Composite the wrong choice, and what are the practical hazards even when it is right?

Wrong choice in three situations. (1) There is no recursion. Suppose a container only ever holds plain items, never other containers, like a playlist of songs or a cart of line items. Then the "things inside things of the same kind" that Composite is for is missing. A plain list and a loop is simpler and clearer. Forcing a Component interface onto it is just ceremony (9.4.1 section 6).

(2) The structure is a graph, not a tree — if a node can have multiple parents or cycles are possible, naive Composite traversal loops forever or double-counts; you need cycle detection (visited-set traversal) or a different model, and calling it "Composite" obscures that it is really a DAG or graph.

(3) The nodes are truly heterogeneous — if leaf and container share almost no meaningful operations, forcing them under one interface produces a fat interface where everything fakes half the methods (9.3.8 ISP); the uniformity Composite promises requires that a genuinely shared set of operations exists.

Practical hazards even when Composite is right. Stack overflow: naive recursion (child.size() descending the tree) consumes the call stack, so a pathologically deep or untrusted-depth tree throws RangeError: Maximum call stack size exceeded; for unbounded depth, traverse iteratively with an explicit stack/queue.

Cycles from aliasing: adding the same mutable node instance under two parents, or accidentally adding an ancestor as a descendant, creates a cycle or shared-mutation corruption; enforce tree invariants on add (reject adding an ancestor) and clone (9.4.5) a node that must appear in two places.

Expensive repeated aggregates: recomputing size() over a huge tree on every read is O(n) each time; cache the aggregate on each composite and invalidate up the parent chain on mutation — but only when reads dominate writes, because it reintroduces cache invalidation.

Serialization depth: serializing a deep tree can hit the same recursion limits and can be surprisingly large. The senior framing: Composite is the correct default for bounded, acyclic, homogeneous-operation trees, and each hazard corresponds to violating one of those assumptions — unbounded (stack), cyclic (loops), or heterogeneous (fat interface).

StaffDesign the document model for a page-builder / no-code tool where users compose pages from components (containers, columns, text, images, forms) nested arbitrarily, with operations like render, serialize, validate, computeStyles, and find-by-id, plus drag-and-drop reparenting and undo. Use Composite and address the real complications.

A page builder is the most natural home Composite has. A page is a tree of components. Containers hold components, and some of those components are containers too, nested as deep as the user likes. So the model is one Component interface. Leaves such as Text and Image implement it. Composites such as Container, Column and Form implement it too. The tree operations live on the nodes.

The interface is split for safety, as in section 6. Operations that every node can answer go on Component: render(), serialize(), validate(), computeStyles(inherited) and findById(id). Operations that only make sense on a container go on the Container type: add, remove, insertAt and moveChild. Because of that split, text.add(child) does not compile.

computeStyles is worth a closer look, because it is recursive and it passes things down. A container first works out its own styles from what it inherited from its parent. Then it hands the merged result down to each child's computeStyles. That is the usual Composite pattern of asking the children, but now carrying collected state downward as it goes. CSS does exactly this. The CSS cascade is itself a Composite operation over the page.

Each operation follows the same template:

• serialize(): a leaf writes out its own JSON. A container writes its type plus its children's JSON. So the whole page is saved by calling root.serialize() once.
• validate(): a leaf checks its own rules. A container checks itself, then collects its children's errors. So a form's rule "at least one submit button" and a text node's rule "must not be empty" end up in one error list.
• findById: the recursive search from section 5.1. The editor needs it all the time, because it always has to find "the node the user clicked".

The real complications, which is what makes this a staff question. (1) Every node needs a stable id and a parent pointer. Drag-and-drop reparenting requires knowing a node's current parent to detach it, and findById is called constantly, so ids are mandatory and parent pointers ([7] variant) make reparent and delete O(1) at the cost of maintaining the back-reference on every structural change — a worthwhile trade here.

(2) Reparenting must preserve the tree invariant — no cycles. Dragging a container into its own descendant would create a cycle that hangs every subsequent traversal; the moveChild operation must reject a move where the target is a descendant of the moved node (walk up the target's parent chain checking identity), which is the cycle-prevention hazard of section 10 made concrete and essential.

(3) Undo and redo change how you store the tree. There are two designs that work, and they are quite different.

The first is to make the tree read-only. Every edit produces a new root rather than changing anything in place, and the parts of the tree that did not change are reused by both the old root and the new one, so a new root is cheap rather than a full copy. Undo then means nothing more than pointing at the previous root. This is the copy-on-write approach from 9.4.5.

The second is to keep the tree editable and, on every edit, save a copy of just the part that is about to change so you can put it back later.

For an editor the read-only tree is usually the better choice, for two reasons. Undo, redo and stepping back through history all become almost free. And it removes the sharing bug described above entirely, because a node that two parents both point at cannot be changed by either of them if nodes cannot be changed at all.

(4) Rendering performance on large pages — recomputing render()/computeStyles() over the whole tree on every keystroke is too slow, so cache computed styles per node and invalidate only the affected subtree on edit (the cached-aggregate variant of section 7), or use the framework's own reconciliation (React's component tree is this Composite, so mapping your document tree onto components lets React handle incremental re-render).

(5) Serialization is the save format and the API contract — so it must be versioned (a document saved today must load after the component set evolves), which means serialize/deserialize need a schema version and a migration path, and the discriminated-union spelling (section 5.2) is attractive here because it makes the persisted shape explicit and the load-time switch compiler-checked for exhaustiveness.

The design in a few sentences: The page is a Composite. Leaves and containers sit behind one Component interface, and container-only operations are kept off leaves so the types stay safe. The recursion is the easy part. The hard parts are two. First, the rules the tree must always obey: every node has a stable id, every node knows its parent, and moving a node can never create a loop. Second, the lifecycle: the tree is never changed in place, and new versions share their unchanged parts with old ones, which is what makes undo, caching and live collaboration manageable. In an interactive editor, the tree is edited far more often than it is simply read.

Flashcards

FlashComposite in one line

Part-whole tree where leaf and container share one Component interface; containers implement each operation by delegating to children. Recursion lives in the objects.

FlashThe key line

Children are typed as the Component interface, not the leaf type — so a container's children can be leaves or containers interchangeably, and operations never ask which.

FlashAdding an operation

One method per node class: leaf answers directly, composite delegates-and-combines. Zero client changes, zero instanceof. Operations and structure vary independently.

FlashTransparency vs safety

add/remove on Component = uniform but leaves fake them (LSP violation). On Composite only = type-safe, some downcasting. Typed languages lean safe.

FlashComposite hazards

Deep tree → stack overflow (iterate). Cycles → infinite loop (it's a tree; reject ancestor-adds). Expensive aggregates → cache + invalidate. Not a tree → don't use it.

FlashComposite vs Decorator

Decorator = one-child wrapper adding behavior. Composite = many-child tree representing a hierarchy, operated on uniformly. Both are recursive same-interface structures.

Scenario Drill

DrillDesign a permissions/access-control model for an organization where permissions are granted to a hierarchy: an org contains departments contain teams contain users, permissions can be granted at any level and inherit downward, and you must answer 'can user U perform action A on resource R?' efficiently for millions of checks per second. Use Composite, and be honest about where it stops being enough.

The organizational hierarchy is a Composite — org contains departments contain teams contain users, self-similar containment — and permission inheritance is a natural Composite operation that flows down the tree, so the model starts here cleanly and then hits scale limits worth being honest about. The Composite model. A PrincipalNode interface implemented by containers (Org, Department, Team) and the leaf (User); each node holds granted permissions and, for containers, child principals. The core operation is effectivePermissions(): PermissionSet, computed as this node's grants merged with the inherited set passed down from the parent — exactly the styles-inheritance pattern from the page-builder drill: a container computes its effective set from what it inherited plus its own grants, then passes the merged set to each child.

So user.effectivePermissions() naturally accumulates grants from the org, its department, its team, and itself, without the client knowing the hierarchy's shape — the Composite payoff. can(user, action, resource) then checks membership of (action, resource) in the user's effective set. Why Composite is right for the model: grants live at the natural level (a department-wide grant is one grant on the department node, not copied to every user), inheritance is a single recursive operation, and adding a new principal level (say, a "division" between org and department) is a new container class with no change to the permission logic.

Where it stops being enough — the honest part, which is the whole reason this is a staff question. (1) Working out effectivePermissions() by walking the tree on every check is far too slow for millions of checks a second. Each walk means one database read per level of the tree, which is a disaster at that rate. So the model stays a Composite, but the running system must not walk it on every check. Instead, work out each user's complete, flattened set of permissions ahead of time, and store it in a fast store such as Redis, keyed by user. Recompute it when grants change, not when someone reads it. This is the cached-total idea from section 7, taken all the way, because reads outnumber writes by many thousands of times. This is the key architectural move:

Keep the Composite tree for editing grants and working out inheritance. Keep a flattened, precomputed copy for the hot path, where every request is checked. (2) Now the hard problem is keeping that copy fresh. Suppose someone adds a grant at the organisation level. Every user beneath it now has an out-of-date cached set, and that can be millions of users. So each grant change sends update events down the subtree, in the background, and each cached set is cleared or recomputed. You accept that a permission change takes a few seconds to reach everyone. That is usually fine. When it is not, that one sensitive action checks the source of truth directly.

(3) Resource-scoped and conditional permissions exceed pure Composite — "can edit documents in this department" or "can approve expenses under $10k" are not simple inherited grants; they are policies with conditions, which is where you move from Composite to a policy engine (ABAC/RBAC hybrid, or a rules evaluation — [8.4]-territory in this book's plan). Composite models the principal hierarchy and grant inheritance; it does not model conditional policy, and pretending it does leads to cramming condition logic into node classes.

(4) Deny rules and precedence — real systems have explicit denies that must override inherited allows, so the merge operation is not a simple union but a precedence-ordered combination (deny-overrides, or most-specific-wins), which the Composite's effectivePermissions merge must encode carefully — and this is exactly the kind of subtle rule that belongs tested exhaustively.

The honest statement of where the pattern stops: The org hierarchy, with grants flowing down it, is a clean Composite. There is one interface, inheritance is a recursive merge, and each grant sits at its natural level. But the pattern models structure and inheritance. It does not solve scale, and it does not handle rules with conditions. At millions of checks per second, people still edit the tree, but requests are answered from a flattened cache that is refreshed in the background. Rules that depend on conditions, or on one specific resource, move to a policy engine. The Composite feeds that engine. It does not get replaced by it. The senior signal here is seeing that Composite is the right way to model the domain but the wrong thing to run on the hot path, and saying exactly where one hands over to the other.