Recursive Types & Tree Structures

Advanced TypeScript

Course 4 · Chapter 2 · Recursive Types & Tree Structures

🌳 Recursive Types & Tree Structures

Chapter 1's DeepAwaited recursed on a conditional type to peel off one wrapper at a time. This chapter recurses on data shapes instead — types that reference themselves to describe trees, graphs, and arbitrarily nested JSON — plus the depth-limiting trick that keeps the compiler from giving up on a genuinely infinite structure.

The Classic Example: JSON Value

JSON is recursive by definition — a value can contain values, which can contain more values. TypeScript can model that exactly:

type JsonValue =
  | string
  | number
  | boolean
  | null
  | JsonValue[]
  | { [key: string]: JsonValue };

const config: JsonValue = {
  name: "widget",
  tags: ["a", "b"],
  nested: { deep: { deeper: [1, 2, { ok: true }] } },
};  // ✅ valid — arbitrarily nested, still fully typed

// const bad: JsonValue = { fn: () => {} }; // ❌ a function isn't a valid JsonValue

JsonValue refers to itself twice in its own definition — in the array branch and the object branch — and TypeScript resolves that self-reference without any special syntax.

🌲 Generic Tree Structures

A generic tree node follows the same self-referencing pattern, parameterized over the data each node carries:

interface TreeNode<T> {
  value: T;
  children: TreeNode<T>[];
}

const tree: TreeNode<string> = {
  value: "root",
  children: [
    { value: "child-a", children: [] },
    { value: "child-b", children: [
      { value: "grandchild", children: [] },
    ] },
  ],
};

Interfaces Recurse Naturally

An interface can reference itself directly by name — no special "recursive type" syntax is needed.

Type Aliases Recurse Too

JsonValue above is a type, not an interface — both forms support self-reference identically.

Recursive Mapped Types: `DeepReadonly<T>`

Course 2's mapped types (Partial<T>, Readonly<T>) only go one level deep. Making them recurse into nested objects combines a mapped type with a conditional type check:

A Genuinely Deep Readonly

type DeepReadonly<T> = T extends object
  ? { readonly [K in keyof T]: DeepReadonly<T[K]> }
  : T;

interface Config {
  apiUrl: string;
  limits: { maxRetries: number; timeoutMs: number };
}

type ReadonlyConfig = DeepReadonly<Config>;
// { readonly apiUrl: string; readonly limits: { readonly maxRetries: number; readonly timeoutMs: number } }

const config: ReadonlyConfig = { apiUrl: "x", limits: { maxRetries: 3, timeoutMs: 5000 } };
// config.limits.maxRetries = 5; // ❌ Course 2's Readonly<T> would have MISSED this nested field

Every branch of the mapped type recurses into DeepReadonly<T[K]> — if T[K] is itself an object, the recursion applies readonly there too; if it's a primitive, the T extends object check fails and the base case returns it unchanged.

🛑 Depth-Aware Types: Stopping Infinite Recursion

Some recursive types genuinely never terminate — TypeScript enforces a recursion depth limit and errors with "Type instantiation is excessively deep and possibly infinite" rather than hanging forever:

Unbounded vs Depth-Limited Recursion

Unbounded (risks the depth error)

type Repeat<T> = [T, ...Repeat<T>];
// ❌ Type instantiation is excessively deep and possibly infinite —
// there's no base case, so the compiler can never stop.

Depth-Limited (a counting tuple)

type Repeat<T, N extends number, Acc extends unknown[] = []> =
  Acc["length"] extends N ? Acc : Repeat<T, N, [...Acc, T]>;

type ThreeStrings = Repeat<string, 3>;  // [string, string, string]

Tuple-as-Counter

Acc["length"] reads a tuple's length as a numeric literal type — appending one element per recursive call increments it, giving recursion a way to "count."

Explicit Base Case

Acc["length"] extends N is the stopping condition — without it, the same "excessively deep" error from the unbounded version would return.

💻 Coding Challenges

Challenge 1: Write a Recursive `Flatten` Type

Write a type FlattenArray<T> that, given a deeply nested array type like number[][][], produces the fully flattened element type (number), recursing until it finds a non-array.

Goal: Practice a recursive conditional type over a self-referencing structure (nested arrays).

→ Solution

Challenge 2: Write `DeepPartial<T>`

Following the DeepReadonly<T> pattern from this chapter, write DeepPartial<T> that makes every property optional at every level of nesting, not just the top level.

Goal: Practice combining a recursive mapped type with the optional modifier instead of readonly.

→ Solution

Challenge 3: Count Tree Depth

Using the TreeNode<T> type from this chapter and the counting-tuple trick, write a type TreeDepth<T> that computes how many levels deep a specific tree value (not just the type) is nested — or, as a simpler variant, write a depth-limited Repeat<T, N> for a value of your choosing.

Goal: Practice using a tuple accumulator to give a recursive type a numeric stopping point.

→ Solution

⚠️ Gotcha: "Excessively Deep and Possibly Infinite"

This error isn't always about a truly infinite type — it also fires on recursive types applied to very large but finite inputs, because TypeScript caps recursion depth for performance reasons. If you hit it on a type that should terminate, check for a missing or unreachable base case first; if the type is fundamentally correct but just deep, a depth-limiting accumulator (like the counting tuple above) is the standard escape hatch.

🎯 What's Next

Trees recurse through nested objects — the next chapter recurses through nested function signatures instead: Tuple & Variadic Generics, spreading types in and out of tuples to build things like type-safe curry and compose functions.

Recursive Types & Tree Structures