Сигнал задачи
Когда применять
Состояние естественно раскладывается по поддеревьям или уровням.
Что держать в голове
- Уметь объяснять рекурсивную декомпозицию по поддеревьям.
- Уметь выбирать порядок обхода по моменту обработки корня.
Сложность
- Полный DFS или BFS дерева: O(n) времени; память O(h) для рекурсивного DFS и до O(w) для BFS, где h — высота, w — ширина.
Границы и ошибки
- Не путайте структурное бинарное дерево с BST: упорядочивающий инвариант существует только при явном условии.