Что такое дерево и его структура

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

Владеете ли вы терминологией без путаницы и понимаете ли, что готовой сбалансированной структуры в Python нет. Вопрос вводный, поэтому ценятся точные формулировки и переход к тому, где деревья реально работают.

Как отвечать

Дерево это связный граф без циклов с выделенным корнем. Отсюда сразу следствия: рёбер на одно меньше, чем узлов, а путь между любой парой узлов единственный. Термины: родитель и потомки, лист (узел без потомков), степень (число потомков), глубина узла (расстояние от корня), высота дерева (глубина самого далёкого листа).

Дальше называют виды: бинарное дерево, дерево поиска с инвариантом на поддеревья, сбалансированные варианты (AVL, красно-чёрное), куча, префиксное дерево для строк, B-дерево в индексах баз данных. Обходы: прямой, симметричный, обратный и в ширину через очередь. Симметричный обход дерева поиска выдаёт ключи по возрастанию, и это самая быстрая проверка, что структура собрана верно.

from collections import deque

def bfs(root):
    queue = deque([root])
    while queue:
        node = queue.popleft()
        yield node.value
        queue.extend(c for c in (node.left, node.right) if c is not None)

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

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

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

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