@astrapi69/tree-kit

Typed, serialisable tree structures for TypeScript. Zero runtime dependencies, framework-agnostic.

A TypeScript port of the Java libraries astrapi69/tree-api and astrapi69/gen-tree, redesigned around TypeScript's own idioms rather than transliterated class-for-class.

Install

npm install @astrapi69/tree-kit

The two types

TreeNode<V, K> is pure data: immutable, acyclic, and free of methods. It survives JSON.stringify and structuredClone untouched, so a whole tree goes into localStorage or over the wire without a serialisation step.

interface TreeNode<V, K = string> {
  readonly id: K
  readonly value: V
  readonly children: readonly TreeNode<V, K>[]
}

TreeCursor<V, K> is a transient pointer that knows its own position. It holds the parent reference the node deliberately does not, so parent(), path() and depth() work without making the object graph cyclic.

const cursor = rootCursor(tree)
cursor.children()[0].parent() === cursor   // true - shared instance

Quick start

import {buildTreeFromFlat, walkForest} from "@astrapi69/tree-kit"

interface Topic {
  id: string
  parentId: string | null
  title: string
  position: number
}

const forest = buildTreeFromFlat<Topic, string>(rows, {
  getId: (row) => row.id,
  getParentId: (row) => row.parentId,
  sort: (a, b) => a.position - b.position,
})

for (const cursor of walkForest(forest)) {
  console.log("  ".repeat(cursor.depth()) + cursor.value.title)
}

localStorage.setItem("topics", JSON.stringify(forest))

Strict by default, tolerant on request

buildTreeFromFlat rejects structural defects loudly — the right answer for data that is supposed to be sound, because a silent repair hides the upstream bug that produced it. Views are different: a page rendering FILTERED rows, or whatever a sync left behind, must show the data it has, not crash on the row it cannot place. That is what onInvalidParent: "promoteToRoot" is for:

const forest = buildTreeFromFlat<Category, string>(rows, {
  getId: (row) => row.path,
  getParentId: (row) => row.parentPath,
  onInvalidParent: "promoteToRoot",
})

| Defect | "throw" (default) | "promoteToRoot" | |---|---|---| | Parent id names no row | Error: ... references unknown parent | Row becomes a root | | Cycle (a -> b -> a) | Error: cycle detected | Every member becomes a root | | Row hanging below a cycle | Error: cycle or orphan rows | Becomes a root too — its chain never terminates either | | Duplicate id | Error: duplicate id | Still throws. Two rows with one id is corruption no placement can express |

The rule is one sentence: a row is promoted to a root when its parent id names no row, or its ancestor chain never reaches a root. Valid nesting in the same input stays intact, promoted roots take part in the sibling sort like real ones, and the resolution is memoised so the build stays O(n).

Which mode belongs where:

• Ingest, import, persistence — keep the default. If a workbook or API response carries a dangling reference, you want the exception and the offending id, not a silently reshaped tree.
• Rendering — opt in. The two real-world shapes this option came from: a category tree where a child can outlive its deleted parent (orphan report exists, the view must still render), and an inventory view over a FILTERED row list, where a visible child of a filtered-out parent must not vanish.
• Custom degradation — stays yours. promoteToRoot promotes to the FOREST root; if your domain wants something else (Topos degrades containers to their type/owner group instead), resolve parents yourself before building and keep the option as a second net.

Traversal is for...of

There is no Visitor callback and no sentinel return value. Stop with break.

for (const cursor of walk(tree, "breadth")) {
  if (cursor.depth() > 2) break
  render(cursor)
}

Three orders: pre (default, parents first), post (children first), breadth (level by level). walkForest synchronises breadth-first levels across roots; pre and post finish one root's subtree before starting the next.

find is lazy and stops at the first match:

const match = find(tree, (cursor) => cursor.id === target)
match?.path().map((node) => node.id)   // breadcrumb

Typed ids

K defaults to string but is free to be a number or a branded string, so ids from two different trees cannot silently cross at compile time.

type TopicId = string & {readonly __brand: "TopicId"}
type LessonId = string & {readonly __brand: "LessonId"}

const topics: TreeNode<Topic, TopicId> = /* ... */
find(topics, (cursor) => cursor.id === someLessonId)   // compile error

Editing is copy-on-write

