Create nested object from multiple string paths

Question

I'm looking for the best way to convert multiple string paths to a nested object with javascript. I'm using lodash if that could help in any way.

I got the following paths:

/root/library/Folder 1
/root/library/Folder 2
/root/library/Folder 1/Document.docx
/root/library/Folder 1/Document 2.docx
/root/library/Folder 2/Document 3.docx
/root/library/Document 4.docx

and I would like to create the following array of object:

  var objectArray =
    [
      {
        "name": "root", "children": [
          {
            "name": "library", "children": [
              {
                "name": "Folder 1", "children": [
                  { "name": "Document.docx", "children": [] },
                  { "name": "Document 2.docx", "children": [] }
                ]
              },
              {
                "name": "Folder 2", "children": [
                  { "name": "Document 3.docx", "children": [] }
                ]
              },
              {
                "name": "Document 4.docx", "children": []
              }
            ]
          }
        ]
      }
    ];

Answer 1

I suggest implementing a tree insertion function whose arguments are an array of children and a path. It traverses the children according to the given path and inserts new children as necessary, avoiding duplicates:

// Insert path into directory tree structure:
function insert(children = [], [head, ...tail]) {
  let child = children.find(child => child.name === head);
  if (!child) children.push(child = {name: head, children: []});
  if (tail.length > 0) insert(child.children, tail);
  return children;
}

// Example:
let paths = [
  '/root/library/Folder 1',
  '/root/library/Folder 2',
  '/root/library/Folder 1/Document.docx',
  '/root/library/Folder 1/Document 2.docx',
  '/root/library/Folder 2/Document 3.docx',
  '/root/library/Document 4.docx'
];

let objectArray = paths
  .map(path => path.split('/').slice(1))
  .reduce((children, path) => insert(children, path), []);

console.log(objectArray);

Answer 2

Iterate over each string and resolve it to an object:

var glob={name:undefined,children:[]};

["/root/library/Folder 1","/root/library/Folder 2","/root/library/Folder 1/Document.docx","/root/library/Folder 1/Document 2.docx","/root/library/Folder 2/Document 3.docx","/root/library/Document 4.docx"]
.forEach(function(path){

  path.split("/").slice(1).reduce(function(dir,sub){

     var children;

     if(children=dir.children.find(el=>el.name===sub)){
       return children;
     }

     children={name:sub,children:[]};
     dir.children.push(children);
     return children;

  },glob);

});

console.log(glob);

http://jsbin.com/yusopiguci/edit?console

---

Improved version:

var glob={name:undefined,children:[]};
var symbol="/" /* or Symbol("lookup") in modern browsers */ ;
var lookup={[symbol]:glob};

["/root/library/Folder 1","/root/library/Folder 2","/root/library/Folder 1/Document.docx","/root/library/Folder 1/Document 2.docx","/root/library/Folder 2/Document 3.docx","/root/library/Document 4.docx"]
.forEach(function(path){

  path.split("/").slice(1).reduce(function(dir,sub){
     if(!dir[sub]){
      let subObj={name:sub,children:[]};
      dir[symbol].children.push(subObj);
      return dir[sub]={[symbol]:subObj};
    }
    return dir[sub];
  },lookup);

});

console.log(glob);

It creates the same result but it is may much faster ( up to O(n) vs. O(n+n!)) http://jsbin.com/xumazinesa/edit?console