Как типизировать рекурсивную структуру данных (дерево)?

// Узел дерева — children ссылается на тот же тип
interface TreeNode<T> {
  value: T;
  children: TreeNode<T>[];
}

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

// Бинарное дерево — left/right или null
interface BinaryTree<T> {
  value: T;
  left: BinaryTree<T> | null;
  right: BinaryTree<T> | null;
}

const bst: BinaryTree<number> = {
  value: 10,
  left: {
    value: 5,
    left: { value: 2, left: null, right: null },
    right: { value: 7, left: null, right: null },
  },
  right: {
    value: 15,
    left: null,
    right: { value: 20, left: null, right: null },
  },
};

// Поиск в глубину — TypeScript отслеживает тип T

function find<T>(node: TreeNode<T>, predicate: (value: T) => boolean): T | undefined {
  if (predicate(node.value)) return node.value;

  for (const child of node.children) {
    const result = find(child, predicate);
    if (result !== undefined) return result;
  }

  return undefined;
}

// map по дереву — преобразование значений

function mapTree<T, U>(node: TreeNode<T>, fn: (value: T) => U): TreeNode<U> {
  return {
    value: fn(node.value),
    children: node.children.map((child) => mapTree(child, fn)),
  };
}

const numTree = mapTree(tree, (s) => s.length);

// TreeNode<number> — TypeScript вывел тип

// Меню: элемент либо ссылка, либо группа с подменю
type MenuItem =
| { kind: "link"; label: string; href: string }
| { kind: "group"; label: string; children: MenuItem[] };

const menu: MenuItem[] = [
  { kind: "link", label: "Home", href: "/" },
  {
    kind: "group",
    label: "Products",
    children: [
      { kind: "link", label: "Laptop", href: "/laptop" },
      {
        kind: "group",
        label: "Accessories",
        children: [
          { kind: "link", label: "Mouse", href: "/mouse" },
        ],
      },
    ],
  },
];

function renderMenu(items: MenuItem[], depth = 0): string {
  return items
  .map((item) => {
      const indent = "  ".repeat(depth);
      if (item.kind === "link") {
        return `${indent}<a href="${item.href}">${item.label}</a>`;
      }
      return `${indent}<div>${item.label}</div>
      ${renderMenu(item.children, depth + 1)}`;
    })
  .join("
    ");
}

type FSEntry =
| { type: "file"; name: string; size: number }
| { type: "dir"; name: string; entries: FSEntry[] };

function totalSize(entry: FSEntry): number {
  if (entry.type === "file") return entry.size;
  return entry.entries.reduce((sum, e) => sum + totalSize(e), 0);
}

const project: FSEntry = {
  type: "dir",
  name: "src",
  entries: [
    { type: "file", name: "index.ts", size: 1024 },
    {
      type: "dir",
      name: "utils",
      entries: [
        { type: "file", name: "helpers.ts", size: 512 },
      ],
    },
  ],
};

console.log(totalSize(project)); // 1536

type Expression =
| { type: "number"; value: number }
| { type: "string"; value: string }
| { type: "binary"; op: "+" | "-" | "*" | "/"; left: Expression; right: Expression }
| { type: "call"; callee: string; args: Expression[] };

function evaluate(expr: Expression): number {
  switch (expr.type) {
    case "number": return expr.value;
    case "binary": {
      const l = evaluate(expr.left);
      const r = evaluate(expr.right);
      const ops = { "+": (a: number, b: number) => a + b, "-": (a: number, b: number) => a - b,
        "*": (a: number, b: number) => a * b, "/": (a: number, b: number) => a / b };
      return ops[expr.op](l, r);
    }
    default: throw new Error(`Cannot evaluate ${expr.type}`);
  }
}

// ❌ Это не скомпилируется осмысленно
// type Infinite = Infinite[];

// ✅ Всегда нужен базовый случай (примитив, null, пустой массив)
type Finite = string | Finite[];