Сравнение бинарных деревьев: рекурсия против итерации

Проверяем, идентичны ли два бинарных дерева: оптимальная рекурсия O(n) с ранними выходами и проверкой ссылок, плюсы и минусы итеративных альтернатив.

Сравнение двух бинарных деревьев на совпадение структуры и значений кажется задачей, где хитрые приемы могут выбить немного дополнительной скорости. На деле простой рекурсивный подход уже работает максимально быстро, а с небольшим уточнением он получается и элегантным, и результативным.

Постановка задачи

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

class Node:
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def same_tree(u: Node, v: Node) -> bool:
    if u is None and v is None:
        return True
    return (u is not None and v is not None) and (u.val == v.val) and \
        same_tree(u.left, v.left) and same_tree(u.right, v.right)
x = Node(1)
y = Node(1)
print(same_tree(x, y))

Что на самом деле происходит

Здесь невозможно спуститься ниже O(n): чтобы убедиться в совпадении деревьев, как минимум нужно посмотреть на каждый узел. Эта нижняя граница делает рекурсивное решение теоретически оптимальным по времени. По памяти рекурсия расходует O(h) кадров стека — это оптимально для сравнения в глубину, которое следует форме дерева. Мгновенное завершение при несовпадении гарантирует, что обход прекращается сразу, как только найдено различие.

Полезно добавить небольшой штрих. Проверка на идентичность ссылок избавляет от лишней работы, когда обе переменные указывают на один и тот же объект узла, а ранняя отрицательная проверка освобождает «горячий путь» для быстрого обнаружения расхождений.

Оптимизированная рекурсивная версия

def trees_match(a, b):
    if a is b:
        return True
    if not a or not b or a.val != b.val:
        return False
    return trees_match(a.left, b.left) and trees_match(a.right, b.right)

Здесь сохраняются O(n) по времени и O(h) по памяти. Проверка идентичности сразу покрывает и случай None, и ситуацию с одинаковыми ссылками. Ранний возврат при несоответствии структуры или значения обрывает работу как можно раньше. На практике это убирает лишние вызовы и оставляет код лаконичным, не добавляя накладных расходов на ведение состояния.

Есть ли более быстрые или экономные по памяти альтернативы

Альтернативы с явным стеком или очередью рабочие, но асимптотики они не улучшают. Итеративный обход в глубину или в ширину также дает O(n) по времени. Он меняет стек вызовов на размещенный в куче стек или очередь, поэтому профиль дополнительной памяти иной, но по-прежнему пропорционален фронту обхода. Чудесного ускорения здесь нет: различается скорее стиль работы и место, где хранится состояние.

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

Функция, ради которой нужно оценивать и подстраивать размер стека вызовов, куда менее полезна, чем та, что просто стабильно работает. В жизни ее просто вызывают и ждут, что все пройдет нормально; иначе это мина, которая срабатывает в самый неподходящий момент.

Если вас тревожит предел рекурсии, его можно выставить практически бесконечным.

Итеративный вариант предпочтительнее, когда нельзя наверняка сказать, что деревья неглубокие. В продакшене рекурсивную обработку бинарного дерева используют лишь тогда, когда оно сбалансировано — например, как красно‑черное или AVL‑дерево.

Из этих взглядов складывается простой практический ориентир. Если деревья сбалансированы или гарантированно неглубокие, рекурсия — оптимальный и удобный путь. Если глубина неизвестна или может сильно вырасти, итерация избавит от сюрпризов, связанных с лимитами рекурсии.

Зачем это важно

Сравнение деревьев часто попадает на «горячие» участки в системах. Понимание, что потолок — O(n), избавляет от погони за несуществующими ускорениями, а знание про O(h) по стеку позволяет выбирать между рекурсией и итерацией, опираясь на эксплуатационные риски, а не на догадки. Небольшие улучшения в рекурсивной версии — проверка идентичности и ранние выходы — дают ощутимую пользу без усложнения кода.

Итоги

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