---
title: "Обход дерева: прямой, симметричный, обратный и по уровням, с кодом на Python"
url: https://algopath.pro/ru/blog/obkhod-dereva
language: ru
summary: "Какой обход для какой задачи, порядок на одном дереве, рекурсивный и итеративный код на Python, задачи про высоту, диаметр и Right Side View, типичные ошибки."
updated: 2026-10-29
---

# Обход дерева: прямой, симметричный, обратный и по уровням, с кодом на Python

**Короткий ответ.** Обход дерева это порядок, в котором посещаются узлы. Есть три обхода в глубину: прямой, симметричный, обратный. Они отличаются тем, когда посещается корень относительно детей. И один обход в ширину, по уровням через очередь. Все стоят O(n). Ниже таблица выбора, код на Python с рекурсией и без, разбор задач.

 

## Что такое обход дерева?

 

Двоичное дерево это узлы с левым и правым ребёнком. Обход посещает каждый узел ровно один раз. Разница только в порядке.

 

Прямой обход: корень, левое поддерево, правое. Симметричный: левое, корень, правое. Обратный: левое, правое, корень. Обход в ширину: уровень за уровнем.

 

Названия запоминаются по месту корня. Pre это до детей, in между, post после.

 

Все четыре обхода посещают n узлов и стоят O(n). Разница в памяти. Обходы в глубину держат стек размером с высоту дерева. Обход в ширину держит очередь размером с самый широкий уровень.

 

## Какой обход дерева для какой задачи?

 

| Обход | Порядок | Когда брать | Пример |
| --- | --- | --- | --- |
| Прямой (preorder) | Корень, левое, правое | Скопировать или сериализовать дерево | Serialize Binary Tree |
| Симметричный (inorder) | Левое, корень, правое | Дерево поиска в отсортированном порядке | Kth Smallest in BST |
| Обратный (postorder) | Левое, правое, корень | Ответ для узла из ответов детей | Высота, диаметр, удаление |
| В ширину (level order) | По уровням | Всё про уровни и расстояние от корня | Level Order, Right Side View |

 

Правило простое. Нужны дети раньше родителя, берите обратный. Нужны уровни, берите ширину. Остальное чаще всего прямой.

 

## Как это выглядит на примере?

 

Дерево: корень 1, слева 2, справа 3. У 2 дети 4 и 5.

 

Прямой: 1, 2, 4, 5, 3. Симметричный: 4, 2, 5, 1, 3. Обратный: 4, 5, 2, 3, 1. В ширину: 1, 2, 3, 4, 5.

 

Обратите внимание на симметричный обход. Корень 1 стоит между левым поддеревом и правым. Именно поэтому он выдаёт дерево поиска по возрастанию.

 

## Как написать обход дерева на Python?

 

```
from collections import deque

def inorder(root):
    return inorder(root.left) + [root.val] + inorder(root.right) if root else []

def preorder_iter(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right: stack.append(node.right)   # правый первым в стек
        if node.left: stack.append(node.left)     # чтобы левый вышел раньше
    return out

def inorder_iter(root):
    out, stack, node = [], [], root
    while stack or node:
        while node:                      # спускаемся влево до упора
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out

def level_order(root):
    out, queue = [], deque([root] if root else [])
    while queue:
        level = []
        for _ in range(len(queue)):      # ровно один уровень
            node = queue.popleft()
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        out.append(level)
    return out
```

 

Рекурсивный вариант короче. Итеративный нужен для глубоких деревьев. Рекурсия Python упрётся в лимит около тысячи.

 

## По каким словам в задаче узнать обход дерева?

 

- «Вывести значения по уровням», «правый вид дерева».
- «k-й наименьший элемент в дереве поиска».
- «Высота», «диаметр», «сбалансировано ли».
- «Восстановить дерево по двум обходам».

 

Почти любая задача на дерево это обход плюс работа в узле. Сначала выберите обход, потом думайте, что делать в узле.

 

## Как решить задачу про высоту и диаметр?

 

Высота узла это один плюс максимум высот детей. Это обратный обход: сначала дети, потом узел.

 

Диаметр это самый длинный путь между двумя узлами. В каждом узле он равен сумме высот левого и правого поддерева. Считаем высоту рекурсивно и по пути обновляем глобальный максимум. Один проход, O(n).

 

## Как обход в ширину даёт Right Side View?

 

Нужны узлы, видимые справа: последний узел каждого уровня. Обходим по уровням, из каждого уровня берём последний элемент. Всё решение это level_order плюс одна строка.

 

## Как симметричный обход даёт k-й наименьший в дереве поиска?

 

В дереве поиска слева меньше, справа больше. Симметричный обход выдаёт значения по возрастанию. Запускаем итеративный вариант со стеком и считаем снятые узлы. Сняли k-й, это и есть ответ. Останавливаемся сразу, весь обход не нужен.

 

Время O(h + k), где h это высота. Для маленького k это гораздо меньше O(n).

 

## Как проверить, что дерево симметрично?

 

Дерево симметрично, если левое поддерево зеркально правому. Идём двумя указателями: левый ребёнок одного и правый ребёнок другого. Значения совпали, спускаемся дальше крест-накрест. Это обход двух деревьев одновременно, O(n).

 

## На каких ошибках ломается обход дерева?

 

- В итеративном прямом обходе кладут в стек сначала левого ребёнка. Порядок переворачивается.
- В обходе в ширину не фиксируют размер уровня и смешивают уровни.
- Забывают проверить пустое дерево и обращаются к root.left.
- Берут рекурсию на дереве в миллион узлов, вытянутом в цепочку.

 

## Как объяснить приём на собеседовании?

 

Назовите обход и почему именно он. Скажите O(n) по времени и O(h) по памяти, где h это высота. Для обхода в ширину память O(w), где w это ширина уровня.

 

Спросят про итеративный вариант, напишите симметричный со стеком. Это самый частый из трёх.

 

Отработать узнавание приёма можно на странице [обход дерева](/ru/patterns/tree-traversal). Соседний приём разобран на странице [двоичное дерево поиска](/ru/patterns/bst).

 

## Вопросы и ответы

 

### Как восстановить дерево по прямому и симметричному обходу?

 

Первый элемент прямого обхода это корень. Найдите его в симметричном. Всё левее это левое поддерево, правее это правое. Повторите для каждой части.

 

### Можно ли обойти дерево без стека и рекурсии?

 

Да, обход Морриса. Он временно перевязывает указатели и работает за O(1) памяти. На собеседовании его просят редко.

 

### Чем обход дерева отличается от обхода графа?

 

В дереве нет циклов, поэтому не нужен набор посещённых. В остальном это тот же DFS и BFS.

 

### Где обход дерева встречается в реальных системах?

 

В компиляторах: синтаксическое дерево обходят обратным обходом, чтобы вычислить выражение. В файловых системах: размер папки это обратный обход. В отрисовке интерфейсов: дерево компонентов обходят прямым.