Если бинарное дерево поиска не полностью сбалансировано, то вам нужно выполнить рекурсивный поиск, чтобы найти n-й наименьший элемент. Это может быть значительно ускорено за счет того, что каждый узел хранит количество подузлов, на которые указывает каждый из его указателей ветвления, эффективно превращая поиск в двоичный. Тем не менее, это добавляет накладные расходы на обновления дерева, так как теперь для каждой вставки или удаления требуется обход от листа к корню для обновления счетчиков узлов.
Кроме того, вы можете сохранить сбалансированное дерево и использовать ответ, приведенный выше.