Обход бинарного дерева: preorder, inorder, postorder, стек и алгоритм Морриса

Коротко

Типовые задачи на деревья (глубина, симметрия, проверка BST, общий предок) разобраны в отдельной статье, а обход графов и сравнение DFS с BFS — в статье про DFS и BFS. Здесь только сами обходы в глубину: как они устроены, как написать каждый без рекурсии и как обойтись вообще без стека.

Одно дерево, три порядка

Возьмём дерево, на котором удобно проверять ответы:

        4
      /   \
     2     6
    / \   / \
   1   3 5   7

Дерево здесь бинарное дерево поиска, поэтому inorder выдал отсортированный список. Это не совпадение, к этому свойству вернёмся ниже.

Названия легко запомнить по положению корня: pre — корень до поддеревьев, in — между ними, post — после. Левое поддерево во всех трёх порядках идёт раньше правого.

Рекурсия: один обход вместо трёх

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

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def traverse(node, pre, ino, post):
    if node is None:
        return
    pre.append(node.val)  # первый визит: пришли сверху
    traverse(node.left, pre, ino, post)
    ino.append(node.val)  # второй визит: вернулись из левого
    traverse(node.right, pre, ino, post)
    post.append(node.val)  # третий визит: вернулись из правого


root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6, TreeNode(5), TreeNode(7)))
pre, ino, post = [], [], []
traverse(root, pre, ino, post)
print(pre)   # [4, 2, 1, 3, 6, 5, 7]
print(ino)   # [1, 2, 3, 4, 5, 6, 7]
print(post)  # [1, 3, 2, 5, 7, 6, 4]

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

Про рекурсию в целом есть отдельная статья, здесь важны две вещи.

Сложность. Каждый узел обрабатывается один раз, плюс по вызову на каждого пустого ребёнка. Это $O(n)$ времени. Память — глубина стека вызовов, то есть высота $h$: $O(\log n)$ для сбалансированного дерева и $O(n)$ для вырожденного, вытянутого в линию.

Лимит глубины. В Python стек вызовов по умолчанию ограничен примерно тысячей кадров. Дерево из ста тысяч узлов, вытянутое в линию, рекурсия не обойдёт:

deep = None
for i in range(100_000):
    deep = TreeNode(i, left=deep)

traverse(deep, [], [], [])
# RecursionError: maximum recursion depth exceeded

sys.setrecursionlimit отодвигает проблему, но не решает её: при большом лимите процесс может упасть уже на уровне C-стека. Надёжный выход — явный стек.

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

Стек повторяет то, что делала рекурсия: хранит узлы, к которым ещё предстоит вернуться. Трудность в том, что у каждого обхода своя логика возвращения. Разберём каждый, а потом приём, который закрывает все три одним шаблоном. Как устроен сам стек, рассказано в статье про стек и очередь.

Preorder

Самый простой случай: узел записываем сразу, как только достали из стека. Детей кладём в обратном порядке — сначала правого, потом левого, чтобы левый оказался сверху и обработался первым.