TreeNode is readonly, so editing a tree means building a new one. Every mutation takes a forest and a cursor at the target, and returns a new forest — the input is never touched. Only the nodes from a root down to the edit are re-allocated; every sibling subtree and untouched root comes back by identity (===), so a deep change costs O(depth) new objects, not O(n). The result stays JSON.stringify- and structuredClone-safe like everything the builder makes.

import {addChild, moveNode, removeNode, updateValue, find} from "@astrapi69/tree-kit"

const target = find(forest[0], (c) => c.id === "menu")!
const withItem = addChild(forest, target, {id: "help", value: {label: "Help"}, children: []})

const renamed = updateValue(withItem, find(withItem[0], (c) => c.id === "help")!, {label: "Support"})

// Drag & drop: reparent a subtree. Throws if the target is inside the source.
const dst = find(renamed[0], (c) => c.id === "sidebar")!
const src = find(renamed[0], (c) => c.id === "help")!
const moved = moveNode(renamed, src, dst)

const pruned = removeNode(moved, find(moved[0], (c) => c.id === "help")!)

Untouched subtrees keep their identity, which is exactly what memoised renders and cheap undo stacks rely on:

const next = updateValue(forest, deepCursor, newValue)
next[0].children[1] === forest[0].children[1]   // true — off the edited path

flatten is the inverse of buildTreeFromFlat: a forest back to parent-linked rows, in pre-order, so the two round-trip.

const rows = flatten(forest)          // [{id, parentId, value}, ...]
const again = buildTreeFromFlat(rows, {getId: (r) => r.id, getParentId: (r) => r.parentId})

Transform and query

mapValues, filterTree and reduceTree are the tree-shaped counterparts to Array's map / filter / reduce. filterTree keeps the hierarchy of the survivors — dropping an intermediate node promotes its kept descendants rather than deleting them — so it returns a forest, unlike findAll's flat list.

const titles = mapValues(forest[0], (topic) => topic.title)          // TreeNode<string>
const published = filterTree(forest[0], (n) => n.value.status !== "draft")
const total = reduceTree(forest[0], (sum, topic) => sum + topic.position, 0)

The structural queries mirror the Java forebears' vocabulary (getAllSiblings, level/depth, ancestor tests) without their mutable node: height, siblings, isAncestor / isDescendant, lowestCommonAncestor, extractSubtree, cloneSubtree.

lowestCommonAncestor(childA, childB)?.id   // breadcrumb / permission scope

API

| Export | Kind | Purpose | |---|---|---| | TreeNode<V, K> | type | Immutable, acyclic, serialisable node | | TreeCursor<V, K> | type | Navigable position inside a tree | | TraversalStrategy | type | "pre" \| "post" \| "breadth" | | DisplayFormatter<V> | type | (value: V) => string | | BuildTreeOptions<V, K> | type | Key extractors, optional sibling sort, onInvalidParent | | FlatNode<V, K> | type | {id, parentId, value} row produced by flatten | | buildTreeFromFlat | fn | Flat (id, parentId) rows into a forest, O(n) | | rootCursor | fn | Cursor at a node, treated as a root | | walk | fn | Generator over one subtree | | walkForest | fn | Generator over several roots | | find / findAll | fn | First / all matching cursors | | count | fn | Node count including the root | | displayValue | fn | Label for a node, via an optional formatter | | addChild | fn | Append a child, copy-on-write → new forest | | removeNode | fn | Drop a node and its subtree → new forest | | moveNode | fn | Reparent a subtree; throws on a cyclic move | | updateValue | fn | Replace one node's value, keep its subtree | | replaceSubtree | fn | Swap the subtree at a cursor | | flatten | fn | Forest → parent-linked rows, inverse of the builder | | mapValues | fn | New tree with transformed values, ids preserved | | filterTree | fn | Keep matches, reparent survivors → forest | | reduceTree | fn | Fold all values into one accumulator | | height | fn | Deepest descent below a node | | siblings | fn | The cursor's same-parent neighbours | | isAncestor / isDescendant | fn | Proper ancestor / descendant test | | lowestCommonAncestor | fn | Nearest node above two cursors | | extractSubtree | fn | The subtree at a cursor as a standalone tree | | cloneSubtree | fn | Deep, independent copy with optional id remap |

Design notes

Why no parent pointer on the node. It would make the object graph cyclic: JSON.stringify throws TypeError: Converting circular structure to JSON, structuredClone throws, and debuggers walk in circles. The parent lives on the cursor instead, which is transient and never serialised.

