Recursive Directory Traversal Algorithms

In this lesson, you will learn how to navigate complex, nested directory structures using Depth-First Search (DFS) and Breadth-First Search (BFS) algorithms.

When we need to process every file within a folder tree, we face a classic computer science problem: how to visit every "node" (directory or file) in a hierarchy. In Node.js, we use the fs module to read directory contents, but the algorithm we choose dictates the order in which we encounter those files.

Depth-First Search (DFS)

DFS prioritizes going "deeper" into the tree before backtracking. Imagine exploring a house by walking to the very end of one hallway, entering a room, and then checking every closet in that room before moving to the next room in the hall.

In Node.js, this is naturally implemented using recursion:

const fs = require('fs/promises');
const path = require('path');

async function walkDFS(dir) {
  const entries = await fs.readdir(dir, { withFileTypes: true });
  for (const entry of entries) {
    const fullPath = path.join(dir, entry.name);
    if (entry.isDirectory()) {
      await walkDFS(fullPath); // Dive deeper
    } else {
      console.log('File:', fullPath);
    }
  }
}

Breadth-First Search (BFS)

BFS explores the tree level-by-level. It visits every folder in the current directory before diving into the sub-folders. This is like standing at the front door of a house and looking into every room on the ground floor before walking up the stairs to check the second floor.

To implement this, we use a queue structure instead of recursion:

async function walkBFS(dir) {
  let queue = [dir];
  while (queue.length > 0) {
    const currentDir = queue.shift();
    const entries = await fs.readdir(currentDir, { withFileTypes: true });
    
    for (const entry of entries) {
      const fullPath = path.join(currentDir, entry.name);
      if (entry.isDirectory()) {
        queue.push(fullPath); // Queue for later processing
      } else {
        console.log('File:', fullPath);
      }
    }
  }
}

DFS is generally more memory-efficient for very deep, sparse trees because it only keeps the current path in the stack. BFS is useful when you need to find files close to the root first or need to control the "breadth" of operations to avoid overloading the Event Loop.

Key Takeaway: Choose Depth-First Search for deep, narrow structures via recursion, and Breadth-First Search for shallow, wide structures using a queue to maintain control over the traversal order.