This website uses cookies

Read our Privacy policy and Terms of use for more information.

Every Composite tutorial ends at the same moment of triumph. You call root.size() on a folder, it recursively sums every file underneath, and the caller never had to ask whether it was holding a file or a folder. Same method, same result type, any depth. Pattern understood, tutorial over.

Then you ship it. Someone moves a node from one branch to another and the totals double-count it. Someone adds a folder into its own subfolder and the next size() call never returns. A customer imports a 5,000-level-deep tree and your recursive method dies with a stack overflow. Someone caches the totals because the tree got big, and three weeks later the dashboard shows a number that was true last Tuesday.

None of these are exotic. They are the default failure modes of any tree you build by hand, and the classic pattern description says nothing about any of them. My claim in this issue: the uniform interface is the easy 20 percent of Composite. The other 80 percent is four invariants, and the production systems that use Composite well (the browser DOM, AWS CDK's construct tree) spend most of their code enforcing exactly those four.

The pattern in one paragraph

The Gang of Four's intent for Composite is to compose objects into tree structures that represent part-whole hierarchies, so clients can treat individual objects and compositions uniformly. Refactoring Guru's write-up gives the standard shape: a Component interface, Leaf classes that do real work, and a Composite class that holds children and delegates to them. The payoff is that client code stops branching on type. A price calculator does not care whether it holds a product or a box of boxes of products; it calls price().

You already use this pattern every day. A DOM Element is a node that contains nodes. A React component returns elements that contain components. A filesystem directory is a file that lists files. An AWS CDK Stack is a construct that contains constructs, and the constructs library's Node class exposes children, scopes, path and findAll() on every one of them. Abstract syntax trees, UI layout systems, org charts, permission groups, bill-of-materials systems: all Composite.

Here is a minimal version in Python that we will harden as we go.

class Node(ABC):
    def __init__(self, name):
        self.name = name
        self.parent = None

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

class File(Node):
    def __init__(self, name, bytes_):
        super().__init__(name)
        self.bytes = bytes_
    def size(self):
        return self.bytes

class Group(Node):
    def __init__(self, name):
        super().__init__(name)
        self.children = []
    def size(self):
        return sum(c.size() for c in self.children)

That is the whole textbook pattern. Now the four rules.

Rule 1: a node has exactly one parent

The naive add() is self.children.append(child). That is a bug the moment a node can be added twice. Add README.md under docs, then later add the same object under src, and it now lives in two places. root.size() counts it twice. Rename it in one place and it renames in both, because it is the same object. Your tree has silently become a graph.

The DOM made a decision here that is worth copying. Per MDN's appendChild reference, a node cannot be in two places at once: if the node you append already has a parent, it is removed from that parent first and then inserted. Append is move. If you want two copies, you call cloneNode() explicitly. The API makes the safe thing the default and the expensive thing visible.

AWS CDK takes the stricter route. A construct receives its scope in the constructor, new Bucket(this, 'Logs'), and that scope is fixed for life. There is no API to reparent a construct after creation, and ids must be unique within a scope. You cannot accidentally put one construct in two stacks because the constructor signature never lets you express it.

Both are fine. What is not fine is the third option most hand-rolled composites pick by accident: no policy at all. Pick move semantics or immutable parentage, and write it into add():

def add(self, child):
    if child.parent is not None:          # move, like the DOM
        child.parent.children.remove(child)
    child.parent = self
    self.children.append(child)
    return child

Note the parent pointer. The textbook Composite often omits it, because the downward recursion does not need it. Every real system has it anyway, because you need it to compute paths, to enforce single-parent, to propagate invalidation (Rule 4), and to answer the question users actually ask, which is "where is this thing?" CDK's node.path is exactly that walk up the parents, joined with /.

Rule 2: no cycles

Single-parent stops a node from appearing twice. It does not stop a node from becoming its own ancestor. src.add(root) with the code above happily reparents the root under one of its own children. Now root.size() recurses forever, or more precisely until Python raises RecursionError and someone gets paged.

The DOM rejects this at insertion time. The DOM Standard's pre-insertion validity check throws a HierarchyRequestError if the node being inserted is an inclusive ancestor of the parent. Every browser runs that ancestor walk on every appendChild. It costs O(depth), and depth in a real document is small, so nobody notices the price.

You should do the same, and you should do it in add(), not in the traversal. Detecting cycles during traversal means every read path carries a visited set forever. Rejecting them at write time means reads can assume a tree.

def add(self, child):
    n = self
    while n is not None:
        if n is child:
            raise ValueError(f"cycle: {child.name} is an ancestor of {self.name}")
        n = n.parent
    if child.parent is not None:
        child.parent.children.remove(child)
    child.parent = self
    self.children.append(child)
    return child

I ran this against a small tree: src.add(root) now fails with rejected: cycle: root is an ancestor of src, and moving README.md from docs to src leaves root.size() at 2000 bytes instead of double-counting to 2500. Two invariants, eight lines.

If your nodes come from outside (a JSON payload, a database table with parent_id), the same rule applies at the boundary. Validate the whole structure once when you load it, and refuse it if it has a cycle or a node with two parents. A self-referencing parent_id row is the most common way a production tree turns into an infinite loop, and it is the one place you are not calling your own add().

Rule 3: own the traversal

The elegant recursive size() has a ceiling. Python's default recursion limit is about 1,000 frames. I built a chain 5,000 groups deep with one file at the bottom, and the recursive size() died with RecursionError. Nobody designs a 5,000-level tree on purpose, but they get imported: deeply nested JSON from a partner, a generated AST from a minified file, a comment thread where every reply is a child of the previous one. Your recursion depth is now an input someone else controls.

The fix is an explicit stack. The same 5,000-deep tree walks fine iteratively:

def walk(self):
    stack = [self]
    while stack:
        n = stack.pop()
        yield n
        if isinstance(n, Group):
            stack.extend(reversed(n.children))

That walk() visited all 5,001 nodes, in pre-order, without touching the call stack. The reversed() is not decoration: without it you visit children right to left, and any output that depends on order (rendered HTML, generated config, a diff) changes for no visible reason.

Order matters more than people expect. CDK's findAll() takes a ConstructOrder argument, pre-order or post-order, because synthesis needs a defined order to produce the same CloudFormation template from the same code every time. A deterministic traversal is what makes the output diffable, and a diffable output is what lets a reviewer trust the change.

Owning the traversal also gives you a seam for the operations that do not belong on the node. The textbook pushes every operation into the Component interface: size(), render(), validate(), export(). After a year the base class has fifteen methods and every new leaf type must implement all of them. A single walk() generator plus free functions (total = sum(n.bytes for n in root.walk() if isinstance(n, File))) keeps the node interface small. When the number of operations keeps growing and the number of node types is stable, that is the point where Visitor starts to earn its place, which is exactly how Python's own ast.NodeVisitor is built.

Rule 4: decide what happens to aggregates

Recomputing size() from scratch on every call is O(n). For a 50-node menu that is nothing. For a 2 million node file index, or a UI tree that asks for its bounding box every frame, it is the profiler's top line. So someone adds a cache. And caching an aggregate in a tree is a cache invalidation problem with a very specific shape: when a leaf changes, every ancestor's cached value is wrong, and nothing below them is.

That shape tells you the fix. Invalidate up the parent chain:

def invalidate(self):
    n = self
    while n is not None and n._size is not None:
        n._size = None
        n = n.parent

def size(self):
    if self._size is None:
        self._size = sum(c.size() for c in self.children)
    return self._size

The early stop in invalidate() is safe because of an invariant worth naming: a parent's cache is only ever filled by calling size() on its children, so a valid parent implies valid children. If you reach a node that is already invalid, everything above it was invalidated by whoever invalidated it. Every mutation (add, remove, a leaf's resize) must call invalidate() on the parent. In my test, a tree reported 15, a leaf was resized from 10 to 100, and the root correctly reported 105.

