@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