Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-21

1 A step-by-step search of tree elements by links between ancestor and descendant nodes istree traversal. We assume that each node will be affected only once during the crawl. By and large, everything is the same as in traversing any collection using a loop or recursion.

2 However, in the case of trees, there are more ways of traversing than just left to right and vice versa.

3 Depth-first traversalis the only traversal order we will use in this course because it naturally follows from recursive traversal. You can read about the rest of the methods in Wikipedia or the books recommended by Hexlet.

4 <h2>Depth-first search</h2>

5 It is one of the tree traversal methods. The strategy of this search is to go as deep into one subtree as possible. This algorithm naturally falls on a recursive solution and works itself out naturally:

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

7 We indicate each non-leaf node by an asterisk. The crawl starts from the root node:

8 <ol><li>Check if node A has children. If there is, then we run the traversal recursively for each child independently

9 </li>

10 <li>The next subtree is inside the first recursive call:

11 We repeat the logic of the first step and fall to the level below.

12 </li>

13 <li>There is a leaf element E inside. The function makes sure that the node has no child elements, performs the necessary work, and returns the result to the top

14 </li>

15 <li>We find ourselves in this situation again:

16 </li>

17 </ol>At this point, we launched a recursive call on each of the children. Since we have already visited the first child, the second recursive call goes to node F and does its job there. After that, it's returned to the top, and everything repeats until it reaches the root:

18 When we apply the dfs function to all children, we get atree recursion- multiple recursive calls within a single function call:

19 Printing to the screen in the example above is just a demonstration. In reality, we want to change the tree or aggregate data. We'll consider data aggregation later, but now we'll analyze the change. Let us say we want to implement a function that changes the owner for the entire tree with all directories and files. To do this, we will combine two things:

20 <ul><li>The recursion discussed above</li>

21 <li>The node update code that we studied in the last lesson</li>

22 </ul>Here is the code:

23 The key difference from the first example is that we form new nodes and return them outside here instead of printing to the screen. Eventually, we assemble a new tree from them. Everything we will do further during the course isbased on this algorithm. Try to open the editor on your computer and implement this function to be sure you understand what is happening.