DEV Community

Delightful Engineering
Delightful Engineering

Posted on • Originally published at delightfulengineering.com

Node JS File Directory Search Algorithm

In this post we're going to write a file system search algorithm in Typescript for Node-based programs with the following criteria:

  • A file tree of any size.
  • A given directory name to search for passed as an argument.
  • Always start the search from process.cwd() by default.
  • Return the first found occurence.
  • Return value should be an array with strings of the path to the found directory or empty array if not found.

Get started

First thing to do is to initialize a new Node JS project. For this we will use the Yarn package manager.

yarn init

# You can go ahead and just press enter through each option.
Enter fullscreen mode Exit fullscreen mode

Next thing to do is add a few development dependencies so that we can run our program.

yarn add -D @types/node ts-node typescript
Enter fullscreen mode Exit fullscreen mode

We can also go ahead and add a script to our package.json that we will use to run the program.

{
  "name": "file-tree-search",
  "scripts": {
    "fts": "ts-node src/index.ts"
  },
  "devDependencies": {
    "@types/node": "^18.7.16",
    "ts-node": "^10.9.1",
    "typescript": "^4.8.3"
  },
  "license": "MIT"
}
Enter fullscreen mode Exit fullscreen mode

Next we'll create a src directory and some files for our program, and also a test directory will some directories and empty files that we can test as a file tree in our search algorithm.

# Create directories
mkdir src test test/hello test/world
Enter fullscreen mode Exit fullscreen mode
# Create files
touch src/index.ts src/search.ts test/random.txt test/hello/another.txt test/world/pizza.txt
Enter fullscreen mode Exit fullscreen mode

Create the search algorithm

Now we can write our search algorithm in search.ts.

import { readdirSync, statSync } from "fs";
import { join } from "path";

export const findDirectory = (
  searchName: string,
  startDirectory = [process.cwd()]
): string => {
  const scanStartDir = readdirSync(join(...startDirectory));
  const filteredScan = scanStartDir.filter((dir) =>
    isDir(join(...[...startDirectory, dir]))
  );
  if (filteredScan.includes(searchName)) {
    return join(...[...startDirectory, searchName]);
  } else if (filteredScan.length === 0) {
    return "";
  } else {
    let subScanFound = "";
    filteredScan.every((dir) => {
      const result = findDirectory(searchName, [...startDirectory, dir]);
      if (result.length > 0) {
        subScanFound = result;
        return false;
      }
      return true;
    });
    return subScanFound;
  }
};

const isDir = (path: string): boolean => {
  try {
    return statSync(path).isDirectory();
  } catch (e) {
    return false;
  }
};
Enter fullscreen mode Exit fullscreen mode

Search algorithm explained

First we need functions provided by the standard Node library to interact with the file system. We'll import readdirSync to retrieve which files belong to a directory and statSync to get information about an individual file. When working with file systems, the "path" library provides an operating system agnostic way to deal with file paths. Paths are different on Windows vs. MacOS for example so we want our program to work with an type of file path structure. For joining strings together to create a path we will also import join from "path".

The two arguments to our findDirectory search function are:

  • searchName: a string of a directory name to search for.
  • startDirectory: a directory to start the search from which will go down the tree, we pass [process.cwd()] as the default will get the current working directory of the running Node process. The user can pass something else if they want (maybe searching from __dirname is useful for the user of our function). We're representing this as an array of strings so that we can later use to construct paths.

The first thing we want to do is read the files in the passed startDirectory and then filter those results to remove basic files from the results. Since we're searching for a directory, this is how we're narrowing the results down to exclude files.

const scanStartDir = readdirSync(join(...startDirectory))
const filteredScan = scanStartDir.filter((dir) => isDir(join(...[...startDirectory, dir])))
Enter fullscreen mode Exit fullscreen mode

To keep the filter simple, we create an abstract isDir function. This function simply takes a path argument and returns a boolean for whether an individual file is a directory or not. The Node standard library has a handy statSync for getting information about files. We use it's isDirectory() function which returns true or false.

With our filtered results we can now start evaluating conditions. Our findDirectory function is written recursively which means it calls itself internally to solve subsets of the original problem.

Our first condition is the base case which is that we found the directory that we were search for so we can stop searching.

if (filteredScan.includes(searchName)) {
  return join(...[...startDirectory, searchName])
}
Enter fullscreen mode Exit fullscreen mode

We also have secondary base case which is that the current directory that we are searching does not contain any directories so we can stop searching.

else if (filteredScan.length === 0) {
  return "";
}
Enter fullscreen mode Exit fullscreen mode

Apart from the conditions that should stop our search, or in other terms our base cases, we need to continue searching all of the directories in our filtered search results. Here is where the recursion happens.

else {
  let subScanFound = "";
  filteredScan.every((dir) => {
    const result = findDirectory(searchName, [...startDirectory, dir]);
    if (result.length > 0) {
      subScanFound = result;
      return false;
    }
    return true;
  });
  return subScanFound;
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)