Бинарные деревья: обходы и задачи

Перед началом: стек и очередь (модуль 5), бинарный поиск (модуль 10). Инструменты: Go 1.27, срез как стек и очередь, strings.Builder. Трудоёмкость: ~6.5 ч (теория 2.5 ч · практика 4 ч).

🔥 Инцидент: «Импорт каталога уронил процесс: дерево глубиной 100 000»

Каталог категорий в сервисе — бинарное дерево, и обход был рекурсивным: восемь строк, которые невозможно написать неправильно. На dev-стенде с десятью тысячами узлов всё работало годами. А ночью клиент загрузил каталог, где категории вложены строго одна в другую — «бамбук» глубиной 100 000.

Обход такого дерева — 100 000 вложенных вызовов: стек горутины вырос до гигабайта, и рантайм убил процесс с fatal error: stack overflow. Ключевая деталь: это не паника — recover() не ловит, умирает весь процесс вместе с чужими запросами, а мониторы показывают «всплеск нагрузки».

Лечим в модуле: обходы с явным стеком в куче (не в стеке горутины), BFS по уровням и задачи, которые спрашивают на деревьях: глубина, диаметр, LCA, invert, сериализация с round-trip. «Бамбук» из сниппета — та самая проверка: 100 000 узлов, ноль рекурсии.

📖 Теория

11.1 Терминология: высота, глубина, форма дерева

Глубина узла — расстояние от корня, высота — до дальнего листа; у дерева высота = высота корня. Формы: perfect — все листья на одной глубине, у внутренних узлов по двое детей; complete — уровни заполняются слева направо (форма кучи из модуля 9). Главный враг рекурсии — «бамбук»: высота n вместо log₂n у сбалансированного дерева.

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

11.2 Обходы: pre / in / post — рекурсивно

Три обхода — один каркас; различается момент «посещения» узла: preorder — корень до детей (копирование, сериализация), inorder — корень между поддеревьями (для BST даёт порядок, задел на модуль 12), postorder — корень после детей (высоты, диаметр, удаление).

go
// Рекурсивная форма повторяет определение обхода дословно.
func preorder(n *node, visit func(*node)) {
	if n == nil {
		return
	}
	visit(n) // inorder: строку ниже; postorder: обе строки ниже
	preorder(n.left, visit)
	preorder(n.right, visit)
}

Рекурсия честно выражает инвариант «обработай поддерево» — поэтому её и пишут. Цена — стек горутины, растущий с высотой; модуль 5 обещал замену явным стеком — это §11.3.

11.3 Итеративно: стек живёт в куче

Идея одна: кадры рекурсии переносим в срез-стек — его глубина ограничена кучей, а не гигабайтным лимитом стека горутины. Preorder: правый ребёнок кладётся первым. Postorder: «корень-право-лево» плюс разворот. Inorder: спуск влево с отложенными родителями на стеке.

go
// Итеративный preorder: правый ребёнок — на дно, левый — наверх стека.
stack := []*node{root}
for len(stack) > 0 {
	n := stack[len(stack)-1]
	stack = stack[:len(stack)-1]
	if n == nil {
		continue // nil-потомков просто пропускаем
	}
	visit(n)
	stack = append(stack, n.right, n.left)
}

Алгоритм тот же, меняется лишь место жизни кадров. «Бамбук» из 100 000 узлов проходит спокойно, а recover() бессилен: overflow — не паника.

11.4 BFS по уровням

Обход в ширину берёт уровни по очереди; граница уровня — размер очереди на входе итерации: печать дерева, минимальная глубина, «правый вид».

go
// Уровни: сколько узлов в очереди на входе итерации — таков и уровень.
queue := []*node{root}
for len(queue) > 0 {
	size := len(queue)
	for i := 0; i < size; i++ {
		n := queue[0]
		queue = queue[1:]
		visit(n)
		for _, c := range []*node{n.left, n.right} {
			if c != nil {
				queue = append(queue, c)
			}
		}
	}
}

Память BFS — ширина фронта: один уровень «широкого» дерева держит миллионы узлов, тогда как DFS-стек хранит только путь. Выбор обхода — компромисс памяти (§11.6).

11.5 Классические задачи

• Глубина и диаметр. Глубина — это высота. Диаметр — длиннейший путь в рёбрах: post-order даёт высоты, а путь через узел — сумма высот детей.
• LCA (наименьший общий предок). Post-order: если оба поддерева вернули по узлу — текущий и есть ответ; если один — ответ ушёл наверх.
• invert (зеркало), same tree, path sum — тренировочные задачи на том же каркасе.
• Сериализация с round-trip. Preorder с nil-маркерами восстанавливает форму однозначно; level-order читаемее, но требует аккуратности с «дырами».

go
// LCA: наверх поднимается найденный узел; нашли оба поддерева —
// текущий узел и есть первый общий.
l, r := lca(n.left, p, q), lca(n.right, p, q)
if l != nil && r != nil {
	return n
}
if l != nil {
	return l
}
return r

Проверка сериализации ровно одна: decode(encode(t)) сравнивается с t (same tree). Нет round-trip-теста — сериализация не работает, даже когда «выглядит правильной».

11.6 Компромиссы

Правило: контракт фиксируйте именем и докомментарием — «invert возвращает копию» или «invert меняет дерево на месте»; обход выбирайте по памяти: BFS платит шириной, DFS — высотой.

💻 Практика

1. Три обхода итеративно. Реализуйте pre/in/post со стеком, сверьте с рекурсивными версиями и прогоните по «бамбуку» из 100 000 узлов. Почему рекурсивный вариант падает фатально и это не ловит recover()?
2. Диаметр. diameter(root) за O(n) одним post-order. Тесты: perfect из 7 → 4; «бамбук» из 5 → 4; один узел → 0; найдите дерево, где диаметр не проходит через корень.
3. LCA. lca(root, p, q) из §11.5. Тесты: узлы в разных поддеревьях → корень; p — предок q; p == q; узел отсутствует → nil. Почему для BST задача решается спуском без пост-ордера (задел м12)?
4. Invert: две версии. Мутирующая и копирующая. Тесты: invert(invert(t)) совпадает с t; копирующая не изменила исходное дерево, мутирующая изменила (это её контракт). Напишите same-tree-сравнение — пригодится в задаче 5.
5. Сериализация уровнями. encode/decode через BFS с маркерами nil. Round-trip-тесты: пусто, один узел, perfect, «бамбук», узел только с правым ребёнком. Почему без nil-маркеров preorder не восстанавливает форму однозначно?

🧩 Quiz

✅ Итоги модуля

• Высота определяет всё: сложность операций, память обхода, глубину рекурсии; «бамбук» делает рекурсию фатально опасной.
• Три обхода — один каркас; inorder на BST отсортирован, postorder — язык агрегатов.
• Итеративный обход — та же логика со стеком в куче: 100 000 узлов проходят без рекурсии.
• BFS берёт уровни через размер очереди; память — ширина, не высота.
• Диаметр, LCA, invert, сериализация — один набор каркасов обхода; round-trip-тест обязателен.

🔗 Мостик к Модулю 12

Деревья мы собирали руками, и порядок держался на удаче: «бамбук» из инцидента — дерево без структуры. Дальше — BST: «левое меньше, правое больше» превращает ветвления в структуру поиска; модуль 12 — о нём.