@chaisser/tree-shake

Tree data structure utilities

Create, query, traverse, modify, and transform tree data structures. Works with any TreeNode<T> shape — no framework dependencies.

Features

• Create trees from flat lists, pairs, or nested objects
• Traversal: pre-order, post-order, in-order, level-order
• Query by id, path, predicate, depth, data
• Modify: add, remove, move, replace, clone nodes
• Filter, map, reduce over tree nodes
• Measure: depth, size, leaf count, branching factor, balance check
• Merge and split trees
• Prune subtrees by depth
• Convert to flat list, array, map, or object
• Full TypeScript support with generics

Installation

npm install @chaisser/tree-shake
# or
yarn add @chaisser/tree-shake
# or
pnpm add @chaisser/tree-shake

Quick Start

import {
  createNode,
  findNodeById,
  findPath,
  preOrder,
  depth,
  size,
  toString
} from '@chaisser/tree-shake';

const tree = createNode('root', { name: 'Root' }, [
  createNode('users', { name: 'Users' }, [
    createNode('alice', { name: 'Alice' }),
    createNode('bob', { name: 'Bob' })
  ]),
  createNode('posts', { name: 'Posts' }, [
    createNode('post-1', { name: 'Hello World' })
  ])
]);

console.log(toString(tree));
// root {"name":"Root"} (2)
//   users {"name":"Users"} (2)
//     alice {"name":"Alice"}
//     bob {"name":"Bob"}
//   posts {"name":"Posts"} (1)
//     post-1 {"name":"Hello World"}

console.log(size(tree));    // 6
console.log(depth(tree));   // 2
console.log(findPath(tree, 'alice')); // ['root', 'users', 'alice']
console.log(preOrder(tree).map(n => n.id)); // ['root', 'users', 'alice', 'bob', 'posts', 'post-1']

API Reference

Node Type

interface TreeNode<T = unknown> {
  id: string;
  data?: T;
  children?: TreeNode<T>[];
}

Create

| Function | Description | |----------|-------------| | createNode(id, data?, children?) | Create a single node | | createTree(root) | Wrap root in a tree | | fromFlatList(items) | Build from [{ id, parentId?, data? }] | | fromPairs(pairs) | Build from [[id, parentId, data?]] | | fromObject(obj, idKey?) | Build from nested plain object |

Convert

| Function | Returns | |----------|---------| | toFlatList(node) | [{ id, parentId, data }] | | toArray(node) | T[] of all data values | | toObject(node) | Nested plain object | | toMap(node) | Map<id, TreeNode> |

Query

| Function | Description | |----------|-------------| | findNode(root, predicate) | First node matching predicate | | findNodeById(root, id) | Node by id | | findNodes(root, predicate) | All matching nodes | | findPath(root, id) | Path array from root to node | | findPathTo(root, predicate) | Path to first matching node | | findAncestors(root, id) | Ancestor chain | | findDescendants(node) | All descendant nodes | | findLeaves(root) | All leaf nodes | | findCommonAncestor(root, idA, idB) | Lowest common ancestor | | findNodesAtDepth(root, depth) | Nodes at given depth | | findNodesByData(root, predicate) | Nodes matching data predicate | | contains(root, id) | Check if id exists | | getNodeByPath(root, path) | Node by path array | | getNodeDepth(root, id) | Depth of node (-1 if missing) | | getParent(root, id) | Parent node | | getSiblings(root, id) | Sibling nodes | | getChildren(node) | Children array | | getChildAt(node, index) | Child at index | | getFirstChild(node) | First child | | getLastChild(node) | Last child |

Traverse

| Function | Description | |----------|-------------| | preOrder(root) | Root, then children (depth-first) | | postOrder(root) | Children, then root | | inOrder(root) | Left child, node, remaining children | | levelOrder(root) | Breadth-first | | traverse(root, visitor, strategy) | Visit with (node, depth, parent) callback | | forEach(root, fn) | Iterate with (node, depth) callback |

Modify

| Function | Description | |----------|-------------| | addChild(parent, child) | Append child | | removeChild(parent, childId) | Remove child by id | | insertChildAt(parent, child, index) | Insert at position | | replaceNode(root, targetId, replacement) | Replace node | | updateNode(root, targetId, updater) | Update with function | | updateNodeData(root, targetId, data) | Update node data | | removeNode(root, targetId) | Remove node and its subtree | | moveNode(root, nodeId, newParentId, index?) | Move node to new parent | | cloneNode(node) | Deep clone | | cloneSubtree(root, id) | Clone subtree by id |

