Register to get access to free programming courses with interactive exercises

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.

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:

Depth-first Search

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 *
    

Sign up

Programming courses for beginners and experienced developers. Start training for free

  • 130 courses, 2000+ hours of theory
  • 1000 practical tasks in a browser
  • 360 000 students
By sending this form, you agree to our Personal Policy and Service Conditions

Our graduates work in companies:

<span class="translation_missing" title="translation missing: en.web.courses.lessons.registration.bookmate">Bookmate</span>
<span class="translation_missing" title="translation missing: en.web.courses.lessons.registration.healthsamurai">Healthsamurai</span>
<span class="translation_missing" title="translation missing: en.web.courses.lessons.registration.dualboot">Dualboot</span>
<span class="translation_missing" title="translation missing: en.web.courses.lessons.registration.abbyy">Abbyy</span>
Suggested learning programs
profession
new
Developing web applications with Django
10 months
from scratch
under development
Start at any time

Use Hexlet to the fullest extent!

  • Ask questions about the lesson
  • Test your knowledge in quizzes
  • Practice in your browser
  • Track your progress

Sign up or sign in

By sending this form, you agree to our Personal Policy and Service Conditions
Toto Image

Ask questions if you want to discuss a theory or an exercise. Hexlet Support Team and experienced community members can help find answers and solve a problem.