This is the same "dirty flag" scheme browsers use for layout: a style change marks the element and its ancestors dirty, and the next layout pass only recomputes the dirty path. It is also the reason Rule 1 matters so much. Invalidation walks the parent pointer. A node with two parents can only invalidate one of them, and the other one serves stale data forever.

Yes, but: isn't this just a tree data structure?

The strongest objection is that none of this is about the pattern. Single parent, no cycles, iterative traversal and cache invalidation are properties of trees. Any CS course covers them. Composite is about the uniform interface, and I am smuggling a data structures lecture into a design patterns series.

Half right. The invariants are tree invariants. But the pattern is precisely what makes them easy to forget, because its selling point is that clients stop thinking about structure. When a caller holds a Component and calls size(), they are not supposed to know whether it is a leaf, a subtree, or a 5,000-deep chain. That uniformity moves the responsibility for structural safety from the caller to the composite itself. If the composite does not enforce the four rules, nobody does, because the pattern has explicitly told everyone else not to look.

There is also a real design tension the GoF book names directly: transparency versus safety. Put add() and remove() on the shared Component interface and clients really can treat everything uniformly, but now File.add() exists and has to throw. Put them only on Composite and the compiler stops you from adding children to a leaf, but clients have to downcast to build the tree. The DOM chose transparency (appendChild exists on Node, and a Text node rejects children at runtime). CDK effectively chose safety, since children are attached through the constructor and there is no add method to misuse. For new code I lean toward safety. Reads are uniform, writes are typed, and the class of bug where someone calls add() on a leaf disappears at compile time.

Monday morning

Open the tree in your codebase. There is one: a category hierarchy, a permissions model, a menu, a config loader, a comment thread. Then ask four questions. What happens if I add the same node twice? What happens if I add an ancestor under its descendant? What is the deepest input I accept, and does my traversal recurse? If I cache a total, which mutations invalidate it and how far up?

If any answer is "I'm not sure," write the test before you write the fix. Each of these is a ten-line test, and each one is a production incident you get to skip. The uniform interface got you the clean call site. The four rules are what make that call site safe to trust.

Sources