Как выглядит поиск по диапазону в деревьях поиска

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

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

Как отвечать

Спускаемся от корня и заходим только в те поддеревья, где могут лежать ключи из [low, high]:

• левое поддерево: имеет смысл, только если node.Val > low, иначе всё слева меньше нижней границы;
• текущий узел: попадает в результат при low <= node.Val && node.Val <= high;
• правое поддерево: только если node.Val < high.

В порядке «лево, узел, право» результат выходит отсортированным: это симметричный обход с отсечениями. Сложность O(h + k), где h это высота дерева, а k число найденных ключей. В сбалансированном дереве (красно-чёрное, AVL) получается O(log n + k), в выродившемся в список O(n). Быстрее k нельзя, если ключи нужно вернуть.

В Go результат удобно копить в срезе. Начиная с Go 1.23 диапазон можно отдать итератором iter.Seq[int]: вызывающий пишет for v := range tree.Range(lo, hi), а если он выйдет из цикла раньше, yield вернёт false, и обход остановится.

Чтобы считать количество без перечисления, в узле хранят размер поддерева, тогда ответ за O(log n) как разность двух рангов. В базах данных та же задача решается B+-деревом: спуск к нижней границе и проход по связанным листьям.

Упорядоченного дерева в стандартной библиотеке Go нет, map порядок не хранит. На практике берут github.com/google/btree или github.com/tidwall/btree, где есть обход по диапазону.

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

Называют сложность O(log n) без оговорок. Логарифм покрывает только спуск, вывод k элементов добавляет O(k), и при диапазоне на всё дерево это O(n).

Обходят всё дерево и фильтруют по условию. Результат верный, но свойство дерева поиска не используется, и интервьюер это сразу видит.

Путают строгие и нестрогие сравнения: теряют ключи, равные границам, или не учитывают, куда дерево кладёт дубликаты. Если равные ключи уходят влево, условие node.Val > low пропустит их.