DEV Community

loading...
Cover image for JS: Recursion through a File Tree

JS: Recursion through a File Tree

Anthony Petrides
DevOps Engineer turned Developer who enjoys being hands-on with the full end-to-end of the development lifecycle.
・2 min read

In this post we’ll discuss recursion in JavaScript through means of the classic file tree example.

Imagine we have the following file tree structure:

{
 type: "folder",
 name: "project",
 content: [
    {
    type: "folder",
    name: "components",
    content: [
          {
        type: "folder",
        name: "helpers",
        content: [
                  {
            type: "file",
            name: "dates.js",
                  },
          ],
        },
        {
        type: "file",
        name: "Button.jsx",
        },
        {
        type: "file",
        name: "Button.css",
        },
      ],
    },
    {
    type: "file",
    name: "index.js",
    },
    {
    type: "file",
    name: "App.jsx",
    },
  ],
};
Enter fullscreen mode Exit fullscreen mode

Now what if we want to create a function that tells us if a specific file exists when we provide it the name of the file?

And what if we want this function to work no matter the depth of the tree?

And lastly, what if I told you that with recursion, we can achieve this in under 10 lines?

First of all, lets imagine our function call:

console.log(fileSearch(fileTree, "dates.js"));
Enter fullscreen mode Exit fullscreen mode

We’ll be creating a function called fileSearch and it will take 2 arguments:

  1. the file tree
  2. the filename we want to search for

We’ll expect a boolean true or false as the output.

Process to the solution

Looking at our file tree structure, we can see there are 2 types of objects. A folder type and a file type.

We know if the type is a file, we have a filename available to compare to the filename we’ll be passing in to our function to search for — a.k.a the ‘searchTerm’.

However, if the type is a folder, we know we have a content attribute which has an array of one or more objects, which again could hold further folder types or filename types. We simply don’t know how many of these there will be depth wise. This alone is an indication that we need to use recursion for a scalable solution.

The first thing we want to do is check, at the root level of the tree, if we have a file or a folder.

If we have a file, compare the filename with our searchTerm, else, in the case we have a folder, we need drop into the content array and again, check if we have a folder or a file.

We’ve already checked folder or file in the first step, so we can reuse this code here recursively by calling our own function again.

Focus on the solution below and see how we call fileSearch within itself:

const fileSearch = (tree, searchTerm) => {
 switch (tree.type) {
   case "file":
     return tree.name === searchTerm;

   case "folder":
     return !!tree.content.find((element) => fileSearch(element, searchTerm));

   default:
     return "File Not Found";
  }
};
Enter fullscreen mode Exit fullscreen mode

The simplicity of the above solution should in hope speak for itself given then steps we've followed to arrive here.

Discussion (0)

Forem Open with the Forem app