Обход Морриса: in-order обход бинарного дерева за O(1) памяти

Как обойти бинарное дерево без стека и рекурсии: нити к предшественнику, inorder, preorder и postorder по Моррису, почему это O(n), Recover BST и типичные ошибки. Код на Python.

11 мин чтенияалгоритмы · деревья · python

Коротко

ПараметрЗначение
ВремяO(n) — каждое ребро проходится не больше трёх раз
Доп. памятьO(1) — ни стека, ни рекурсии
Ценадерево временно модифицируется (нити в пустых right)
Порядкиinorder и preorder — просто, postorder — с разворотом цепочки
  • Главная идея: перед тем как уйти в левое поддерево, оставляем «нить» — указатель из самого правого узла левого поддерева обратно в текущий узел. Это и есть дорога назад, которую обычно хранит стек.
  • Вторая встреча с нитью означает «левое поддерево обойдено», нить убираем, и дерево возвращается в исходный вид.
  • На собеседовании это follow-up к обычному обходу: «а можно за O(1) памяти?».

Зачем это вообще нужно

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

Алгоритм Джозефа Морриса (1979) убирает эту память целиком. Он пользуется тем, что в бинарном дереве из n узлов есть n + 1 пустых указателей None. Это бесплатное место: временно положим туда служебные ссылки, а потом вернём всё как было.

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

Что хранит стек при inorder-обходе

Inorder — это «левое поддерево, узел, правое поддерево». Когда мы спускаемся из узла X влево, стек запоминает X, чтобы вернуться к нему после левого поддерева.

К какому узлу мы вернёмся? Последний узел, который посещается в левом поддереве X, — самый правый узел этого поддерева. Его называют inorder-предшественником X. У этого узла правый указатель гарантированно пустой (иначе он не был бы самым правым).

Отсюда трюк: запишем в predecessor.right ссылку на X. Тогда после обхода левого поддерева мы просто пойдём «вправо» из предшественника и окажемся в X. Стек больше не нужен — дорога назад вшита в дерево.

Алгоритм

Держим один указатель cur, начиная с корня:

  1. Если у cur нет левого ребёнка — посещаем cur и идём вправо.
  2. Иначе находим предшественника pred: шаг влево, потом вправо до упора, но останавливаемся, если pred.right уже указывает на cur.
  3. Если pred.right пустой — это первый заход. Ставим нить pred.right = cur и спускаемся влево.
  4. Если pred.right == cur — мы вернулись по нити, левое поддерево обойдено. Снимаем нить, посещаем cur, идём вправо.
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def morris_inorder(root): result = [] cur = root while cur: if cur.left is None: result.append(cur.val) cur = cur.right continue # ищем предшественника: самый правый узел левого поддерева pred = cur.left while pred.right and pred.right is not cur: pred = pred.right if pred.right is None: pred.right = cur # ставим нить cur = cur.left else: pred.right = None # снимаем нить result.append(cur.val) cur = cur.right return result

Обратите внимание на шаг 1: «идём вправо» может означать как настоящего правого ребёнка, так и нить. Алгоритму всё равно — в обоих случаях это следующий узел в inorder-порядке.

Разбор на примере

Возьмём дерево:

        4
      /   \
     2     6
    / \   / \
   1   3 5   7
ШагcurЧто происходитВывод
14предшественник — 3, ставим нить 3 → 4, идём влево
22предшественник — 1, ставим нить 1 → 2, идём влево
31левого нет: посещаем, идём вправо по нити1
42предшественник 1 уже указывает на 2: снимаем нить, посещаем2
53левого нет: посещаем, идём вправо по нити 3 → 43
64нить 3 → 4 найдена: снимаем, посещаем, идём к 64
76предшественник — 5, ставим нить 5 → 6
85посещаем, по нити к 65
96снимаем нить, посещаем, идём к 76
107посещаем, right = None — конец7

Результат [1, 2, 3, 4, 5, 6, 7], и после обхода все нити сняты: дерево совпадает с исходным. Я проверил это на двух тысячах случайных деревьев, сравнивая с рекурсивным обходом и структурой до/после.

Почему это O(n), а не O(n·h)

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

Но посмотрите, по каким рёбрам он ходит: шаг cur.left, затем цепочка правых рёбер в левом поддереве. Эта цепочка — правая граница левого поддерева cur, и у разных узлов такие цепочки не пересекаются. Каждое ребро дерева попадает на правую границу левого поддерева ровно одного узла.

Для каждого cur с левым ребёнком цепочка проходится дважды: при установке нити и при её снятии. Плюс сам обход ходит по каждому ребру один раз. Итого каждое ребро — не больше трёх раз, то есть O(n). Эмпирически на случайных деревьях выходит около 2,5n шагов указателя.

Preorder по Моррису

Preorder — «узел, левое, правое». Каркас тот же, меняется только момент посещения: узел выводим при первом заходе, когда ставим нить, а не когда снимаем.

def morris_preorder(root): result = [] cur = root while cur: if cur.left is None: result.append(cur.val) cur = cur.right continue pred = cur.left while pred.right and pred.right is not cur: pred = pred.right if pred.right is None: result.append(cur.val) # печатаем при первом заходе pred.right = cur cur = cur.left else: pred.right = None cur = cur.right return result

Для дерева выше получится [4, 2, 1, 3, 6, 5, 7].

Postorder по Моррису

С postorder сложнее: узел нужно выводить после обоих поддеревьев, а Моррис возвращается в узел только один раз — после левого. Решение классическое:

  • добавляем фиктивный корень dummy, у которого left = root;
  • когда снимаем нить у cur, выводим правую границу левого поддерева cur в обратном порядке — от предшественника вверх до cur.left.

