K-е по величине в дереве поиска

Средняя

Дан корень root двоичного дерева поиска: у каждой вершины все значения в левом поддереве меньше её значения, а в правом — больше. Дано также число rank. Верните значение, которое окажется на месте rank, если выписать все значения дерева по возрастанию (нумерация с единицы). Подумайте, как быть, если дерево часто меняется, а такой запрос приходит постоянно.

Пример 1

root=tree_node([20, 10, 30, 5, 15, None, 40]), rank=4 → 20

По возрастанию значения идут так: 5, 10, 15, 20, 30, 40. Четвёртое — 20.

Пример 2

root=tree_node([7, None, 9, 8]), rank=1 → 7

Меньше всех корень 7: левого поддерева у него нет.

Ограничения

Число вершин n — от 1 до 10⁴
1 ≤ rank ≤ n
0 ≤ Node.val ≤ 10⁴
Все значения различны, дерево — дерево поиска

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Tree Depth-First Search Binary Search Tree Binary Tree

Вход

root=tree_node([20, 10, 30, 5, 15, None, 40]), rank=4

Ожидается

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 43 теста на сервере, включая скрытые.