A step-by-step search of tree elements by connections between ancestor nodes and descendant nodes is called **tree traversal**. It's assumed that each node will only be visited once during the traversal. Basically, it's the same as traversing any collection using a loop or recursion. Only for trees, there are more ways around than just left to right and right to left.

This course will look at **depth-first** traversal, the natural way to traverse a tree by depth. You can read about the other methods on Wikipedia or in recommended books from our list.

## Depth-first search

This is just one way to traverse a tree (or a graph in the general case). The strategy here is to go as deep into one subtree as possible; this algorithm is naturally based on a recursive solution and works itself out.

Let's look at this algorithm using the following tree as an example.

```
// * A
// / | \
// B * C * D
// /| |\
// E F G J
```

Each non-leaf node is marked with an asterisk. The traversal begins at the root node.

- Check if node A has children. If true, run a recursive traversal for each child independently
- The next subtree is inside the first recursive call:

```
// B *
// /|
// E F
```

Repeat the logic of the first step. We fall to a lower level.

- Inside we find leaf node
`E`

. The function makes sure that the node has no children, does the necessary work, and returns the result to the top - Again we find ourselves in a situation:

```
// B *
// /|
// E F
```

At this point, as we remember, a recursive call was run on each child. Since the first child has already been visited, the second recursive call goes to node `F`

and does its work there. Then it goes up one, and repeats until it reaches the root.

```
const tree = mkdir('/', [
mkdir('etc', [
mkfile('bashrc'),
mkfile('consul.cfg'),
]),
mkfile('hexletrc'),
mkdir('bin', [
mkfile('ls'),
mkfile('cat'),
]),
]);
const dfs = (tree) => {
// Print the contents of the node
console.log(getName(tree));
// If it is a file, we return control
if (isFile(tree)) {
return;
}
// Getting the children
const children = getChildren(tree);
// Apply the dfs function to all children
// Many recursive calls within a single function call
// is called tree recursion
children.forEach(dfs);
};
dfs(tree);
// => /
// => etc
// => bashrc
// => consul.cfg
// => hexletrc
// => bin
// => ls
// => cat
```

https://repl.it/@hexlet/js-trees-traversal-dfs-nodejs-en

The logging in the example above is just a demonstration. In reality, we're interested in either changing the tree or aggregating data on it. We'll look at data aggregation later, but now let's look at the change.

Suppose we want to implement a function that changes the owner for the whole tree, i.e., all directories and files. To do this, we have to combine two things: the recursion, which we looked at above, and the node updating we learned in the last lesson.

```
const changeOwner = (tree, owner) => {
const name = getName(tree);
const newMeta = _.cloneDeep(getMeta(tree));
newMeta.owner = owner;
if (isFile(tree)) {
// Return the updated file
return mkfile(name, newMeta);
}
const children = getChildren(tree);
// Key line
// Recursive call on each child
const newChildren = children.map((child) => changeOwner(child, owner));
const newTree = mkdir(name, newChildren, newMeta);
// Return the updated directory
return newTree;
};
// This function can be generalized as a map that works with trees
```

https://repl.it/@hexlet/js-trees-traversal-changeOwner-nodejs-en

The key difference from the first example is that instead of printing, new nodes are formed and returned outside. Eventually, a new tree is built from them.

Everything we do in this course will invariably be **based on this algorithm**. Try opening an editor on your computer and implementing this function yourself without peeking. That way you make sure you understand what's going on.

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

The Hexlet support team or other students will answer you.

- Article “How to Learn and Cope with Negative Thoughts“
- Article “Learning Traps“
- Article “Complex and simple programming tasks“

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