javascriptalgorithmdata-structuresarray-algorithms

Convert array of paths into a Tree in JavaScript


Given this input:

const paths = ["src", "src/components", "src/components/index.ts", "src/utils", "src/configuration/config.ts", "another/file.ts"];

I need to create a function or a data structure that returns a Tree with the following structure.

[
      {
            "id": "src",
            "level": 1,
            "childrens": [
                  {
                        "id": "src/components",
                        "level": 2,
                        "childrens": [
                              {
                                    "id": "src/components/index.ts",
                                    "level": 3,
                                    "childrens": []
                              }
                        ]
                  },
                  {
                        "id": "src/utils",
                        "level": 2,
                        "childrens": []
                  },
                  {
                        "id": "src/configuration",
                        "level": 2,
                        "childrens": [
                              {
                                    "id": "src/configuration/config.ts",
                                    "level": 3,
                                    "childrens": []
                              }
                        ]
                  }
            ]
      },
      {
            "id": "another",
            "level": 1,
            "childrens": [
                  {
                        "id": "another/file.ts",
                        "level": 2,
                        "childrens": []
                  }
            ]
      }
]

I tried everything but I can't make it work, so if anyone can help I would appreciate it a lot.

Thank you.


Solution

  • First, here's the solution based on this answer: https://stackoverflow.com/a/57344801/3807365. Explanation below.

    const paths = ["src", "src/components", "src/components/index.ts", "src/utils", "src/configuration/config.ts", "another/file.ts"];
    
    let agg = {
      temp: []
    };
    
    paths.forEach(path => {
      path.split('/').reduce((agg, part, level, parts) => {
        if (!agg[part]) {
          agg[part] = {
            temp: []
          };
          agg.temp.push({
            id: parts.slice(0, level + 1).join("/"),
            level: level + 1,
            children: agg[part].temp
          })
          // console.log(agg)
        }
        return agg[part];
      }, agg)
    })
    
    var result = agg.temp;
    console.log(result)
    .as-console-wrapper {
      max-height: 100% !important;
    }

    Explanation:

    Given a path (splitted to parts) and the result which is an empty array [] we are building this kind of object (helper object!):

    {
      "src" : {
        "utils" : {
          "file.ts" : {}
        }, 
        "components" : {
          "file.ts" : {}
        }
      },
      "another": {
        "file.ts" : {}
      }
    }
    

    We do this step by step as we go on each part of the path. And we do this to each path building this lovely tree. Simple enough.

    But as we do, we are creating arrays in the result object (which is under property temp) - arrays of items of the same level in the format {id, level, children}. Finally, we ignore this entire helper tree and only return the first level array - which is the result (under property temp).

    Once you realize this, you can see the possible error in this method. Can you spot it? What kind of path name will "mess" with the result?