Обход дерева: прямой, симметричный, обратный и по уровням, с кодом на 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 это ширина уровня.

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

Отработать узнавание приёма можно на странице обход дерева. Соседний приём разобран на странице двоичное дерево поиска.

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

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

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

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

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

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

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

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

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