This module provides a simple API to create trees from adjacency lists. Specifically, given an array of JSON objects with ids and pointers to their parent ids, we can construct a tree structure and furnish operations on that structure.
/*** This tree looks like this:* ROOT* / | \* id:1 id:4 id:6* / / \* id:2 id:7 id:3* /* id:5*/const nodes =id : 1parent : 0id : 2parent : 1id : 3parent : 6valueA : 10valueB : 2id : 4parent : 0valueA : 30valueB : 4id : 5parent : 2valueA : 9valueB : 7id : 6parent : 0id : 7parent : 6valueA : 10valueB : 19;const tree = nodes;tree;// => 1, 2, 5, 4, 6, 7, 3
The API is simple but powerful. Most operations on trees can be defined as recursive functions, where a property of a
node is either determined by a parent property or an aggregation of the child properties. For example, the depth of
N is simply the depth of
N's parent plus 1. Similarly, to compute a sum on the parent nodes, simply update
the parent node's value for every child in the tree.
The following API functions are supported:
walk(fn, callFnBeforeRecurse = true)
Walks the tree in order and applies
fn() either before or after the recursive (descent) step. The
fn function can
take in two properties
Finds a node in the tree by its id.
Sorts the tree in place using the comparison function
fn function is internally passed to
To keep operations simple, the library expects you to use
walk() for the majority of your operations. However,
walk() functions are exposed through the
Tree.common object. These are documented below:
depth all nodes as a function of their parents depths property. The root node is
depth = 0 and subsequent
childNode.depth = parentNode.depth + 1.
const tree = nodes;tree;// each node now has node.depth set on it!const node = tree;console;
sumOnProperty(property, defaultValue = 0)
Aggregates the value of parent nodes as a function of their children. For example, if a parent has two children with
5, the parent's value will be
// an adjency tree of one parent, two childrenconst nodes =id: 1 value: nullid: 2 value: 3 parent : 1id: 3 value: 10 parent : 1;const tree = nodes;tree;const node2 = tree;console; // => 3const node1 = tree;console; // => 13