Replace Implicit Tree With Composite

Triggered by

Destination

Symptom

Tree-shaped data is encoded as flat records with parentId pointers, prefix strings (`'products/category/electronics'`), or nested arrays without typed nodes. Every traversal re-derives the tree shape by filtering or string-parsing; bugs surface as 'this node should be a child of X but isn't'.

Goal

Each node is an object with explicit children. Traversals are method calls on the node; tree-shape invariants (cycles, orphans) are impossible by construction; the data structure expresses what it is.

Before the refactoring

// Tree shape encoded as flat records joined by parentId pointers.
const items = [
  { id: 1, label: 'File', parentId: null },
  { id: 2, label: 'Edit', parentId: null },
  { id: 3, label: 'New', parentId: 1 },
  { id: 4, label: 'Open', parentId: 1 },
  { id: 5, label: 'Recent', parentId: 4 },
  { id: 6, label: 'Cut', parentId: 2 },
];

function render(items) {
  const roots = items.filter((i) => i.parentId === null);
  return roots.map((root) => renderItem(root, items)).join('\n');
}
function renderItem(item, items, depth = 0) {
  const children = items.filter((i) => i.parentId === item.id);
  let line = '  '.repeat(depth) + item.label;
  for (const child of children) {
    line += '\n' + renderItem(child, items, depth + 1);
  }
  return line;
}

After the refactoring

// Explicit composite: each node holds its children directly.
class MenuItem {
  constructor(label) {
    this.label = label;
    this.children = [];
  }
  add(child) {
    this.children.push(child);
    return this;
  }
  render(depth = 0) {
    return (
      '  '.repeat(depth) +
      this.label +
      this.children.map((child) => '\n' + child.render(depth + 1)).join('')
    );
  }
}

const file = new MenuItem('File')
  .add(new MenuItem('New'))
  .add(new MenuItem('Open').add(new MenuItem('Recent')));
const edit = new MenuItem('Edit').add(new MenuItem('Cut'));
const menus = [file, edit];

menus.map((menu) => menu.render()).join('\n');

Example source: Illustrative example written for this site, faithful to Kerievsky's pattern shape in Refactoring to Patterns (Addison-Wesley, 2004), chapter 9. The book uses an XML-ish document tree encoded implicitly; this JavaScript version uses a menu hierarchy encoded as flat parentId-joined records — same shape, accessible domain.

Pressure

Implicit trees defeat type safety — the tree's shape is an emergent property of pointer wiring. Operations that should be O(node) become O(N) filters; relational join logic leaks into every traversal; bugs in one filter ship as silent data inconsistencies.

Tradeoff

Concrete tree objects must be constructed (often by reading the flat data once); persistence requires explicit serialization back to whatever store the implicit form lived in. Memory cost grows with tree size; the flat form may have been load-on-demand.

Relief

Traversals shrink to recursive method calls; tree invariants are enforceable at construction; type-checked access replaces filtered-list-of-records. Adding behaviour (e.g., 'render', 'count', 'find') is a method on the node, not a new traversal function.

Trap

Eager construction of large trees from large flat datasets explodes memory. The pattern pays when the tree is the working unit; for trees that exist primarily as serialized state in a database, lazy-loaded record-based traversal may stay cheaper despite the awkwardness.