Чтобы вывести цепочку снизу вверх без стека, её временно разворачивают, как связный список по right-указателям, а после вывода разворачивают обратно. Приём тот же, что в задаче о развороте связного списка.

def reverse_path(frm, to): # разворачивает цепочку по right-указателям от frm до to if frm is to: return prev, node = frm, frm.right while prev is not to: nxt = node.right node.right = prev prev, node = node, nxt def morris_postorder(root): result = [] dummy = TreeNode(0, left=root) cur = dummy while cur: if cur.left is None: cur = cur.right continue pred = cur.left while pred.right and pred.right is not cur: pred = pred.right if pred.right is None: pred.right = cur cur = cur.left else: # выводим правую границу левого поддерева снизу вверх reverse_path(cur.left, pred) node = pred while True: result.append(node.val) if node is cur.left: break node = node.right reverse_path(pred, cur.left) pred.right = None cur = cur.right return result

Результат для примера — [1, 3, 2, 5, 7, 6, 4]. Сложность остаётся O(n): каждая правая граница разворачивается дважды, а границы не пересекаются. Но код уже заметно хрупче, и на интервью его обычно не требуют — достаточно объяснить идею.

Где это применяют

Моррис полезен везде, где нужен inorder-обход BST, а ограничение по памяти жёсткое.

Recover Binary Search Tree

Классика LeetCode 99: в BST поменяли местами значения двух узлов, нужно починить дерево. Follow-up в условии прямо просит O(1) памяти — это и есть Моррис.

Идея: inorder-обход BST даёт отсортированную последовательность. Два переставленных элемента ломают порядок в одном или двух местах. Первый «плохой» узел — prev в первой инверсии, второй — cur в последней.

def recover_tree(root): first = second = prev = None cur = root while cur: if cur.left: pred = cur.left while pred.right and pred.right is not cur: pred = pred.right if pred.right is None: pred.right = cur cur = cur.left continue pred.right = None # посещение cur if prev and prev.val > cur.val: if first is None: first = prev second = cur prev = cur cur = cur.right first.val, second.val = second.val, first.val

Здесь каркас записан компактнее: ветка «посещение» общая для случая без левого ребёнка и для случая снятой нити. Так удобнее, когда логика посещения больше одной строки.

K-й наименьший элемент в BST

Считаем посещённые узлы и запоминаем k-й. Тут есть ловушка, о которой ниже.

Другие применения

  • Проверка, что дерево — корректный BST (см. статью о бинарном дереве поиска): сравниваем каждый посещённый узел с предыдущим.
  • Поиск двух элементов BST с заданной суммой — два встречных итератора, хотя здесь чаще берут стеки.
  • Flatten Binary Tree to Linked List (LeetCode 114) решается той же идеей: правое поддерево подвешивается к предшественнику.

Типичные ошибки

Ранний выход из цикла. Самая коварная. Допустим, мы ищем k-й элемент и делаем return, как только нашли. В этот момент в дереве ещё висят нити, и оно превратилось в граф с циклами. Любой следующий рекурсивный обход уйдёт в бесконечность — у меня проверочная функция упала с RecursionError. Правильно — запомнить ответ и дойти цикл до конца:

def kth_smallest(root, k): ans = None cur = root while cur: if cur.left: pred = cur.left while pred.right and pred.right is not cur: pred = pred.right if pred.right is None: pred.right = cur cur = cur.left continue pred.right = None k -= 1 if k == 0: ans = cur.val # запоминаем, но обход не прерываем cur = cur.right return ans

Это превращает «O(k)» в честный O(n), зато дерево остаётся целым. Если ранний выход критичен, используйте стек.

Условие pred.right без проверки на cur. Если написать while pred.right: pred = pred.right, то при втором заходе цикл пройдёт по нити в cur, дальше вправо — и либо зациклится, либо найдёт не того предшественника.

Сравнение == вместо is. В Python pred.right == cur для объектов без __eq__ работает как сравнение идентичности, но если у класса узла переопределено равенство по значению, а в дереве есть дубликаты, получите трудноуловимый баг. Сравнивайте ссылки через is.

Многопоточность и чужие данные. Обход мутирует дерево. Если параллельно его кто-то читает, он увидит циклы. В многопоточном коде и в библиотеках, которые получают дерево извне, Моррис почти всегда плохая идея.

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

Как это спрашивают на собеседовании

Типичный сценарий: вы решили «обойти дерево inorder» или «найти k-й элемент в BST» стеком, и интервьюер спрашивает: «Сколько памяти? А можно O(1)?». Ожидается:

  1. Сказать, что стек занимает O(h), и в худшем случае это O(n).
  2. Объяснить идею нитей: стек хранит путь назад, а путь назад можно положить в пустой right предшественника.
  3. Написать inorder — это 15 строк.
  4. Обосновать O(n) по времени: каждое ребро проходится константное число раз.
  5. Упомянуть цену: дерево временно меняется, обход нельзя прерывать, он не потокобезопасен.

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

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

  • Стек при inorder хранит «куда вернуться после левого поддерева». Моррис кладёт этот адрес в пустой right inorder-предшественника.
  • Первый заход в узел — ставим нить и идём влево; второй — снимаем нить и идём вправо.
  • Время O(n): правые границы левых поддеревьев не пересекаются, каждое ребро проходится до трёх раз.
  • Preorder — выводим при установке нити, inorder — при снятии, postorder — разворачиваем правые границы.
  • Не выходите из цикла досрочно: дерево останется с циклами.

Потренироваться в спокойной обстановке

Все задачи