В следующей задаче нужно найти в BST значение, ближайшее к заданному числу. Например, дано дерево ниже и число 5 — нужно найти узел, который ближе всего к пятёрке.
Для этого не нужно обходить все узлы — в BST можно на каждом шаге отбрасывать половину дерева. Стоим в корне 8 — пятёрка меньше, значит более близкие значения точно в левом поддереве. Переходим в 3 — пятёрка больше, идём вправо. Переходим в 6 — пятёрка меньше, идём влево. На каждом шаге отбрасываем половину узлов.
Такой спуск работает за O(h), где h — высота дерева. Именно по такому принципу работают std::set / std::map в C++, TreeSet / TreeMap в Java и индексы в базах данных.
Переходи к задаче и попробуй применить направленный спуск для оптимального решения. Важно: так как всегда идём только в одну ветку, рекурсия тебе не понадобится и решить нужно без нее.