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 (leaves must implement add(child)/remove(child) that make no sense for them — the pattern's central design tension, section 6) or too narrow (clients must downcast to reach container-only operations, partly defeating uniformity); deep trees risk stack overflow on naive recursion; and it can be over-applied to data that is not actually 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." The abstract tell: "an X can contain Xs" (self-similar containment) plus "I want to run an operation over the whole tree uniformly." If containment is not recursive (a container holds only leaves, never other containers), you may not need Composite — a list suffices.

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 (the shared interface for leaves and containers, declaring the operations), Leaf (a node with no children; implements operations directly), Composite (a node holding child Components; implements operations by delegating to children and combining results, and manages the child list), Client (operates on the tree through Component, uniformly).

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: a shared Component interface implemented by both Leaf and Composite; the leaf implements each operation directly (base case), and the composite implements it by delegating the same operation to its children — typed as Component, so it never asks whether each child is a leaf or a container — and combining the results (recursive case).

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, because a compile error is strictly better than a runtime throw, and the uniformity that matters — the operations clients actually run across the whole tree (size, render, find) — stays on Component and remains fully uniform; only the tree-construction operations, which clients use far less and usually in code that already knows it has a container, move to Composite.

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 — if a container holds only leaves and never other containers (a playlist of songs, a shopping cart of line items), the self-similar containment that motivates Composite is absent, and a plain list with a loop is simpler and clearer; forcing a Component interface here is 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 Composite in its natural habitat — a page is a tree of components where containers hold components (including other containers) arbitrarily deep — so the model is a Component interface implemented by leaves (Text, Image) and composites (Container, Column, Form), with the tree operations living on the nodes. The interface, cut for safety (section 6): universal operations every node answers go on Component — render(), serialize(), validate(), computeStyles(inherited), findById(id); container-only operations — add, remove, insertAt, moveChild — go on the Container composite type, so text.add(child) does not compile. computeStyles is worth noting as a genuinely recursive operation with inheritance: a container computes its own styles from inherited context, then passes the merged context down to each child's computeStyles — the classic Composite delegation carrying accumulated state downward, exactly like CSS cascade (which is itself a Composite operation over the DOM).

Each operation is the standard template: serialize() — a leaf emits its own JSON, a container emits its type plus its children's serialization (so the whole page serializes by calling root.serialize()); validate() — a leaf checks its own constraints, a container validates itself then aggregates children's errors (so a form's "at least one submit button" rule and a text node's "non-empty" rule compose into one error list); findById — the recursive search of section 5.1, essential because the editor constantly needs "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.

Testing: the uniformity test (a mixed list of leaves and containers all serialize/validate), deep-nesting tests, the cycle-rejection test on reparent (the invariant that prevents editor hangs), and an undo/redo round-trip. The design sentence: the page is a Composite — leaf and container behind one Component interface with container-only ops kept off leaves for type safety — and the hard parts are not the recursion but the tree invariants (stable ids, parent pointers, no-cycle reparenting) and the lifecycle (immutable structural-sharing tree so undo, caching, and collaboration are tractable), because in an interactive editor the tree is edited far more than it is merely traversed.

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) Computing effectivePermissions() by walking the tree on every check is far too slow for millions of checks per second — a per-check tree traversal is O(depth) database reads, catastrophic at that rate. So the model is a Composite but the runtime must not traverse it per check: precompute and cache each user's flattened effective permission set (the Composite computed once and materialized), stored in a fast store (Redis) keyed by user, and recomputed on grant changes rather than on reads — the cached-aggregate variant of section 7 taken to its logical end, because reads dominate writes by many orders of magnitude. This is the key architectural move:

Composite for authoring and inheritance semantics, a flattened materialized view for the hot path. (2) Invalidation is now the hard problem — a grant added at the org level must invalidate the cached sets of every user beneath it, potentially millions; so grant-change events fan out invalidations (or recomputations) down the subtree asynchronously, and you accept brief eventual consistency on permission changes (usually fine — a permission taking seconds to propagate is acceptable; if not, that specific action re-checks against the source of truth).

(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 boundary statement: the org hierarchy and downward grant inheritance are a clean Composite — one interface, inheritance as a recursive merge, grants at their natural level — but the pattern models structure and inheritance, not scale or conditional policy; at millions of checks per second the tree is authored as a Composite and served as a flattened cache with asynchronous invalidation, and conditional/resource-scoped rules graduate to a policy engine the Composite feeds rather than replaces. Recognizing that Composite is the right domain model but the wrong hot-path runtime — and saying exactly where the handoff is — is the senior signal here.