Итеративный обход дерева: как избежать переполнения стека

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

Вы когда-нибудь писали рекурсивный обход бинарного дерева, и на глубоком дереве (например, вырожденном в список) программа падала с RecursionError? Это классическая ловушка на собеседованиях и в реальных проектах. В этой статье вы узнаете, как заменить рекурсию явным стеком, чтобы обходить дерево любой формы без риска переполнения стека. Вы поймёте, почему рекурсия и итерация — две стороны одной медали, и сможете уверенно решать задачи вроде проверки BST или поиска k-го наименьшего элемента.

Рекурсия vs итерация: одно и то же, но с контролем

В основе любого обхода дерева лежит систематическое посещение каждого узла ровно один раз. Рекурсия использует стек вызовов для хранения состояния «где я сейчас». Когда вы вызываете traverse(node.left), на стек кладётся фрейм; при возврате он снимается, и вы знаете, куда продолжить. Но у стека вызовов есть лимит — обычно несколько тысяч фреймов. На вырожденном дереве (длинная цепочка) вы его превысите и получите крах.

Итеративный подход делает стек явным: вы используете собственный список (например, list в Python) для хранения узлов, которые нужно обработать. Алгоритмически шаги идентичны — вы просто переносите учёт из рантайма в структуру данных, которую контролируете. Это даёт гарантированную сложность O(h) по памяти (где h — высота дерева) без риска переполнения.

Инфиксный обход: от рекурсии к явному стеку

Рекурсивная версия: элегантно, но опасно

def inorder_recursive(node, result):
    if node is None:
        return
    inorder_recursive(node.left, result)  # идём влево
    result.append(node.val)               # посещаем узел
    inorder_recursive(node.right, result) # идём вправо

Почему это работает: стек вызовов запоминает, куда вернуться после левого поддерева, поэтому порядок: левое, узел, правое.

Проблема: на дереве из 100 000 узлов в виде цепочки стек переполнится.

Итеративная версия: безопасно для любой формы

def inorder_iterative(root):
    result = []
    stack = []
    cur = root
    while cur is not None or stack:
        # спускаемся по левым детям, сохраняя узлы в стек
        while cur is not None:
            stack.append(cur)
            cur = cur.left
        # cur is None — извлекаем следующий узел
        cur = stack.pop()
        result.append(cur.val)  # посещаем
        cur = cur.right         # переходим к правому поддереву
    return result

Почему это работает: внутренний цикл кладёт в стек весь левый путь, имитируя спуск рекурсии. Когда идти влево некуда, мы извлекаем последний узел — тот, чьё левое поддерево только что обработано. Затем посещаем его и переходим к правому ребёнку, повторяя процесс.

Типичные ошибки и как их избежать

• Забыли обновить cur после извлечения — если оставить cur на извлечённом узле, внешний цикл добавит его в стек снова, получится бесконечный цикл. Всегда ставьте cur = cur.right после посещения.
• Использование Stack из Java вместо ArrayDeque — в Python это неактуально, но помните: в Java Stack синхронизирован и медленнее. В Python просто используйте список.
• Неправильное условие внешнего цикла — условие cur is not None or stack гарантирует, что мы обрабатываем, пока есть текущий узел или узлы в стеке. Упустив любую часть, вы рискуете преждевременно выйти или получить AttributeError.

Применение в реальных задачах на собеседованиях

Задача 1: Проверка корректности BST

Дано бинарное дерево, определите, является ли оно валидным BST. Свойство инфиксного обхода (строго возрастающая последовательность) решает задачу за O(n) времени и O(h) памяти.

def is_valid_bst(root):
    prev = float('-inf')  # используем -inf для удобства
    stack = []
    cur = root
    while cur is not None or stack:
        while cur is not None:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        if cur.val <= prev:  # нарушение строгого возрастания
            return False
        prev = cur.val
        cur = cur.right
    return True

Задача 2: k-й наименьший элемент в BST

Верните k-е наименьшее значение (индексация с 1). Раньше остановите инфиксный обход, когда посетите k узлов.

def kth_smallest(root, k):
    stack = []
    cur = root
    count = 0
    while cur is not None or stack:
        while cur is not None:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        count += 1
        if count == k:
            return cur.val
        cur = cur.right
    raise ValueError("k больше числа узлов")

Оба решения работают за O(n) времени (в худшем случае посещаем каждый узел) и O(h) дополнительной памяти. Для несбалансированного дерева h = n, что даёт O(n) памяти — это неизбежно, если мы имитируем стек рекурсии. Для сбалансированного дерева h = log n, так что итеративная версия гораздо экономнее по памяти, чем наивная рекурсия, которая может упереться в лимит стека.

Почему это важно для вашего роста

Переход от слепой рекурсии к явному стеку — это не просто трюк для собеседований, а смена мышления. Вы начинаете видеть алгоритмы как конечные автоматы, а не магические заклинания. Когда вы встретите DFS на графах, итеративное углубление или разбор выражений, вы автоматически потянетесь к стеку, зная, что контролируете память и избегаете неожиданных падений.

Более того, вы обретёте уверенность: если интервьюер даст «глубокое» дерево, вы улыбнётесь, достанете свой стек и решите задачу за O(n) времени и O(h) памяти — без пота и переполнения.

Ваш следующий шаг

Возьмите бинарное дерево (сгенерируйте случайное или нарисуйте простое BST на бумаге). Попробуйте реализовать прямой обход (preorder) итеративно, используя тот же паттерн: кладите узел, затем правого ребёнка, затем левого (чтобы левый обработался следующим). Сравните вывод с рекурсивной версией. Почувствуйте, как контроль переходит от стека вызовов к вашим рукам.

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