Measure

| Function | Returns | |----------|---------| | depth(root) | Max depth | | size(root) | Total node count | | leafCount(root) | Leaf node count | | internalCount(root) | Non-leaf node count | | branchingFactor(root) | Average children per internal node | | getStats(root) | { totalNodes, leafCount, internalCount, maxDepth, branchingFactor } | | getWidthAtDepth(root, d) | Node count at depth |

Check

| Function | Description | |----------|-------------| | isLeaf(node) | No children | | isInternal(node) | Has children | | isRoot(node, rootId) | Is root node | | contains(root, id) | Id exists in tree | | isAncestorOf(root, ancId, descId) | Ancestor relationship | | isDescendantOf(root, descId, ancId) | Descendant relationship | | isSibling(root, idA, idB) | Same parent | | isEmpty(node) | Leaf with no data | | isBalanced(root) | Depth differs by at most 1 | | equals(a, b) | Structural equality |

Filter & Map

| Function | Description | |----------|-------------| | filter(root, predicate) | Keep matching subtrees | | filterWithAncestors(root, predicate) | Keep matches and their ancestors | | map(root, fn) | Transform data with function | | mapIds(root, fn) | Transform ids with function | | reduce(root, fn, initialValue) | Reduce to single value |

Sort

| Function | Description | |----------|-------------| | sortChildren(root, comparator) | Sort children at all levels | | sortById(root, direction?) | Sort by id ascending or descending |

Flatten

| Function | Returns | |----------|---------| | flattenPaths(root) | { id, path }[] for every node | | flattenIds(root) | All node ids | | flattenData(root) | All data values |

Merge & Split

| Function | Description | |----------|-------------| | merge(a, b, mergeData?) | Merge two trees by id | | splitAt(root, id) | Split into removed + remaining | | subtree(root, id) | Clone subtree by id | | prune(root, maxDepth) | Remove nodes beyond depth |

Print

| Function | Description | |----------|-------------| | toString(root, indent?) | Human-readable tree string |

Examples

Build from Flat List

import { fromFlatList, toString } from '@chaisser/tree-shake';

const tree = fromFlatList([
  { id: '1', data: 'CEO' },
  { id: '2', parentId: '1', data: 'VP Eng' },
  { id: '3', parentId: '1', data: 'VP Sales' },
  { id: '4', parentId: '2', data: 'Eng Lead' },
  { id: '5', parentId: '2', data: 'QA Lead' }
]);

console.log(toString(tree!));

Traverse and Collect

import { createNode, levelOrder, reduce } from '@chaisser/tree-shake';

const tree = createNode('root', 1, [
  createNode('a', 2, [createNode('a1', 3)]),
  createNode('b', 4)
]);

// Sum all data
const total = reduce(tree, (acc, node) => acc + (node.data ?? 0), 0);
// 10

// Breadth-first ids
levelOrder(tree).map(n => n.id);
// ['root', 'a', 'b', 'a1']

Filter with Ancestors

import { filterWithAncestors, toString } from '@chaisser/tree-shake';

const tree = createNode('root', undefined, [
  createNode('a', undefined, [createNode('a1', 'target'), createNode('a2')]),
  createNode('b', undefined, [createNode('b1', 'target')])
]);

const filtered = filterWithAncestors(tree, n => n.data === 'target');
// Keeps: root, a, a1, b, b1 (preserves paths to matches)

Merge Trees

import { createNode, merge, toString } from '@chaisser/tree-shake';

const a = createNode('root', undefined, [
  createNode('users', { count: 5 }),
  createNode('posts', { count: 10 })
]);

const b = createNode('root', undefined, [
  createNode('users', { count: 8, active: true }),
  createNode('comments', { count: 20 })
]);

const merged = merge(a, b, (dA, dB) => ({ ...dA, ...dB }));
// root -> users({count:8,active:true}), posts({count:10}), comments({count:20})

Prune by Depth

import { createNode, prune, depth, size } from '@chaisser/tree-shake';

const tree = createNode('root', undefined, [
  createNode('a', undefined, [
    createNode('a1', undefined, [createNode('a1a')]),
    createNode('a2')
  ])
]);

const pruned = prune(tree, 2);
// Removes nodes deeper than depth 2 (a1a is removed)

License

MIT