Traversal — Python: Trees

A step-by-step search of tree elements by links between ancestor and descendant nodes is tree 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.

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

Depth-first traversal is 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.

Depth-first search

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:

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

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

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

1. Check if node A has children. If there is, then we run the traversal recursively for each child independently

2. The next subtree is inside the first recursive call:

   # B *
   #  /|
   # E F
   

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

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

4. We find ourselves in this situation again:

   # B *