Как определить, в какую ветвь дерева нужно спускаться при поиске или обходе?

Выбор ветви дерева при поиске или обходе зависит от двух вещей: типа дерева (бинарное, n-арное, куча и т.д.) и цели операции (найти значение, посетить все узлы в определённом порядке).

Для бинарного дерева поиска (BST) правило простое: если искомое значение меньше текущего узла — идём в левое поддерево, если больше — в правое. Равенство — нашли. Если наткнулись на null — элемента нет. Это даёт сложность O(log n) в среднем.

def search_bst(root, target):
    if root is None:
        return None
    if target == root.val:
        return root
    elif target < root.val:
        return search_bst(root.left, target)
    else:
        return search_bst(root.right, target)

Для обходов (in-order, pre-order, post-order) порядок спуска фиксирован независимо от значений. Например, in-order: сначала левое поддерево, потом корень, потом правое. Рекурсия сама решает, куда идти — просто вызываем для левого и правого потомка в нужном порядке:

def inorder(node):
    if node is None:
        return
    inorder(node.left)
    visit(node)
    inorder(node.right)

Если дерево не является BST (например, обычное бинарное или n-арное), при поиске конкретного значения нужно проверять все ветви, пока не найдём. Здесь нет «умного» выбора — просто рекурсия по всем потомкам. Для полного обхода (DFS) тоже рекурсия, для BFS — очередь с посещением по уровням.

Есть ещё особые случаи: кучи и деревья отрезков. В куче при добавлении элемента идём в последний уровень, а потом всплываем; при извлечении корня — заменяем последним и просеиваем вниз, выбирая меньшего (в min-heap) или большего (max-heap) потомка. В дереве отрезков спускаемся по индексу-пути, сравнимому с бинарным поиском по отрезкам.

На практике для обычного обхода (например, чтобы вывести все узлы) просто следуем рекурсивному шаблону — никаких критериев выбора ветви нет, кроме самого определения обхода. Для поиска в любом дереве — если не знаем про упорядоченность, придётся просматривать все поддеревья, выбирая «все ветви» — то есть не выбираем, а перебираем.

Важно запомнить:

• В BST решение о ветви принимается за O(1) на уровень по сравнению ключа.
• В обходах направление задаётся жёстко алгоритмом (сначала левый, потом правый).
• В произвольном дереве — если цель не очевидна, просто обходим всё.
• Куча при операциях вставки/удаления выбирает ветвь по значению (меньший/больший ребёнок).