Agnostic: Supports any kind of tree. You provide a way to access a node's children, that's it.
Fast: Crafted to be optimizer-friendly. See performance for more details.
Mutation friendly: Does not 💥 when you mutate the tree.
Multiple orders: Supports DFS pre and post order and BFS traversals.
Quickstart
Installation
You can install tree-crawl with yarn:
$ yarn add tree-crawl
Alternatively using npm:
$ npm install --save tree-crawl
Usage
import crawl from 'tree-crawl'// traverse the tree in pre-ordercrawl(tree, console.log)crawl(tree, console.log, { order: 'pre' })// traverse the tree in post-ordercrawl(tree, console.log, { order: 'post' })// traverse the tree using `childNodes` as the children keycrawl(tree, console.log, { getChildren: node => node.childNodes })// skip a node and its childrencrawl(tree, (node, context) => { if ('foo' === node.type) { context.skip() }})// stop the walkcrawl(tree, (node, context) => { if (
If you are really concerned about performance, you could read items from the stack directly. Each item has a node and index property that you can use. The first item in the stack can be discarded and will have a node set to null. Be aware that you should not mutate the stack, or it will break the traversal.
If you are using BFS, things gets more complex. A simple hacky way to do so is to traverse the tree using DFS first. You can ad a path property to your nodes using the method above. And then do your regular BFS traversal using that path property.
Notifies that the current node has been removed, children won't be visited.
Because tree-crawl has no idea about the intrinsic structure of your tree, you have to
remove the node yourself. Context#remove only notifies the traversal code that the structure
of the tree has changed.
Notifies that the current node has been replaced, the new node's children will be visited
instead.
Because tree-crawl has no idea about the intrinsic structure of your tree, you have to
replace the node yourself. Context#replace notifies the traversal code that the structure of
the tree has changed.
tree-crawl is built to be super fast and traverse potentially huge trees. It's possible because it implements its own stack and queue for traversal algorithms and makes sure the code is optimizable by the VM.
If you do need real good performance please consider reading this checklist first.
Your main objective is to keep the traversal code optimized and avoid de-optimizations and bailouts. To do so, your nodes should have the same hidden class and your code stay monomorphic.