Node JS File Directory Search Algorithm
Tags: javascript, tutorial, node, typescript
Published: 2022-09-11 00:57:51

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.

```bash
yarn init

# You can go ahead and just press enter through each option.
```

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

```bash
yarn add -D @types/node ts-node typescript
```

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

```json
{
  "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"
}
```

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.

```bash
# Create directories
mkdir src test test/hello test/world
```

```bash
# Create files
touch src/index.ts src/search.ts test/random.txt test/hello/another.txt test/world/pizza.txt
```

### Create the search algorithm

Now we can write our search algorithm in _search.ts_.

```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;
  }
};
```

#### 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.

```ts
const scanStartDir = readdirSync(join(...startDirectory))
const filteredScan = scanStartDir.filter((dir) => isDir(join(...[...startDirectory, dir])))
```

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.

```ts
if (filteredScan.includes(searchName)) {
  return join(...[...startDirectory, searchName])
}
```

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.

```ts
else if (filteredScan.length === 0) {
  return "";
}
```

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.

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