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.

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

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"
}

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

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

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.

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.

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.

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.

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

On our filteredScan filtered results, we can use the every function which unlike javascript's forEach can be broken at any point in it's execution. Now every directory and every directory's directories will be searched and so on until either a match is found or we reach the end of the file tree and ther are no more directories to be searched.

Create the program entry point

With our search algorithm we can create a main entry point to our program in index.ts so that it can be run from the command line and can access an argument for a directory to be searched.

#!/usr/bin/env ts-node
import { findDirectory } from "./search";

const main = (): void => {
  const searchResult = findDirectory(process.argv[2] ?? "world");
  if (searchResult.length > 0) {
    console.log("FOUND DIRECTORY!");
  } else {
    console.log("DIRECTORY NOT FOUND!");
  }
  console.log("SEARCH RESULT: ", searchResult);
};

main();

Run the program

yarn fts hello

# Expected output

$ ts-node src/index.ts hello
FOUND DIRECTORY!
SEARCH RESULT:  /Users/austinhoward/code/file-tree-search/test/hello

yarn fts non-existent-dir

# Expected output

$ ts-node src/index.ts non-existent-dir
DIRECTORY NOT FOUND!
SEARCH RESULT: