Recursive Types & Tree Structures

Advanced TypeScript — 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.