Пример использования деревьев

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

Отличаете ли задачу, где дерево действительно нужно, от той, где хватит словаря. Просят пример, а не определение, и почти всегда спрашивают про сложность операций и про глубину рекурсии.

Как отвечать

Сначала назовите, где деревья встречаются на практике: иерархии (категории, комментарии, файлы), разбор кода и выражений (модуль ast), индексы баз данных, префиксное дерево для автодополнения, куча в heapq как дерево внутри списка, решающие деревья в моделях.

Хороший пример на Python это не самописный BST, а разворачивание плоского списка с идентификатором и родителем в иерархию за один проход:

def build_tree(rows):
    nodes = {r["id"]: {"id": r["id"], "children": []} for r in rows}
    roots = []
    for r in rows:
        parent = nodes.get(r["parent_id"])
        target = parent["children"] if parent else roots
        target.append(nodes[r["id"]])
    return roots

Один запрос к базе, один проход, линейное время. Дальше про сложность: в сбалансированном дереве поиск и вставка стоят логарифм, но словарь даёт доступ за константу и почти всегда выигрывает. Дерево берут, когда нужен порядок, диапазонные запросы, префиксы или сама иерархия. Для отсортированных данных чаще подходит bisect по списку, для приоритетов heapq, и это лучше самодельной структуры.

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

Рассказывают определение и пишут вставку в BST, но не могут сказать, чем это лучше словаря. Заодно забывают, что без балансировки на отсортированном входе дерево вырождается в список, и логарифм превращается в линию.

Обходят рекурсией реальные данные. На глубокой иерархии приходит RecursionError, потому что предел стека в Python примерно тысяча кадров. Поднимать предел не решение, глубокий обход пишется итеративно со своим стеком.

Не проверяют данные на циклы и висячие ссылки. Если родитель указывает на потомка или на удалённый узел, построение зацикливается или молча теряет ветку. Нужен набор посещённых узлов и явная обработка сирот.