Обход Морриса: in-order обход бинарного дерева за O(1) памяти
Как обойти бинарное дерево без стека и рекурсии: нити к предшественнику, inorder, preorder и postorder по Моррису, почему это O(n), Recover BST и типичные ошибки. Код на 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, начиная с корня:
- Если у
curнет левого ребёнка — посещаемcurи идём вправо. - Иначе находим предшественника
pred: шаг влево, потом вправо до упора, но останавливаемся, еслиpred.rightуже указывает наcur. - Если
pred.rightпустой — это первый заход. Ставим нитьpred.right = curи спускаемся влево. - Если
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 | Что происходит | Вывод |
|---|---|---|---|
| 1 | 4 | предшественник — 3, ставим нить 3 → 4, идём влево | |
| 2 | 2 | предшественник — 1, ставим нить 1 → 2, идём влево | |
| 3 | 1 | левого нет: посещаем, идём вправо по нити | 1 |
| 4 | 2 | предшественник 1 уже указывает на 2: снимаем нить, посещаем | 2 |
| 5 | 3 | левого нет: посещаем, идём вправо по нити 3 → 4 | 3 |
| 6 | 4 | нить 3 → 4 найдена: снимаем, посещаем, идём к 6 | 4 |
| 7 | 6 | предшественник — 5, ставим нить 5 → 6 | |
| 8 | 5 | посещаем, по нити к 6 | 5 |
| 9 | 6 | снимаем нить, посещаем, идём к 7 | 6 |
| 10 | 7 | посещаем, 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)?». Ожидается:
- Сказать, что стек занимает O(h), и в худшем случае это O(n).
- Объяснить идею нитей: стек хранит путь назад, а путь назад можно положить в пустой
rightпредшественника. - Написать inorder — это 15 строк.
- Обосновать O(n) по времени: каждое ребро проходится константное число раз.
- Упомянуть цену: дерево временно меняется, обход нельзя прерывать, он не потокобезопасен.
Последний пункт часто важнее самого кода — он показывает, что вы понимаете компромисс, а не просто выучили трюк. Для общей картины техник на деревьях пригодится подборка задач на деревья.
Что запомнить
- Стек при inorder хранит «куда вернуться после левого поддерева». Моррис кладёт этот адрес в пустой
rightinorder-предшественника. - Первый заход в узел — ставим нить и идём влево; второй — снимаем нить и идём вправо.
- Время O(n): правые границы левых поддеревьев не пересекаются, каждое ребро проходится до трёх раз.
- Preorder — выводим при установке нити, inorder — при снятии, postorder — разворачиваем правые границы.
- Не выходите из цикла досрочно: дерево останется с циклами.