def preorder_iterative(root):
    if root is None:
        return []
    result, stack = [], [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

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

Inorder

Узел нельзя записать, пока не пройдено его левое поддерево. Поэтому сначала спускаемся влево до упора, складывая узлы в стек. Достали узел — значит, всё левее уже выведено: записываем его и переходим в правое поддерево.

def inorder_iterative(root):
    result, stack = [], []
    node = root
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        result.append(node.val)
        node = node.right
    return result

Условие while node or stack важно целиком. Когда стек пуст, у нас может остаться необработанное правое поддерево корня. Когда node пустой, в стеке ещё лежат предки. Цикл заканчивается, только если нет ни того, ни другого.

Этот шаблон стоит выучить наизусть: на нём держатся почти все итеративные задачи на дерево поиска.

Postorder: трюк с разворотом

Postorder записывает корень последним, а это обратный порядок к «корень → правое → левое». Такой обход пишется как preorder с переставленными детьми. Остаётся развернуть результат:

def postorder_reversed(root):
    if root is None:
        return []
    result, stack = [], [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return result[::-1]

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

Postorder: честный, с указателем на предыдущий

Честная версия использует тот же спуск влево, что и inorder. Сложность в том, что узел на вершине стека мы видим дважды: после левого поддерева и после правого. Отличить эти случаи помогает last — последний записанный узел. Если правый ребёнок есть и он не равен last, правое поддерево ещё не пройдено.

def postorder_iterative(root):
    result, stack = [], []
    node, last = root, None
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        top = stack[-1]
        if top.right and top.right is not last:
            node = top.right
        else:
            stack.pop()
            result.append(top.val)
            last = top
    return result

Заметьте, что top берётся через stack[-1], без pop. Снимать узел со стека можно, только когда оба поддерева пройдены.

Один шаблон на все три

Если не хочется держать в голове три разные схемы, можно сделать визиты явными. В стек кладём пары (узел, готов). Флаг False значит «узел нужно развернуть», True — «пора записать». Порядок в стеке обратный, поэтому кладём элементы задом наперёд:

def traverse_iterative(root, order):
    result = []
    stack = [(root, False)] if root else []
    while stack:
        node, ready = stack.pop()
        if ready:
            result.append(node.val)
            continue
        if order == 'post':
            stack.append((node, True))
        if node.right:
            stack.append((node.right, False))
        if order == 'in':
            stack.append((node, True))
        if node.left:
            stack.append((node.left, False))
        if order == 'pre':
            stack.append((node, True))
    return result


for order in ('pre', 'in', 'post'):
    print(order, traverse_iterative(root, order))
# pre [4, 2, 1, 3, 6, 5, 7]
# in [1, 2, 3, 4, 5, 6, 7]
# post [1, 3, 2, 5, 7, 6, 4]

Положение строки с True повторяет положение append в рекурсии, только в зеркальном порядке. Каждый узел попадает в стек дважды, так что константа чуть больше, но асимптотика та же: $O(n)$ времени и $O(h)$ памяти. На собеседовании это хороший запасной вариант, если вылетел из головы честный postorder.

Обход Морриса: без стека и без рекурсии

И рекурсия, и стек тратят $O(h)$ памяти, чтобы помнить, куда возвращаться. Дж. Моррис в 1979 году предложил хранить эту информацию в самом дереве. У листьев и многих внутренних узлов правый указатель пустой, и его можно временно использовать как нить обратно к предку.

Идея

Возьмём текущий узел node с непустым левым поддеревом. В inorder сразу перед node идёт его предшественник — самый правый узел левого поддерева. Его правый указатель всегда пустой: иначе он не был бы самым правым.

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

На каждом узле с левым ребёнком ищем предшественника. Дальше два случая:

• Нити ещё нет (pred.right is None): мы здесь впервые. Ставим нить, идём влево.
• Нить уже есть (pred.right is node): мы вернулись по ней, левое поддерево пройдено. Снимаем нить, записываем узел, идём вправо.

Узел без левого ребёнка записываем сразу и идём вправо. Если его правый указатель — нить, переход по ней и есть возвращение к предку.

def morris_inorder(root):
    result = []
    node = root
    while node:
        if node.left is None:
            result.append(node.val)
            node = node.right
            continue
        pred = node.left
        while pred.right and pred.right is not node:
            pred = pred.right
        if pred.right is None:
            pred.right = node  # ставим нить и уходим влево
            node = node.left
        else:
            pred.right = None  # левое поддерево пройдено, снимаем нить
            result.append(node.val)
            node = node.right
    return result

Условие pred.right is not node во внутреннем цикле обязательно. Без него поиск предшественника пройдёт по уже поставленной нити обратно в node и зациклится.

Пошаговый разбор

Пройдём по нашему дереву.

После обхода все нити сняты, дерево такое же, как в начале.

Почему это $O(n)$

Поиск предшественника выглядит как вложенный цикл, и легко решить, что сложность $O(n \log n)$ или хуже. На деле каждое ребро дерева проходится не больше двух раз за всё время работы: один раз, когда ставим нить, и один, когда её снимаем. Рёбер $n - 1$, значит, суммарная работа внутреннего цикла — $O(n)$. Константа примерно в два-три раза больше, чем у обхода со стеком.

Preorder Моррисом

Отличие от inorder — одна перенесённая строка. Узел записываем не при возвращении по нити, а при первом визите, когда нить ставим:

def morris_preorder(root):
    result = []
    node = root
    while node:
        if node.left is None:
            result.append(node.val)
            node = node.right
            continue
        pred = node.left
        while pred.right and pred.right is not node:
            pred = pred.right
        if pred.right is None:
            result.append(node.val)  # единственное отличие от inorder
            pred.right = node
            node = node.left
        else:
            pred.right = None
            node = node.right
    return result

Postorder Моррисом

Postorder заметно сложнее, и на собеседовании его почти не просят. Схема такая: добавляем фиктивный корень, у которого исходное дерево — левое поддерево. Каждый раз, когда снимаем нить у node, выводим правую кромку его левого поддерева снизу вверх. Чтобы пройти её снизу вверх без стека, кромку временно разворачивают как связный список и после чтения разворачивают обратно.

def reverse_right_edge(start):
    prev, cur = None, start
    while cur:
        nxt = cur.right
        cur.right = prev
        prev, cur = cur, nxt
    return prev


def morris_postorder(root):
    result = []
    dummy = TreeNode(0, left=root)
    node = dummy
    while node:
        if node.left is None:
            node = node.right
            continue
        pred = node.left
        while pred.right and pred.right is not node:
            pred = pred.right
        if pred.right is None:
            pred.right = node
            node = node.left
        else:
            pred.right = None
            tail = reverse_right_edge(node.left)
            cur = tail
            while cur:
                result.append(cur.val)
                cur = cur.right
            reverse_right_edge(tail)
            node = node.right
    return result


print(morris_postorder(root))  # [1, 3, 2, 5, 7, 6, 4]

Каждая кромка разворачивается дважды, и узлы разных кромок не пересекаются, так что время остаётся $O(n)$. Если собрать кромку в список вместо разворота, код станет проще, но память вырастет до $O(h)$ и смысл Морриса пропадёт.

Когда Моррис уместен

Плюс один: $O(1)$ памяти. Минусов больше:

• Дерево меняется во время обхода. Параллельно читать его из другого потока нельзя. Неизменяемые узлы так обходить вообще не получится.
• Ранний выход ломает дерево. Если прервать обход посередине (например, нашли k-й элемент и сделали return), часть нитей останется на месте, и в дереве появятся циклы. Придётся либо доходить до конца, либо отдельно снимать нити.
• Медленнее на практике. Лишние проходы по рёбрам и плохая работа с кешем делают его медленнее обхода со стеком, несмотря на ту же асимптотику.

Моррис встречается как follow-up: «а можно без дополнительной памяти?». Его стоит уметь объяснить и написать для inorder. В продакшен-коде обычно лучше стек.

Сравнение подходов

Здесь $h$ — высота дерева. В preorder в стеке лежат отложенные правые дети, не больше одного на уровень, поэтому оценка та же. Подробнее о том, как считать такие оценки, — в статье про O-нотацию.

Какой обход выбрать

Порядок выбирают не по вкусу, а по тому, когда узлу нужна информация.

Preorder: узел нужен раньше детей

Подходит, когда родитель передаёт что-то вниз: текущий путь, глубину, границы.

• Сериализация и копирование. Preorder с маркерами пустых узлов однозначно восстанавливает дерево. Корень идёт первым, поэтому при чтении его можно создать сразу и рекурсивно достроить поддеревья.

def serialize(root):
    out = []

    def go(node):
        if node is None:
            out.append('#')
            return
        out.append(str(node.val))
        go(node.left)
        go(node.right)

    go(root)
    return ','.join(out)


print(serialize(root))  # 4,2,1,#,#,3,#,#,6,5,#,#,7,#,#

• Пути от корня до листьев. Путь накапливается по пути вниз, и это ровно preorder.
• Префиксная запись выражения. Preorder дерева выражения даёт польскую нотацию: + * 2 3 4.

Inorder: дерево поиска

Для бинарного дерева поиска inorder выдаёт ключи по возрастанию. Отсюда целый класс задач:

• проверка, что дерево — BST: каждый следующий элемент inorder строго больше предыдущего;
• k-й наименьший элемент: остановиться на k-м шаге итеративного inorder;
• итератор по BST с операциями next и has_next: это итеративный inorder, разрезанный на части. Он тратит $O(h)$ памяти и в среднем $O(1)$ на вызов;
• минимальная разность между соседними ключами, восстановление BST с двумя переставленными узлами.

def kth_smallest(root, k):
    stack, node = [], root
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right


print(kth_smallest(root, 3))  # 3

Обратите внимание: итеративный вариант умеет останавливаться рано, а Моррис в такой задаче оставил бы нити в дереве.

Для обычного дерева, не BST, inorder особого смысла не имеет. Исключение — инфиксная запись выражения: 2 * 3 + 4, правда, без скобок она теряет приоритеты.

Postorder: ответ узла зависит от детей

Подходит, когда информация идёт снизу вверх.

• Высота, размер поддерева, диаметр, сбалансированность. Узел сначала получает ответы от детей, потом считает свой.
• Удаление дерева и освобождение памяти. Удалить узел можно только после того, как удалены оба поддерева, иначе потеряем на них ссылки.
• Вычисление выражения. Postorder дерева выражения — это обратная польская запись, которую считают одним стеком.
• Динамика на дереве. Почти вся она устроена как postorder, подробнее — в статье про DP на деревьях.

Короткое правило: если в рекурсивной функции результат вызова для детей используется в формуле для узла, это postorder, даже если в коде нет никакого append.

Восстановление дерева по двум обходам

Частый вопрос: какие пары обходов однозначно задают дерево с различными ключами. Ответ: preorder + inorder или postorder + inorder. Preorder (или postorder) указывает корень, а inorder делит остальные ключи на левое и правое поддерево. Пара preorder + postorder в общем случае неоднозначна: деревья «корень 1 с левым ребёнком 2» и «корень 1 с правым ребёнком 2» дают одинаковые [1, 2] и [2, 1]. Однозначно восстановить по ним можно только полное бинарное дерево, где у каждого узла ноль или два ребёнка.

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

• Перепутан порядок детей в итеративном preorder. Если положить левого раньше правого, стек выдаст правого первым, получится «корень → правое → левое».
• pop вместо просмотра вершины в postorder. Узел сняли со стека до обхода правого поддерева — вернуться к нему уже нельзя.
• Нет проверки is not node в Моррисе. Поиск предшественника проходит по нити и зацикливается.
• Нить не сняли. После обхода в дереве остаются циклы, и следующий обход, а заодно и сериализация, зависнут.
• **sys.setrecursionlimit(10**6) как решение.** На глубоком дереве это заканчивается падением процесса, а не исключением.
• Строгое сравнение при проверке BST через inorder. Если дубликаты запрещены, условие ошибки — node.val <= prev, а не node.val < prev: иначе равные соседи пройдут проверку.

Что спрашивают на собеседовании

1. Напишите inorder без рекурсии. Самый частый вопрос. Ответ — спуск влево со стеком.
2. А postorder? Сначала можно предложить разворот preorder, затем честную версию с last или шаблон с флагами.
3. Сколько памяти тратит обход? $O(h)$, а не $O(n)$ и не $O(\log n)$. Сбалансированность дереву никто не обещал.
4. Можно ли за $O(1)$ памяти? Да, обход Морриса. Объясните нити через предшественника, почему он работает за $O(n)$ и что дерево временно меняется.
5. Какой обход для такой-то задачи? Применяйте правило «вниз — preorder, BST — inorder, снизу вверх — postorder».

Если задача требует обхода по уровням (правая проекция, зигзаг, среднее по уровню), это уже BFS с очередью, а не один из трёх порядков. Такие задачи разобраны в статье про задачи на деревья.

Что запомнить

• Три обхода — это одна прогулка по дереву с тремя визитами в каждый узел. Порядок определяет, на каком визите узел записывают.
• Рекурсия и стек тратят $O(h)$ памяти. В Python на глубоком дереве рекурсия падает, стек — нет.
• Итеративный inorder — спуск влево до упора, pop, запись, шаг вправо. Его стоит знать наизусть.
• Postorder без рекурсии: разворот «корень → правое → левое», указатель на последний записанный узел или стек с флагами.
• Моррис даёт $O(1)$ памяти за счёт временных нитей от предшественника к узлу. Время $O(n)$, потому что каждое ребро проходится не больше двух раз.
• Выбор порядка: данные идут вниз — preorder, отсортированный BST — inorder, ответ собирается из детей — postorder.