Create a Tree Node from JavaScript Array

Question

I'm trying to create a list of subpaths from a flattened array.

Here's the starting point:

var flat = [
 {path: "/" },
 {path: "A" },
 {path: "A.A"},
 {path: "A.B"},
 {path: "A.C"},
 {path: "B" },
 {path: "C" }
]

The goal is that anything under a parent would be a subpath of that. So the goal would look like this:

var goal = [
 {path: "/" },
 {path: "A",
 subpaths: [
 {path: "A.A"},
 {path: "A.B"},
 {path: "A.C"}
 ]
 },
 {path: "B" },
 {path: "C" }
]

I've hobbled together a solution, but it doesn't feel very clean and is probably prone to breakage:

var nested = [];
for (var i=0; i < flat.length; i++) {
 // split components up
 var routes = flat[i].path.split(".");
 // get parent key
 var key = routes[0];
 // check if we've already added the key
 var index = -1;
 for (var j=0; j < nested.length; j++) {
 if (nested[j].path == key) {
 index = j;
 break;
 }
 }
 if (index===-1) {
 // if we have a new parent add it
 nested.push(flat[i])
 } else { 
 // create subpaths property on new object
 if (!nested[index].subpaths) { nested[index].subpaths = [] }
 // add child paths to existing parent
 nested[index].subpaths.push(flat[i])
 }
}

Here's a working Demo in Stack Snippets

var flat = [
 {path: "/" },
 {path: "A" },
 {path: "A.A"},
 {path: "A.B"},
 {path: "A.C"},
 {path: "B" },
 {path: "C" }
]
var nested = [];
for (var i=0; i < flat.length; i++) {
 // split components up
 var routes = flat[i].path.split(".");
 
 // get parent key
 var key = routes[0];
 // check if we've already added the key
 var index = -1;
 for (var j=0; j < nested.length; j++) {
 if (nested[j].path == key) {
 index = j;
 break;
 }
 }
 
 if (index===-1) {
 // if we have a new parent add it
 nested.push(flat[i])
 
 } else { 
 // create subpaths property on new object
 if (!nested[index].subpaths) { nested[index].subpaths = [] }
 
 // add child paths to existing parent
 nested[index].subpaths.push(flat[i])
 }
}
console.log(nested);

I'm also open to using jQuery or Underscore if they expose any functionality that would tidy up the source code. I'd also like to modify the code so it could handle this recursively with an unspecified level of depth on each node.

Answer 1

Your code seems to only support 2 levels down. Also, the second loop is costly because it has to search through the array if the path already exists.

I believe your structure can be better represented using an object. Lookups won't need searching through, and there's still room for path metadata.

var goal = {
 // Room for "goal" metadata.
 "/": {},
 "A": {
 // Room for "A" metadata.
 subpaths: {
 "A": {},
 "B": {},
 "C": {},
 }
 },
 "B": {},
 "C": {},
}

Here's an example

var paths = [
 {path: "/" },
 {path: "A" },
 {path: "A.A"},
 {path: "A.B"},
 {path: "A.C"},
 {path: "A.D.C"},
 {path: "B" },
 {path: "C" }
];
// Move out or template into a creator function.
function createPath(){
 return {
 subpaths: {}
 };
}
// Resolves the path into objects iteratively (but looks eerily like recursion).
function resolvePath(root, path){
 path.split('.').reduce(function(pathObject, pathName){
 // For each path name we come across, use the existing or create a subpath
 pathObject.subpaths[pathName] = pathObject.subpaths[pathName] || createPath();
 // Then return that subpath for the next operation
 return pathObject.subpaths[pathName];
 // Use the passed in base object to attach our resolutions
 }, root);
}
var goal = paths.reduce(function(carry, pathEntry){
 // On every path entry, resolve using the base object
 resolvePath(carry, pathEntry.path);
 // Return the base object for suceeding paths, or for our final value
 return carry;
// Create our base object
}, createPath());
document.write(JSON.stringify(goal));