Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-21

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

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

3 In this lesson, we'll get to know the concept ofaccumulator, 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.

4 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:

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

6 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:

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

8 Let's try to make it more difficult. Find all empty directories, but with a maximum search depth of 2 levels. Basically,/logsand/etc/apachefit this condition, but/etc/consul/data- does not.

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

10 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 calledaccumulatorbecause itaccumulatesdata.

11 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:

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

13 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 useInfinityas the default value: