Итеративный обход бинарного дерева без рекурсии

Зачем вам итеративный обход дерева?

Вы готовитесь к собеседованию на senior-инженера, и интервьюер задаёт, казалось бы, безобидный вопрос: «Выполните inorder обход бинарного дерева без рекурсии». В голове мгновенно всплывает элегантное рекурсивное решение, которое вы писали десятки раз, но доска требует итеративную версию. Вы чувствуете себя как Люк Скайуокер в бою со Звездой Смерти — знаете, что Сила (рекурсия) сильна, но нужно положиться на собственные навыки пилотирования (явный стек).

Почему это важно? Потому что интервьюеры любят проверять, понимаете ли вы почему работает техника, а не просто запомнили шаблон. Рекурсивные обходы элегантны, но скрывают цену: каждый вызов добавляет фрейм в стек вызовов. В вырожденном дереве (представьте связный список, замаскированный под дерево) глубина может достигать O(n) и вызвать переполнение стека. Итеративный подход даёт вам контроль над стеком, позволяя безопасно обрабатывать деревья произвольной глубины.

Суть метода: стек вместо рекурсии

Inorder обход посещает узлы в порядке: левое поддерево → узел → правое поддерево. Рекурсивно это три шага: обойти левое, посетить узел, обойти правое. Чтобы превратить это в итеративный алгоритм, мы имитируем стек вызовов с помощью собственного стека.

Начинаем с корня и идём влево, помещая узлы в стек, пока возможно. Когда левый потомок отсутствует, извлекаем верхний узел — это следующий узел для посещения (всё левее уже обработано). После посещения переключаемся на его правого потомка и повторяем цикл. Цикл завершается, когда стек пуст и текущий указатель равен null.

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

Код: от рекурсии к итерации

Рекурсивный базовый вариант

def inorder_recursive(root):
    if root is None:
        return
    inorder_recursive(root.left)
    print(root.val, end=' ')
    inorder_recursive(root.right)

Этот код отлично работает для сбалансированных деревьев, но если дерево представляет собой прямую линию (все узлы имеют только правого потомка), глубина рекурсии равна n. На машине с ограниченным стеком дерево из 10⁵ узлов вызовет переполнение стека.

Итеративное решение с явным стеком

def inorder_iterative(root):
    stack = []
    curr = root
    while curr is not None or stack:
        # Идём максимально влево, сохраняя предков
        while curr is not None:
            stack.append(curr)
            curr = curr.left
        # curr равен None, извлекаем следующий узел
        curr = stack.pop()
        print(curr.val, end=' ')
        # Переходим к правому поддереву
        curr = curr.right

Время работы O(n), память O(h), где h — высота дерева (в худшем случае O(n) для вырожденного, в лучшем O(log n) для сбалансированного).

На что обратить внимание

• Не забыть обновить curr после извлечения — если оставить curr как извлечённый узел, внутренний цикл будет бесконечно добавлять тот же узел.
• Использовать список как стек — в Python список с методами append и pop работает как стек.

Задачи для собеседований

Inorder обход бинарного дерева (LeetCode 94)

Классика. Итеративное решение выше — ожидаемый ответ, когда интервьюер запрещает рекурсию.

K-й наименьший элемент в BST (LeetCode 230)

Можно использовать тот же цикл, добавив счётчик. Когда счётчик достигает k, вернуть значение узла. Дополнительная память только для стека.

Обе задачи работают за O(n), так как каждый узел помещается и извлекается ровно один раз.

Почему это важно

Освоение паттерна «явный стек» помогает не только на собеседованиях — это инструмент для любых ситуаций, где рекурсия рискует переполнить стек: разбор вложенных выражений, обход файловых каталогов, реализация собственного undo/redo. Вы начнёте видеть стек вызовов как ещё одну структуру данных, которой можно управлять, — это невероятно расширяет кругозор.

К тому же вы произведёте впечатление на интервьюера, показав, что понимаете компромиссы: читаемость против безопасности, и сможете объяснить, почему выбрали один подход вместо другого.

Ваш ход

Возьмите бинарное дерево (нарисуйте на бумаге или сгенерируйте) и вручную пройдите итеративный алгоритм для нескольких узлов. Затем запрограммируйте его на Python и протестируйте на вырожденном дереве из 10⁵ узлов — убедитесь, что оно работает без переполнения стека.

Если чувствуете азарт, модифицируйте цикл, чтобы собирать узлы в список и возвращать k-й элемент без дополнительных обходов.

Какие ещё рекурсивные паттерны обхода деревьев вы превратили в итеративные? Поделитесь в комментариях — интересно узнать ваши истории!