0 added
0 removed
Original
2026-01-01
Modified
2026-02-21
1
<p>A step-by-step search of tree elements by connections between ancestor nodes and descendant nodes is called<strong>tree traversal</strong>. 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.</p>
1
<p>A step-by-step search of tree elements by connections between ancestor nodes and descendant nodes is called<strong>tree traversal</strong>. 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.</p>
2
<p>This course will look at<strong>depth-first</strong>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.</p>
2
<p>This course will look at<strong>depth-first</strong>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.</p>
3
<h2>Depth-first search</h2>
3
<h2>Depth-first search</h2>
4
<p>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.</p>
4
<p>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.</p>
5
<p>Let's look at this algorithm using the following tree as an example.</p>
5
<p>Let's look at this algorithm using the following tree as an example.</p>
6
<p>Each non-leaf node is marked with an asterisk. The traversal begins at the root node.</p>
6
<p>Each non-leaf node is marked with an asterisk. The traversal begins at the root node.</p>
7
<ol><li>Check if node A has children. If true, run a recursive traversal for each child independently</li>
7
<ol><li>Check if node A has children. If true, run a recursive traversal for each child independently</li>
8
<li>The next subtree is inside the first recursive call:</li>
8
<li>The next subtree is inside the first recursive call:</li>
9
</ol><p>Repeat the logic of the first step. We fall to a lower level.</p>
9
</ol><p>Repeat the logic of the first step. We fall to a lower level.</p>
10
<ol><li>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</li>
10
<ol><li>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</li>
11
<li>Again we find ourselves in a situation:</li>
11
<li>Again we find ourselves in a situation:</li>
12
</ol><p>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.</p>
12
</ol><p>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.</p>
13
<p>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.</p>
13
<p>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.</p>
14
<p>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.</p>
14
<p>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.</p>
15
<p>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.</p>
15
<p>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.</p>
16
<p>Everything we do in this course will invariably be<strong>based on this algorithm</strong>. 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.</p>
16
<p>Everything we do in this course will invariably be<strong>based on this algorithm</strong>. 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.</p>