Typing Recursive Data Structures in TypeScript: Linked Lists, Trees, and Graphs
Introduction
Recursive data structures are everywhere in software: linked lists, binary trees, abstract syntax trees, dependency graphs, DOM-like hierarchies, and more. Typing them in TypeScript is straightforward at first glance, but real-world requirements—nullable children, discriminated unions, readonly shapes, cycle-safe traversal, and generic payloads—quickly make the types complex. This guide teaches intermediate TypeScript developers how to design robust, maintainable types for recursive structures while keeping runtime ergonomics and performance in mind.
In this article you will learn to:
- Model recursive types using interfaces, type aliases, and generics.
- Use discriminated unions and literal inference to express node variants safely.
- Write safe traversal algorithms with typed iterators and generator functions.
- Create type guards and predicates to refine node types at runtime.
- Handle cycles and mutual recursion with safe traversal and visited sets.
- Combine runtime validation and static typing to guard external input.
We include extensive code examples: linked lists, n-ary trees, binary trees with parent pointers, and directed graphs. Each example shows types, constructors, traversal utilities, and common pitfalls with solutions. You'll also find tips to interoperate with JavaScript code, how to use readonly and exact object shapes, and how to write ergonomic APIs for consumers. Where relevant, links to deeper TypeScript topics are included so you can level up your typing patterns.
Background & Context
Recursive data structures are defined in terms of themselves: a tree node contains children that are trees. In TypeScript, that self-reference is expressed by naming a type and using it within its own definition. But simple recursion can hide complexity: optional fields, mutually recursive types, and shared references (cycles) complicate both static typing and runtime algorithms.
Typing recursive structures is important because it prevents common bugs (wrong payloads, null errors), improves DX with better autocomplete and refactorability, and clarifies invariants across teams. Additionally, when you combine static types with runtime validation and discriminated unions, you get safer systems that fail early and clearly. This guide focuses on pragmatic typing patterns you can apply today.
Key Takeaways
- Use named types and generics to model recursive shapes clearly.
- Prefer discriminated unions and literal inference for node variants.
- Use type predicates for safe runtime refinement; see our guide on using type predicates for custom type guards for patterns.
- Generator functions and iterators simplify traversal; review typing generator functions and iterators in TypeScript to learn advanced patterns.
- Combine compile-time typing with runtime schema checks for external data.
- Be explicit about mutability and exact properties to avoid accidental structural drift; see typing objects with exact properties in TypeScript for techniques.
Prerequisites & Setup
This guide assumes you are familiar with TypeScript basics: interfaces, type aliases, generics, union types, and basic mapped types. You should be comfortable reading and writing functions with generics and basic type guards. To follow along locally, have Node.js and a TypeScript toolchain installed (tsc or a bundler with ts support). Optionally, an editor like VS Code will show most of the benefits of types as you code.
If you use JavaScript and want to keep static checks, consider learning to annotate with JSDoc; our article on using JSDoc for type checking JavaScript files (@typedef, @type, etc.) covers that. Also, when designing constructors and APIs, you may want to accept optional config objects; see patterns at typing functions with optional object parameters in TypeScript — deep dive.
Main Tutorial Sections
1) Modeling a Simple Linked List
Start with a singly linked list of values. Use a generic to allow different payload types.
type ListNode<T> = {
value: T
next: ListNode<T> | null
}
function createNode<T>(value: T, next: ListNode<T> | null = null): ListNode<T> {
return { value, next }
}This model is simple and practical. Use null for the terminator—it's explicit and interoperable. For immutable lists, mark properties readonly:
type ImmutableListNode<T> = {
readonly value: T
readonly next: ImmutableListNode<T> | null
}This prevents accidental mutation and improves reasoning about references.
2) Traversal with Iterators and Generators
Iterating linked lists is common. Generators express iteration succinctly and integrate with for..of. Typing generator functions correctly improves DX; refer to our deep dive on typing generator functions and iterators in TypeScript.
function* iterateList<T>(head: ListNode<T> | null): Generator<T, void, unknown> {
let cur = head
while (cur) {
yield cur.value
cur = cur.next
}
}
// usage
for (const v of iterateList(head)) {
console.log(v)
}Generator types let callers know yield and return types. If you want a higher-level iterator object, implement Symbol.iterator.
3) Binary Trees and Discriminated Unions
Binary trees often have variants: internal nodes and leaves. Discriminated unions are great for this. Use a literal kind property and freeze values with 'as const' where appropriate to preserve literals; see using as const for literal type inference in TypeScript.
type Leaf<T> = { kind: 'leaf'; value: T }
type Branch<T> = { kind: 'branch'; left: Tree<T>; right: Tree<T> }
type Tree<T> = Leaf<T> | Branch<T>
function isLeaf<T>(node: Tree<T>): node is Leaf<T> {
return node.kind === 'leaf'
}This pattern ensures exhaustive checks in switch statements and safe refinements.
4) Generic Tree Builders and Exact Shapes
Builders help construct trees reliably. When building firm APIs, prefer exact property shapes and explicit constructors. The article on typing objects with exact properties in TypeScript offers utilities and patterns to prevent excess properties.
function leaf<T>(value: T): Leaf<T> {
return { kind: 'leaf', value }
}
function branch<T>(left: Tree<T>, right: Tree<T>): Branch<T> {
return { kind: 'branch', left, right }
}Use factories instead of object literals in public APIs to maintain invariants and allow internal refactors.
5) N-ary Trees and Recursive Generics
For trees with arbitrary numbers of children, model children as arrays of the same tree type. Beware of mixed-type arrays; see patterns for mixed arrays in our article on typing arrays of mixed types (union types revisited) for when children can be heterogeneous.
type NaryNode<T> = { value: T; children: NaryNode<T>[] }
function traverseNary<T>(root: NaryNode<T>, visit: (n: NaryNode<T>) => void) {
const stack: NaryNode<T>[] = [root]
while (stack.length) {
const cur = stack.pop()!
visit(cur)
for (let i = cur.children.length - 1; i >= 0; i--) stack.push(cur.children[i])
}
}This DFS implementation is iterative to avoid JS recursion limits with deep trees.
6) Graphs, Cycles, and Safe Traversal
Graphs introduce cycles. Traversal must track visited nodes to avoid infinite loops. Use a Set keyed by node identity or node id. For nodes that are plain objects, either assign unique ids or use WeakSet for identity checks.
type GraphNode<T> = { id: string; value: T; edges: GraphNode<T>[] }
function traverseGraph<T>(start: GraphNode<T>, visit: (n: GraphNode<T>) => void) {
const visited = new Set<string>()
const stack: GraphNode<T>[] = [start]
while (stack.length) {
const cur = stack.pop()!
if (visited.has(cur.id)) continue
visited.add(cur.id)
visit(cur)
for (const e of cur.edges) stack.push(e)
}
}Choosing string ids makes visited checks simple and serializable; WeakSet works when you can rely on object identity.
7) Type Guards and Predicates for Node Refinement
Runtime refinement of nodes is usually necessary when reading external data or when you need to branch on node variants. Type predicates are the idiomatic approach. See our deeper guide on using type predicates for custom type guards for patterns and pitfalls.
function isBranch<T>(node: Tree<T>): node is Branch<T> {
return (node as any).kind === 'branch'
}
// usage
function sumLeaves(node: Tree<number>): number {
if (isBranch(node)) return sumLeaves(node.left) + sumLeaves(node.right)
return node.value
}When data comes from JSON, validate shape first (see Advanced Techniques below) before trusting predicates.
8) Interop with JavaScript and JSDoc
If you maintain mixed JS/TS codebases, annotate recursive types with JSDoc to get editor checks without a full migration. Our article on using JSDoc for type checking JavaScript files (@typedef, @type, etc.) shows how to add typedefs and keep runtime shapes explicit.
/**
* @typedef {{ value: number, next: ListNode | null }} ListNode
*/
/** @type {ListNode} */
const n = { value: 1, next: null }This helps when consumed by TypeScript projects and avoids fragile any types at boundaries.
9) API Design: Optional Parameters and Variadic Constructors
APIs that construct trees often accept optional options. TypeScript patterns for optional object parameters help keep signatures clean. See patterns in typing functions with optional object parameters in TypeScript — deep dive. For constructors that accept variable numbers of children, use rest params; learn advanced patterns in typing functions with variable number of arguments (rest parameters revisited).
function makeBranch<T>(...children: Tree<T>[]): NaryNode<T> {
return { value: (children[0] && (children[0] as any).value) ?? null, children }
}Design your factories to be ergonomic while keeping type-safety for consumers.
10) Combining Runtime Validation and Typing
When loading tree-structured data from JSON or APIs, validate before you assert types. Libraries like zod, io-ts, or runtypes help, but sometimes small runtime checks suffice. Runtime validation plus static types prevents trusting malformed input.
function validateGraphNode(obj: unknown): obj is GraphNode<unknown> {
if (typeof obj !== 'object' || obj === null) return false
const o = obj as any
return typeof o.id === 'string' && Array.isArray(o.edges)
}For robust APIs, pair lightweight validators with type guards and include clear error messages on failure.
Advanced Techniques
Once basic types and traversals are in place, you can optimize for performance and ergonomics. Memoize expensive traversals with Maps keyed by node id. Use iterative traversals to avoid call-stack overflows with deep structures. For large immutable trees, consider structural sharing via persistent data structures or pointer-based trees, and leverage readonly types to enforce immutability in consumers.
Type-level tricks: conditional types, mapped types, and tail recursion elimination in your designs can encode invariants such as depth limits or balanced trees at compile time, though they add complexity. If you expose iterator-based APIs, type the iterator carefully so consumers get the correct yield types; see typing generator functions and iterators in TypeScript for guidance on yield/return/method signatures. For factory APIs, prefer optional config objects so you can later extend options without breaking callers—see typing functions with optional object parameters in TypeScript — deep dive for recommended patterns.
When performance matters, prefer primitive ids for visited checking over object hashing. Use WeakSet when nodes are ephemeral and you want automatic cleanup. If nodes are large, use numeric ids and compact adjacency lists for memory efficiency.
Best Practices & Common Pitfalls
Dos:
- Do keep your recursive type definitions simple and name them clearly (ListNode, Tree, GraphNode).
- Do use discriminated unions with a literal "kind" field where nodes have variants; combine with using as const for literal type inference in TypeScript when returning literal objects.
- Do write type predicates for runtime refinement and tests; see using type predicates for custom type guards.
- Do validate external data before casting to your types.
Don'ts:
- Don't rely solely on structural typing to enforce runtime invariants. Static types can't prevent malformed JSON.
- Don't use any in constructors or traversal internals; prefer narrow types or unknown with validation.
- Avoid deep recursion in JS for very deep trees; prefer iterative traversals or trampolines.
Common pitfalls:
- Accidentally allowing extra properties on node shapes. Use exact-object patterns from typing objects with exact properties in TypeScript to tighten your APIs.
- Forgetting to mark fields readonly when you intend immutability, leading to subtle bugs.
- Not handling cycles in graphs; always plan for visited checks.
Troubleshooting tips:
- When traversal returns unexpected nodes, log node ids and inspect visited sets.
- If TypeScript union narrowing fails, ensure the discriminant is a literal and not widened; use 'as const' when constructing literals.
Real-World Applications
Recursive data structures power many systems: compilers (ASTs), UI frameworks (component trees), databases (index trees), dependency resolution (directed graphs), and social networks (friend graphs). For example, a data-fetching hook that returns nested results might expose a typed tree—see our practical case study: typing a data fetching hook to learn patterns for typing hook return values that could include nested caches and error nodes.
Other practical uses include form libraries that model nested field groups (see patterns in form management typing), state-management trees for normalized stores, and graph algorithms for dependency analysis. In each case, the combined approach of clear recursive types, runtime validation, and safe traversal produces code that is easier to maintain and reason about.
Conclusion & Next Steps
Typing recursive data structures in TypeScript is a mix of clean type modeling, pragmatic runtime checks, and API design that resists accidental misuse. Start by modeling nodes with named generic types, add discriminated unions for variants, write solid type guards, and ensure traversal algorithms are cycle-safe. Next steps: explore generator typings for advanced iteration patterns, tighten object shapes with exact property patterns, and adopt runtime validators for external inputs.
Recommended reading from this site: dive into typing generator functions and iterators in TypeScript for traversal, typing objects with exact properties in TypeScript to prevent excess properties, and using type predicates for custom type guards for safer runtime refinement.
Enhanced FAQ
Q1: How do I type mutually recursive types (two types refer to each other)?
A1: Use type aliases or interfaces that reference each other by name. For example, a parent-child pair where Parent has children of type Child and Child has a parent of type Parent | null can be typed like:
interface Parent { id: string; children: Child[] }
interface Child { id: string; parent: Parent | null }TypeScript handles mutual recursion fine. Just be mindful of circular JSON serialization if you try to stringify instances.
Q2: Should I use null or undefined for missing children?
A2: Prefer null for explicitly absent pointers because it's explicit and more consistent across interop boundaries. undefined signals optional presence and is useful for properties that may be omitted. Be consistent in your codebase to avoid bugs, and document the choice in your types.
Q3: How can I enforce exact shapes so callers don't pass extra properties into node constructors?
A3: TypeScript's structural typing allows extra properties unless you take steps. Use factory functions and keep constructors narrow, or adopt techniques described in typing objects with exact properties in TypeScript. Another pattern is to use branded types or hidden symbol properties so only factory functions can create valid instances.
Q4: How to detect and handle cycles in graphs while preserving types?
A4: Track visited nodes by id or by object identity using Set or WeakSet. Typings remain the same; the key is runtime algorithm design. For complex algorithms that need to detect strongly connected components, keep separate data structures (maps from id to state) alongside your typed graph.
Q5: Are generators the best way to implement tree traversals?
A5: Generators are expressive and integrate with for..of consumers, and they can be typed precisely. However, they introduce a small overhead. For hot loops or performance-critical code, a manual stack-based iterator might be faster. See typing generator functions and iterators in TypeScript for details on typing and trade-offs.
Q6: How do I handle JSON input that claims to be a tree but is malformed?
A6: Validate before you cast. Use a runtime validator or write defensive checks: verify types of discriminants, ensure arrays where expected, and confirm id uniqueness for graphs. Lightweight validators can be hand-rolled; for complex schemas consider a library. Pair validators with type predicates as shown earlier.
Q7: Can I represent recursive types in JavaScript using JSDoc?
A7: Yes. You can annotate recursive shapes with @typedef and reference them in JSDoc comments so editors and TypeScript can provide checks without full TS migration. See using JSDoc for type checking JavaScript files (@typedef, @type, etc.) for examples.
Q8: How to type APIs that accept multiple node shapes or payload types?
A8: Use generics for payload type variation and discriminated unions for structural variants. If children arrays can contain different node types, model the children array as a union of allowed node types and use type predicates to narrow. Our article on typing arrays of mixed types (union types revisited) is helpful when arrays contain heterogeneous members.
Q9: What performance tips apply to very large trees or graphs?
A9: Avoid recursive functions that can overflow the call stack; use iterative algorithms. Use appropriate data structures: adjacency lists with numeric ids are memory-efficient. Cache expensive computations with Maps keyed by node id. Use WeakSet/WeakMap for ephemeral references to allow GC to reclaim nodes.
Q10: How to design public APIs for constructing trees so they remain extensible?
A10: Prefer factory functions and optional config objects so you can add options without breaking callers. Keep constructor args minimal, avoid positional optional arguments, and use typed options objects as detailed in typing functions with optional object parameters in TypeScript — deep dive. If you need overload-like ergonomics, consider builder patterns or method chaining and consult patterns in method-chaining typing guides.
Further reading: explore typing iterators and generators, exact object shapes, and custom type guards via the links sprinkled through this guide to deepen your mastery of typed recursive structures.