What invariants must a Composite container enforce when children are added, removed, or moved — and what breaks if it maintains parent references or shares nodes between containers?
answer
- cycle guard: not self, not an ancestor (walk up via parent — O(depth))
- add detaches from old parent; remove clears parent
- expose children read-only, never the live list
- membership + depth rules become runtime checks
- shared node = DAG: parent ambiguous, sums double-count, need visited set
basics
~20 sadd() must reject cycles (a node must not contain itself or an ancestor), keep parent references consistent by detaching the child from its old parent, and enforce any rules about which children are allowed. Sharing one node under two parents breaks parent pointers and double-counts totals.
solid answer
~60 sFour invariants. **Acyclicity**: a node must never become its own ancestor, or every traversal loops forever; `add` should verify the candidate child is neither this node nor an ancestor of it. **Parent consistency**: if nodes carry a parent reference — needed for event bubbling, path computation, or invalidating cached aggregates upward — then `add` must detach the child from its previous parent and `remove` must clear it, otherwise a node appears in two child lists or points at a parent that no longer holds it. **Domain constraints**: rules like "only cells inside a row" cannot be expressed in a uniform interface, so they become runtime checks inside `add`. **Cache validity**: any structural change must invalidate cached aggregates along the whole ancestor chain, not just locally. Deliberately allowing a node under multiple parents turns the tree into a DAG: a single parent pointer becomes meaningless, summing aggregates double-count shared subtrees, and traversals need a visited set. That can be a valid memory optimisation for immutable, stateless leaves, but the semantics must be chosen consciously.
code
pseudocode · 20 linesclass Container implements Node {
private children: List<Node>
parent: Container?
add(child: Node) {
// 1. acyclicity — walk UP from self, O(depth), needs parent links
var p = this
while (p != null) { require(p !== child); p = p.parent }
// 2. domain + depth rules
require(accepts(child) && this.depth + 1 <= MAX_DEPTH)
// 3. detach from previous parent
child.parent?.children.remove(child)
children.add(child)
child.parent = this
// 4. invalidate cached aggregates up the chain
invalidateUpward()
}
childrenView(): ReadOnlyList<Node> = children.readOnly() // never the live list
}go deeper
Mention that add must not let a container contain itself, and that removing a child should also clear any parent reference.
Give the full invariant set — acyclicity, parent consistency with detach-from-old-parent, membership rules as runtime checks, and read-only exposure of the child list.
Add cached-aggregate invalidation up the parent chain, the O(depth) upward cycle check enabled by parent pointers, and the concurrency hazards of path-wise locking.
Discuss tree versus DAG as a deliberate modelling decision with explicit aggregate semantics, argue immutability with structural sharing as the design that eliminates most of these invariants, and treat depth limits as a boundary control against untrusted input.
## Why child management is where Composite actually breaks The recursion in Composite is simple; the mutation is not. Every guarantee traversal relies on is established by `add`, `remove`, and `move`. If those are sloppy, the elegant recursive operations hang, double-count, or return stale numbers. ## Invariant 1 — acyclicity Composite assumes a **tree**: one root, every node reachable by exactly one path, no node is its own ancestor. Nothing in the code enforces this by default — `directory.add(directory)` type-checks perfectly, and afterwards `size()` recurses forever. The check on `add(child)`: 1. `child !== this` — the trivial self-containment case. 2. `this` is not reachable from `child` — i.e. the node you are inserting must not already contain the container. Two ways to test: walk down from `child` looking for `this` (O(subtree)), or, if parent pointers exist, walk **up** from `this` looking for `child` (O(depth), much cheaper — a good answer to give). On a move operation both directions matter: moving an ancestor into its own descendant is the classic "drag a folder into itself" bug that file managers must reject. ## Invariant 2 — parent-reference consistency Parent pointers are optional but frequently needed: computing a node's full path, bubbling an event from a clicked widget up to a handler, invalidating cached aggregates upward, or answering "which container am I in?". Once they exist, the two-sided relationship must be maintained atomically: ``` add(child): guardAcyclic(child) if child.parent != null: child.parent.children.remove(child) # detach first children.add(child) child.parent = this remove(child): if children.remove(child): child.parent = null ``` Skip the detach and the node sits in two child lists while claiming one parent — traversals from the old root still visit it, counts are wrong, and deleting the old parent may or may not take it along. This is the same bidirectional-association hazard as in ORM entity mapping, and the same remedy applies: make one side own the relationship and route all mutation through it, rather than exposing the child list for direct manipulation. Which implies: **do not return the live children collection from a getter.** Hand back an immutable/defensive copy or an iterator, so nobody can bypass the invariants by mutating the list directly. ## Invariant 3 — domain constraints on membership The uniform interface deliberately erases type distinctions, so rules like "a table row contains only cells", "a playlist contains only tracks and folders, not albums", or "maximum nesting depth 20" cannot be enforced by the compiler. They must live as runtime validation inside `add`, with a clearly documented failure mode (exception versus rejection result). This is a real cost of Composite that candidates should acknowledge rather than gloss over — the pattern trades static guarantees for uniformity. Depth is worth enforcing here specifically: maintaining a `depth` field incrementally makes the limit an O(1) check on insert, which protects downstream recursive traversals from stack overflow when the tree is built from untrusted input. ## Invariant 4 — cached-aggregate validity Containers commonly memoise expensive aggregates (`cachedSize`, `cachedBoundingBox`, `cachedValidity`). The invalidation rule is unforgiving: **a change to any descendant invalidates every ancestor.** So mutation must walk the parent chain marking caches dirty (or eagerly recomputing). That requires parent pointers, and under concurrent mutation it requires synchronisation over a path — with real deadlock risk if two threads lock paths in different orders. This is a strong argument for **immutable nodes**: children are fixed at construction, so an aggregate computed once is valid forever. Edits create new nodes along the path from the changed node to the root and share every untouched subtree (structural sharing), giving lock-free readers and free undo history at the cost of some allocation. ## Sharing a node between containers — tree becomes DAG Suppose you deliberately insert the same node object into two containers. The structure is now a **directed acyclic graph**, and several assumptions silently break: - **Parent pointer is ill-defined.** "Which container am I in?" has more than one answer, so path computation and event bubbling become ambiguous. - **Aggregates double-count.** A sum over the graph counts the shared subtree once per incoming edge. Sometimes that is desired (the same component used twice in a bill of materials genuinely costs twice); often it is not (unique file count). - **Traversals may need a visited set** if each node must be processed once; without it, work is exponential in pathological graphs. - **Mutating a shared node affects every parent at once** — surprising unless the node is immutable. - **Removal semantics get fuzzy**: removing from one parent should not destroy the node, so lifetime moves to reference counting or garbage collection. When is sharing a good idea? When leaves are **immutable and stateless**, as in a Flyweight-style scene graph, a rendering tree reusing the same mesh, or an expression DAG where identical subexpressions are interned for caching. Then the memory saving is large and the hazards mostly evaporate — but aggregates must still be defined explicitly as "per occurrence" or "per distinct node". ## A checklist for reviewing a Composite's mutation API 1. Does `add` reject self-containment and ancestor insertion (checking upward via parent if available)? 2. Does `add` detach the child from its previous parent, and `remove` clear the parent field? 3. Is the children collection exposed only as read-only, so invariants cannot be bypassed? 4. Are domain membership rules and a depth limit validated on insert, with a documented failure mode? 5. Do mutations invalidate cached aggregates up the entire ancestor chain? 6. Is concurrent mutation prevented, or is the tree immutable so the question does not arise? 7. If nodes may be shared, is the structure documented as a DAG with explicit aggregate semantics and visited-set traversal?
- What is the cheapest correct way to detect that an add would create a cycle?If nodes have parent references, walk upward from the container checking that no ancestor is the candidate child — O(depth). Without parent references you must search the child's subtree for the container, which is O(subtree size).
- Why should a Composite not expose its live children collection through a getter?Because callers could then add or remove directly, bypassing the cycle guard, parent-pointer maintenance, membership rules, and cache invalidation. Return an immutable view, a defensive copy, or an iterator instead.
- You allow the same node under two containers. Which aggregate operations must be redefined?Any operation that counts or sums, since a shared subtree is reached through multiple paths and would be counted once per path. You must decide explicitly between per-occurrence semantics (bill of materials, where duplication is real) and per-distinct-node semantics (unique file count), and implement the latter with a visited set.
- How do immutable Composite nodes change this invariant list?Cycles become impossible to create after construction, parent-pointer desynchronisation cannot occur (parent links are usually dropped or supplied by the traversal), cached aggregates never go stale, and concurrent readers need no locks. The remaining costs are allocation per edit and rebuilding the path to the root.
saying these in an interview costs you the question
- Implementing add() as a bare list append with no cycle guard — the resulting infinite traversal is often blamed on the algorithm rather than the insert.
- Keeping parent references but forgetting to detach the child from its previous parent, leaving a node in two child lists.
- Returning the live mutable children list from a getter, letting callers bypass every invariant.
- Assuming node sharing is harmless; it converts the tree to a DAG and silently double-counts aggregates.
- Caching a container's aggregate without invalidating the whole ancestor chain on descendant changes.
- Believing membership rules like "only cells inside a row" can still be enforced by the type system once the uniform interface exists.