Обходы: в глубину и в ширину

Интуиция: два способа обойти дом

Представь, что ты осматриваешь большой дом с комнатами, коридорами и кладовками.

• В глубину (DFS): заходишь в первую дверь и идёшь до самой дальней кладовки. Потом возвращаешься на шаг назад и пробуешь следующую дверь. Так работает лабиринт с «правой рукой на стене».
• В ширину (BFS): сначала осматриваешь все комнаты первого этажа, потом все комнаты второго, потом третьего. Ты обходишь этаж за этажом.

С деревом всё так же. DFS ныряет вниз по ветке, а BFS идёт по уровням. Почти любая задача на деревья на собесе — один из этих двух обходов плюс немного логики сверху.

Наше дерево для примеров

Возьмём одно дерево и обойдём его всеми способами:

DFS: три порядка — одна рекурсия

У DFS есть три варианта. Они отличаются только одним: в какой момент ты «обрабатываешь» текущий узел — до детей, между ними или после.

Обход	Порядок	Результат для нашего дерева
Прямой (pre-order)	узел → левое → правое	4 2 1 3 6 5 7
Симметричный (in-order)	левое → узел → правое	1 2 3 4 5 6 7
Обратный (post-order)	левое → правое → узел	1 3 2 5 7 6 4

Как это запомнить: приставка показывает, где стоит узел. Pre — узел до детей, in — узел внутри, между детьми, post — узел после детей.

Посмотри на прямой обход. Мы начинаем с корня, ныряем влево и проходим всю левую ветку, прежде чем трогать правую:

Фишка симметричного обхода. В дереве поиска (BST) он выдаёт значения отсортированными: 1 2 3 4 5 6 7. На собесах этот факт спрашивают очень часто — запомни его.

Когда какой порядок нужен:

• Прямой — когда решение принимается сверху вниз. Например, нужно передать детям глубину или путь от корня, скопировать дерево или сериализовать его.
• Симметричный — для BST: k-й по величине элемент, проверка корректности дерева.
• Обратный — когда узлу нужны ответы от детей. Например, высота, диаметр, «сбалансировано ли». Сначала спрашиваем детей, потом считаем себя.

Шаблон DFS (рекурсия)

У шаблона три «окна». Код в первом окне даёт прямой обход, во втором — симметричный, в третьем — обратный. Здесь печать стоит в окне симметричного обхода:

def dfs(node):
    if node is None:          # базовый случай — пустое поддерево
        return
    # 1) здесь — прямой обход
    dfs(node.left)
    print(node.val)           # 2) здесь — симметричный обход
    dfs(node.right)
    # 3) здесь — обратный обход

Перенеси print в другое окно — и получишь другой порядок. Это и есть весь секрет трёх обходов.

BFS: по уровням через очередь

BFS держит очередь узлов, которые ждут своей очереди на обработку. Достаём узел из начала очереди, а его детей кладём в конец. Поэтому верхние уровни всегда обрабатываются раньше нижних.

Главный трюк для собеса: в начале каждого уровня запомни размер очереди. Ровно столько узлов и составляют текущий уровень.

Уровни нашего дерева: [4], [2, 6], [1, 3, 5, 7].

Шаблон BFS (очередь с размером уровня)

Для примера посчитаем, сколько узлов на каждом уровне. Для нашего дерева получится [1, 2, 4].

from collections import deque

def level_sizes(root):
    if root is None:
        return []
    res, q = [], deque([root])
    while q:
        size = len(q)             # столько узлов на текущем уровне
        for _ in range(size):
            node = q.popleft()
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        res.append(size)
    return res

Сложность

	Время	Память
DFS	O(n)	O(h) — стек рекурсии, h — высота дерева
BFS	O(n)	O(w) — самый широкий уровень, до n/2 узлов

Каждый узел посещается ровно один раз. Если дерево вырождено в «палку», h = n, и глубокая рекурсия может переполнить стек.

Когда что выбирать на собесе

• В задаче есть слова «уровень», «слой», «минимальная глубина», «вид справа», «зигзаг» → BFS.
• Ответ узла зависит от ответов детей (высота, диаметр, сумма пути) → DFS, обратный обход.
• Нужно передать что-то сверху вниз (путь, текущая глубина) → DFS, прямой обход.
• Дерево поиска и нужен порядок значений → DFS, симметричный обход.

Как это звучит вслух: «Обойду дерево в глубину рекурсией, высоту считаю на выходе из детей, то есть это post-order. Время O(n), память O(h) на стек». Одна такая фраза показывает интервьюеру, что ты понимаешь, что делаешь.

Частые ошибки

• Забыть базовый случай node == null в DFS — это сразу падение.
• Не проверить пустой root перед тем, как класть его в очередь BFS.
• Брать len(q) прямо в условии цикла по уровню. Очередь растёт, пока ты добавляешь детей, и уровни смешиваются. Размер нужно сохранить в переменную заранее.
• Использовать list.pop(0) в Python или shift() в JS. Это O(n) на операцию, и обход превращается в O(n²). Бери deque или собирай следующий уровень отдельным массивом.
• Путать порядки. Ориентируйся на то, где стоит узел: pre — до детей, in — между ними, post — после.

Два шаблона из этого урока закрывают большую часть задач на деревья. Дальше — практика, и ты увидишь, как они повторяются из задачи в задачу.