transform file/directory structure into 'tree' in javascript

Question

I have an array of objects that looks like this:

[{ name: 'test',
  size: 0,
  type: 'directory',
  path: '/storage/test' },
{ name: 'asdf',
  size: 170,
  type: 'directory',
  path: '/storage/test/asdf' },
{ name: '2.txt',
  size: 0,
  type: 'file',
  path: '/storage/test/asdf/2.txt' }]

There could be any number of arbitrary path's, this is the result of iterating through files and folders within a directory.

What I'm trying to do is determine the 'root' node of these. Ultimately, this will be stored in mongodb and use materialized path to determine it's relationships.

In this example, /storage/test is a root with no parent. /storage/test/asdf has the parent of /storage/test which is the parent to /storage/test/asdf/2.txt.

My question is, how would you go about iterating through this array, to determine the parent's and associated children? Any help in the right direction would be great!

Thank you

Are you looking for something that'll actually give you a directory tree like structure, where /storage/test belongs to the implied node /storage which in turn would belong to the implied root /? Not entirely sure what kind of data structure you want to end up with. — Marcus Stade
– Marcus Stade, Commented Oct 23, 2013 at 2:16
To clarify my comment, what if you have a file at /storage/test and one at /storage/text/asdf/2.txt then /storage/text/asdf would have to be implied unless parent could also mean grandparent. — Marcus Stade
– Marcus Stade, Commented Oct 23, 2013 at 2:18
Well, I would want to basically have nested children, so a json object that represented the same as a 'folder tree', if that makes sense. I guess I would have to recursively iterate through it in order to save. — dzm
– dzm, Commented Oct 23, 2013 at 2:22

user568109 · Accepted Answer · 2013-10-23 04:06:40Z

You can do it like this:

var arr = [] //your array;
var tree = {};

function addnode(obj){
  var splitpath = obj.path.replace(/^\/|\/$/g, "").split('/');
  var ptr = tree;
  for (i=0;i<splitpath.length;i++)
  {
    node = { name: splitpath[i],
    type: 'directory'};
    if(i == splitpath.length-1)
    {node.size = obj.size;node.type = obj.type;}
    ptr[splitpath[i]] = ptr[splitpath[i]]||node;
    ptr[splitpath[i]].children=ptr[splitpath[i]].children||{};
    ptr=ptr[splitpath[i]].children;
  }    
}

arr.map(addnode);
console.log(require('util').inspect(tree, {depth:null}));

Output

{ storage:
   { name: 'storage',
     type: 'directory',
     children:
      { test:
         { name: 'test',
           type: 'directory',
           size: 0,
           children:
            { asdf:
               { name: 'asdf',
                 type: 'directory',
                 size: 170,
                 children: { '2.txt': { name: '2.txt', type: 'file', size: 0, children: {} } } } } } } } }

Marcus Stade · Accepted Answer · 2013-10-23 03:50:18Z

3

Assuming / will never show up in the list of files, something like this should work:

function treeify(files) {
  var path = require('path')

  files = files.reduce(function(tree, f) {
    var dir = path.dirname(f.path)

    if (tree[dir]) {
      tree[dir].children.push(f)
    } else {
      tree[dir] = { implied: true, children: [f] }
    }

    if (tree[f.path]) {
      f.children = tree[f.path].children
    } else {
      f.children = []
    }

    return (tree[f.path] = f), tree
  }, {})

  return Object.keys(files).reduce(function(tree, f) {
    if (files[f].implied) {
      return tree.concat(files[f].children)
    }

    return tree
  }, [])
}

It'll turn the array you mention in the question in to something like this:

[ { name: 'test',
    size: 0,
    type: 'directory',
    path: '/storage/test',
    children: 
     [ { name: 'asdf',
         size: 170,
         type: 'directory',
         path: '/storage/test/asdf',
         children: 
          [ { name: '2.txt',
              size: 0,
              type: 'file',
              path: '/storage/test/asdf/2.txt',
              children: [] } ] } ] } ]

I haven't actually tested this with any other data sources, so your milage may vary but at least it ought to nudge you in the right direction.

answered Oct 23, 2013 at 3:50

Marcus Stade

5,0544 gold badges35 silver badges54 bronze badges

2 Comments

Todd Horst Over a year ago

This works, but could you add some comments to your code, I'm having issue understanding all of it. Specifically, after the first reduce, there is a implied object in addition to all the others, then you throw everything else away with the second reduce. Couldn't that be done in the first?

huan feng Over a year ago

It missing the first level directory 'storage'.

cancerbero · Accepted Answer · 2018-06-24 18:29:43Z

Solution based on @user568109 but returning results in arrays instead of objects:

function filesToTreeNodes(arr) {
  var tree = {}
  function addnode(obj) {
    var splitpath = obj.fileName.replace(/^\/|\/$/g, "").split('/');
    var ptr = tree;
    for (let i = 0; i < splitpath.length; i++) {
      let node: any = {
        fileName: splitpath[i],
        isDirectory: true
      };
      if (i == splitpath.length - 1) {
        node.isDirectory = false
      }
      ptr[splitpath[i]] = ptr[splitpath[i]] || node;
      ptr[splitpath[i]].children = ptr[splitpath[i]].children || {};
      ptr = ptr[splitpath[i]].children;
    }
  }
  function objectToArr(node) {
    Object.keys(node || {}).map((k) => {
      if (node[k].children) {
        objectToArr(node[k])
      }
    })
    if (node.children) {
      node.children = Object.values(node.children)
      node.children.forEach(objectToArr)
    }
  }
  arr.map(addnode);
  objectToArr(tree)
  return Object.values(tree)
}

This is the signature to better understand the input / output formats:

export interface TreeNode {
  isDirectory: string
  children: TreeNode[]
  fileName: string
}
export interface File {
  fileName: string
}
export type fileToTreeNodeType = (files: File[]) => TreeNode[]

Collectives™ on Stack Overflow

transform file/directory structure into 'tree' in javascript

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related