Accumulator — JS: Trees

In some situations, we need additional information while traversing the tree, depending on the node location. It can't be obtained from the node definition itself – this information should be accumulated directly during the traversal.

This information includes, among other things, the full path to the file or the depth of the current node. The node itself doesn't actually know where it's located. The file location in the file structure is determined by the nodes that lead to the specific file.

In this lesson, we'll get to know the concept of accumulator, a special parameter that collects the necessary data while traversing the tree. It makes the code more complicated but allows one to handle more tricky tasks.

Let's take the following task: we want to find all empty directories in our file system. First, we'll implement a basic solution, and then we'll complicate it and introduce an accumulator. Below is an example of a file system:

const tree = mkdir('/', [
  mkdir('etc', [
    mkdir('apache'),
    mkdir('nginx', [
      mkfile('nginx.conf'),
    ]),
    mkdir('consul', [
      mkfile('config.json'),
      mkdir('data'),
    ]),
  ]),
  mkdir('logs'),
  mkfile('hosts'),
]);

There are three empty directories in this structure: /logs, /etc/apache and /etc/consul/data. The code that does this task looks like this:

const findEmptyDirPaths = (tree) => {
  const name = getName(tree);
  const children = getChildren(tree);
  // If there are no children, we add a directory
  if (children.length === 0) {
    return name;
  }

  // Filter the files, we don't need them
  const emptyDirNames = children.filter((child) => !isFile(child))
    // Search for empty directories inside the current one
    // flatMap flattens the array
    .flatMap(findEmptyDirPaths);

  return emptyDirNames;
};

findEmptyDirPaths(tree); // ['apache', 'data', 'logs']

https://repl.it/@hexlet/js-trees-search-findEmptyDirs-nodejs

The most unusual thing about this implementation is the flatMap() function. What is it for? If you leave only map(), the result may be surprising:

findEmptyDirPaths(tree);

// [ [ 'apache', [], [ 'data' ] ], 'logs' ]

This happens because an array is returned at each nesting level. The output is an array of arrays, similar in structure to the original file tree. To avoid this, you need to fix the code with flat() or use flatMap() straight away.

Let's try to make it more difficult. Find all empty directories, but with a maximum search depth of 2 levels. Basically, /logs and /etc/apache fit this condition, but /etc/consul/data — does not.

To begin with, you need to understand where to get the depth from. With trees, depth is counted as the number of edges from the root to the desired node. It's easy to calculate visually, but what about the code? The depth of a particular node can be represented as the depth of the previous node plus one.

The next step is to add a variable that is passed in each recursive call (falling into the directory). In our task, this value contains the current depth. I.e., at each level (within each directory) one is added to it. This variable is called accumulator because it accumulates data.

The only problem is that the original findEmptyDirPaths() function has exactly one parameter: the node. It can't save information about the current depth level for all nested directories and files. Therefore, we have to introduce an internal function that will be able to pass the accumulator further down the tree:

const findEmptyDirPaths = (tree) => {
  // An internal function that can pass the accumulator
  // The accumulator is a variable that contains the current depth, and it's called, for obvious reasons, depth
  const iter = (node, depth) => {
    const name = getName(node);
    const children = getChildren(node);

    // If the directory is empty, add it to the list
    if (children.length === 0) {
      return name;
    }

    // If this is the second nesting level, and the directory isn't empty
    // it makes no sense to look any further
    if (depth === 2) {
      // Why does it return an empty array?
      // Because flat is executed outside
      // It expands empty arrays
      return [];
    }

    // Leave only the directories
    return children.filter(isDirectory)
      // Don't forget to increase the depth
      .flatMap((child) => iter(child, depth + 1));

  };

  // We start with zero depth level
  return iter(tree, 0);
};

findEmptyDirPaths(tree); // ['apache', 'logs']

https://repl.it/@hexlet/js-trees-accumulator-findEmptyDirsWithDepth-en

You can go even further and allow the maximum depth to be specified outside:

const findEmptyDirPaths = (tree, maxDepth = 2) => {
  // ...
}

But one question arises, how do we make it so that by default, the entire tree is viewed? For example, you can take a clearly large number and make it the default value. This approach will work, but it's a bit of a hack job. The proper way to do this is to use Infinity as the default value:

const findEmptyDirPaths = (tree, maxDepth = Infinity) => {
  // ...
}

Recommended materials

1. Parameters for internal needs