Какие виды обхода бинарного дерева существуют?

Что проверяют

Знаете ли вы четыре классических обхода и можете ли написать любой без рекурсии. Следом почти всегда просят код итеративного in-order и спрашивают про сложность по памяти.

Как отвечать

Два семейства:

• обход в глубину (DFS): три порядка, различаются моментом посещения корня. Pre-order: корень, левое, правое. In-order: левое, корень, правое. Post-order: левое, правое, корень;
• обход в ширину (BFS, level-order): уровень за уровнем через очередь.

Сразу назовите применение, это ценнее определений:

• in-order на бинарном дереве поиска выдаёт ключи по возрастанию, так проверяют корректность BST и ищут k-й элемент;
• pre-order удобен для копирования и сериализации: корень пишется раньше потомков, и при сохранении пустых узлов дерево восстанавливается однозначно;
• post-order нужен, когда результат узла зависит от потомков: высота, размер поддерева, удаление, вычисление выражения;
• BFS даёт минимальную глубину, вид сбоку, вывод по уровням.

Время у всех O(n). Память у DFS O(h), где h высота дерева, у вырожденного дерева это O(n). У BFS O(w), где w ширина самого широкого уровня, у полного дерева это около n/2. Если спросят про O(1) памяти, назовите обход Морриса: он временно перешивает указатели на пустых правых ссылках.

Для Python важны две детали. Глубина рекурсии ограничена: sys.getrecursionlimit() по умолчанию 1000, и вырожденное дерево на десять тысяч узлов уронит рекурсивный обход с RecursionError. Поэтому нужно уметь итеративные версии на явном стеке из списка. Очередь для BFS делается на collections.deque с popleft(), а сам обход удобно оформить генератором через yield, чтобы не собирать список целиком.

Где спотыкаются

Делают очередь на обычном списке через pop(0). Каждое извлечение сдвигает весь список, и BFS становится квадратичным.

Путаются в итеративном post-order. Проще всего пройти в порядке «корень, правое, левое» и развернуть результат, но это нужно уметь объяснить, а не только вспомнить.

Говорят, что in-order всегда выдаёт отсортированную последовательность. Это верно только для BST, на произвольном бинарном дереве это просто порядок «левое, корень, правое».