Today I am continuing on with my review of a book on programming algorithms. The book, “Grokking Algorithms, Second Edition” by Aditya Bhargava, is well worth a read if you haven’t studied algorithms or if you would like a refresher. In Part 4 and Part 4B, I covered Breadth First Search. In Part 5, I would like to discuss Depth First Search (DFS).

Breadth First Search (BFS) is useful for finding the shortest path in a graph. In the example code I wrote, it shows the means of finding the nearest mango seller among a person’s group of friends. This is the example used by the author of the book, with code written in Python rather than JavaScript as in my example. DFS, rather than working outward from the first node to all adjacent nodes, recurses down the path of the first adjacent node and finds all child nodes of that first node before checking the next adjacent node.

A typical use of DFS is to search through a nested directory file system. Let’s say you are trying to find a file by name somewhere in your Documents folder. You could use DFS to recurse through this nested folder structure and find the file you are looking for. Let’s look at some code.

import * as fs from 'fs'
import * as path from 'path'

const basepath = '/home/robert/Documents/'
async function readFolder(thePath) {
    const folder = { path: thePath, childFolders: [], files: [] }
    const files = await fs.promises.readdir(thePath)

    for (const file of files) {
        const fullPath = path.join(thePath, file)
        const stats = await fs.promises.stat(fullPath)

        if (stats.isDirectory() && file !== '.' && file !== '..') {
            folder.childFolders.push(await readFolder(fullPath))
        } else {
            folder.files.push(file)
        }
    }
    return folder
}

// Usage:
readFolder(basepath)
    .then((myfolders) => console.dir(myfolders))
    .catch(console.error)

This code rolls through a user’s Documents folder and makes an array of folder objects in the root folder, with an array of the files in each folder inside the folder object. It doesn’t actually do any searching for specific information, but this code can be easily extended to search for a pattern in files, folders, or both and perform some action on any matches.

In Part 6 of this series, I will start talking about trees.