Recursive generic types in Typescript

Introduction

Recursive generic types let you define types that refer to themselves. This helps describe complex, nested data like trees or linked lists in a safe way.

When you want to represent a tree structure where each node can have children of the same type.

When defining a linked list where each element points to the next element of the same type.

When modeling nested JSON objects where properties can be the same type recursively.

When creating a type-safe way to handle deeply nested data structures like menus or folders.

Syntax

Typescript

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

The interface TreeNode refers to itself inside the children property.

This allows nesting the same type inside itself to any depth.

Examples

A linked list node points to the next node of the same type or undefined if it is the last.

Typescript

interface LinkedListNode<T> {
  value: T;
  next?: LinkedListNode<T>;
}

This type allows arrays nested inside arrays recursively.

Typescript

interface NestedArray<T> {
  value: T | NestedArray<T>[];
}

Shows a single node with no next node (end of list).

Typescript

interface EmptyNode<T> {
  value: T;
  next?: EmptyNode<T>;
}

// Edge case: single node with no next
const singleNode: EmptyNode<number> = { value: 5 };

A tree node with an empty children array means it has no children.

Typescript

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

// Edge case: empty children array
const leafNode: TreeNode<string> = { value: "leaf", children: [] };

Sample Program

This program defines a recursive generic type TreeNode for a tree structure. It creates a tree of numbers with nested children. The printTree function prints each node's value with indentation to show the tree shape.

Typescript

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

// Create a tree of numbers
const rootNode: TreeNode<number> = {
  value: 1,
  children: [
    { value: 2 },
    {
      value: 3,
      children: [
        { value: 4 },
        { value: 5 }
      ]
    }
  ]
};

// Function to print tree values recursively
function printTree<T>(node: TreeNode<T>, indent = "") {
  console.log(`${indent}${node.value}`);
  if (node.children) {
    for (const child of node.children) {
      printTree(child, indent + "  ");
    }
  }
}

console.log("Tree structure:");
printTree(rootNode);

Important Notes

Time complexity of traversing recursive types depends on the number of nodes (usually O(n)).

Space complexity depends on recursion depth and stored data.

Common mistake: forgetting the optional property for recursion base case, causing infinite recursion or errors.

Use recursive generic types when you need to model nested or linked data safely with TypeScript's type system.

Summary

Recursive generic types let types refer to themselves to model nested data.

They are useful for trees, linked lists, and nested structures.

Always include a base case (like optional properties) to avoid infinite recursion.