I wanted to convert hierarchical data expressed in a flattened self-referencing table (in csv) back to a decent hierarchical JSON structure.
In other words...
). You can find the source, an example using d3 to illustrate the hierarchy and tests on github here
Tree has a root node, the ability to find a node in itself (given an optional matching function) and importantly a factory method that can create a tree given a flat self referencing table.
The root node is a DataStructures.TreeNode and has a children reference which is instantiated as DataStructures.TreeNodeCollection.
To simplify traversal I made Tree able to iterate through its nodes by using a depth first non-recursive approach (by using a queue) to finding the next node.
Once I had the initial structure in place, the next task was to convert from this Tree structure and its attributes (which had a lot to do with traversal and relationships), back to a simple leaner json object, so I added a toSimpleObject method, which also allows for a decorator function to be passed in to do bespoke formatting/manipulation.
This was particularly useful for the d3 case that I wanted to use this with (see example in index.html), where I needed to add size values to leaf nodes and remove empty children attributes to indicate which nodes are actually leaves.
There are quite a few potential improvements I've already identified, in the building of the tree from csv I assume that parent nodes already exist when I come across a child row, and the algorithm could and should be optimised, but for now, I'm getting what I want from it!
If you're interested, theres a set of unit tests written with QUnit to illustrate how it all fits together under /js/lib/tests
Any suggestions welcome! ping me on twitter : @stephenhjames or leave a comment
credit for the d3 code used in index.html goes to Mike Bostock (@mbostock) and Jeff Heer (@jeffrey_heer) as it was copied from http://bl.ocks.org/mbostock/4063530 with only a couple of line changes to pop in the csv load and conversion using Tree.