Why no [Symbol.iterator] on the node. A method is an own property. JSON.stringify would drop it silently, but structuredClone refuses to clone functions outright — the node would stop being clonable. Iteration lives on the cursor: for (const each of rootCursor(tree)).

Why no formatter stored on the tree. A label is a rendering concern, and storing a function on the node would break clonability for the same reason. displayValue(node, formatter) takes it at call time.

Cursor identity is deliberate. cursor.parent() returns the same instance on every call and children() memoises, so sibling cursors compare equal on their parent and Set / memo dependencies behave. Compare cursor.node when comparing positions across independent traversals.

Every pass is iterative. Build, sort and all three traversals run on an explicit stack rather than recursion, so a chain deeper than the call stack is handled like any other input. Pinned by a 50 000-level test.

Construction is O(n). One pass indexes rows by id in a Map, one pass links each row to its parent with an O(1) lookup. Duplicate ids, unknown parent references and cycles all throw with the offending ids named — a silent drop would hide the upstream bug that produced them. The tolerant mode (onInvalidParent: "promoteToRoot") trades the exception for a visible degradation — promotion to a root — and only for the two defects a view can meaningfully survive; duplicate ids stay fatal in both modes. Its chain resolution is memoised, so tolerance costs no complexity class.

Maturity: which surface is proven

The package ships three surfaces, and they do not carry the same weight of evidence. The version number says so on purpose.

TreeNode and buildTreeFromFlat are proven by use. They were migrated into a real application before this package was first published: five lines changed, 735 deleted, no addition needed. The shape held against a consumer. The tolerant mode (0.2.0) came the same way, from the consumer side: Topos had written the identical pre-sanitizer twice (a category tree tolerating orphans, an inventory tree over filtered rows), and adaptive-learner called the builder raw - a latent crash on the first dangling reference. The option replaced both Topos sanitizers with their behaviour pins staying green unchanged, and adaptive-learner closed its latent crash with the one-line opt-in (its curriculum now renders an orphaned topic at top level instead of throwing) - two applications consume the tolerant mode in production.

TreeCursor is proven by tests only. No consumer has used parent(), path() or depth() yet. It exists because the alternative was a parent pointer on the node, which would have cost JSON.stringify and structuredClone — that reasoning stands on its own. But a surface without a user is a prediction about what someone will need, and its first real use (keyboard focus and breadcrumbs in a menu engine) is still ahead. Expect it to move before 1.0.

The mutation and query surface (0.3.0) is proven by tests only, and by design review. 110 tests pin copy-on-write semantics, structural sharing and the cyclic-move guard, and the runnable example asserts the sharing property live (=== on the untouched subtree). But no application edits its trees through this surface yet - the first candidate (reparenting topics in a curriculum view) is known and still ahead. Same caveat as the cursor: a surface without a consumer is a prediction.

This is what 0.x is for. One surface is verified by use, two are expected, and the number should not claim otherwise.

Planned, awaiting a consumer

Some API is deliberately not built yet. The rule (see CONTRIBUTING): new surface needs a real caller, not a use case - a library grows credibility by what it refuses to predict. Each entry below is tracked, with the trigger that would turn it into code:

| Idea | Trigger that unlocks it | Tracked | |---|---|---| | merge(forestA, forestB) with a conflict strategy | Live collaboration or two-source sync in a consumer app | #9 | | diff(forestA, forestB) for incremental updates | Same - shipping deltas instead of whole forests | #9 | | Orphan-collection variant of onInvalidParent | A caller that wants to HANDLE invalid rows programmatically instead of rendering them promoted | #10 |

Two shipped surfaces are in the same waiting room, just further along: the cursor (its first real use - keyboard focus and breadcrumbs - is still ahead) and the 0.3.0 mutation surface, whose first named candidate is reparenting curriculum topics via moveNode in adaptive-learner. The maturity section above tracks both honestly.

Changelog

See CHANGELOG.md for the release history.

Examples

Runnable scripts under examples/: the happy path (build, sort, cursor traversal, serialisation), the tolerant mode side by side with the strict default on the same defective rows, and the copy-on-write surface - a move with the structural-sharing identity check, the cyclic-move refusal, and flatten closing the circle back to rows.

npm run build && node examples/mutations.mjs

Development

make install     # install dependencies
make test        # run the suite
make check-all   # lint + typecheck + test + build
make inspect     # show exactly what would be published

License

MIT — Asterios Raptis