Register to get access to free programming courses with interactive exercises

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']

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) => {
  // ...
}

Hexlet Experts

Are there any more questions? Ask them in the Discussion section.

The Hexlet support team or other students will answer you.

About Hexlet learning process

For full access to the course you need a professional subscription.

A professional subscription will give you full access to all Hexlet courses, projects and lifetime access to the theory of lessons learned. You can cancel your subscription at any time.

Get access
130
courses
1000
exercises
2000+
hours of theory
3200
tests

Sign up

Programming courses for beginners and experienced developers. Start training for free

  • 130 courses, 2000+ hours of theory
  • 1000 practical tasks in a browser
  • 360 000 students
By sending this form, you agree to our Personal Policy and Service Conditions

Our graduates work in companies:

<span class="translation_missing" title="translation missing: en.web.courses.lessons.registration.bookmate">Bookmate</span>
<span class="translation_missing" title="translation missing: en.web.courses.lessons.registration.healthsamurai">Healthsamurai</span>
<span class="translation_missing" title="translation missing: en.web.courses.lessons.registration.dualboot">Dualboot</span>
<span class="translation_missing" title="translation missing: en.web.courses.lessons.registration.abbyy">Abbyy</span>
Suggested learning programs

From a novice to a developer. Get a job or your money back!

Frontend Developer icon
Profession
beginner
Development of front-end components for web applications
start anytime 10 months

Use Hexlet to the fullest extent!

  • Ask questions about the lesson
  • Test your knowledge in quizzes
  • Practice in your browser
  • Track your progress

Sign up or sign in

By sending this form, you agree to our Personal Policy and Service Conditions

Toto Image

Ask questions if you want to discuss a theory or an exercise. Hexlet Support Team and experienced community members can help find answers and solve a problem.