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));