Description

Login

Syncing account progress…

Back

Advanced · 18 min

Recursive data with runtime limits

Traverse a recursive union while bounding recursion depth.

Model nested groups

A recursive type can refer to itself through child nodes. Narrow the discriminant before reading leaf data or children. Types do not guarantee that runtime data is acyclic. This traversal throws when depth exceeds 20; it is an explicit application limit.

type Tree = { kind: "leaf"; minutes: number } | { kind: "group"; children: readonly Tree[] };
function total(tree: Tree, depth = 0): number {
  if (depth > 20) throw new Error("Too deep");
  if (tree.kind === "leaf") return tree.minutes;
  return tree.children.reduce((sum, child) => sum + total(child, depth + 1), 0);
}
const tree: Tree = { kind: "group", children: [{ kind: "leaf", minutes: 10 }, { kind: "group", children: [{ kind: "leaf", minutes: 5 }] }] };
const minutes = total(tree);
console.log(minutes);

Output

15

Handle empty and excessive input

An empty group contributes zero because reduce has an initial value. Catch variables are unknown and need narrowing. A depth limit bounds stack depth, not the total amount of work in a wide tree; external data also needs validation and size limits.

type Tree = { kind: "leaf"; minutes: number } | { kind: "group"; children: readonly Tree[] };
function total(tree: Tree, depth = 0): number {
  if (depth > 20) throw new Error("Too deep");
  if (tree.kind === "leaf") return tree.minutes;
  return tree.children.reduce((sum, child) => sum + total(child, depth + 1), 0);
}
console.log(total({ kind: "group", children: [] }));
try { total({ kind: "leaf", minutes: 1 }, 21); }
catch (error: unknown) { console.log(error instanceof Error ? error.message : "Failed"); }

Output

0
Too deep

Put it into practice

  1. Predict the output and explain which relationships the types enforce.
  2. Fix the task while preserving its type contract, then check both practice questions.

Try it yourself

Code runs on this device. When you are signed in, drafts sync to your account.

Narrow a recursive node

Restore the leaf check before returning minutes. Keep recursion and the depth limit.

Show solution
type Tree = { kind: "leaf"; minutes: number } | { kind: "group"; children: readonly Tree[] };
function total(tree: Tree, depth = 0): number {
  if (depth > 20) throw new Error("Too deep");
  if (tree.kind === "leaf") return tree.minutes;
  return tree.children.reduce((sum, child) => sum + total(child, depth + 1), 0);
}
const tree: Tree = { kind: "group", children: [{ kind: "leaf", minutes: 10 }, { kind: "group", children: [{ kind: "leaf", minutes: 5 }] }] };
const minutes = total(tree);
console.log(minutes);

The corrected discriminant check narrows both paths. Leaves return their value, and groups traverse children with the existing depth guard.

Practice