Задача с собеса в Авито

Условие задачи
Дано бинарное поисковое дерево (BST) и число k. Нужно вернуть значение k-го по величине элемента в этом дереве (нумерация с 1).
для любой вершины: все значения в левом поддереве меньше её значения; все значения в правом поддереве больше её значения.

Решение
Очень важное свойство BST: если обойти дерево в порядке
лево -> корень -> право (симметричный / inorder обход),
то значения вершин будут посещаться в отсортированном по возрастанию порядке.

Значит, k-й посещённый элемент при таком обходе — это и есть k-й по величине.
Делаем итеративный inorder-обход через стек:
1. Идём по указателю node максимально влево, по пути кладём все вершины в стек.
2. Когда упёрлись в None, достаём вершину из стека — это следующий по возрастанию элемент.
3. Уменьшаем k. Если k стало 0 — возвращаем значение этой вершины.
4. Переходим в правого ребёнка и повторяем.
Так мы не храним все элементы, а только путь в стеке.

Сложность:
по времени: O(h + k), где h — высота дерева (в худшем O(n), для сбалансированного O(log n)), по памяти: O(h) на стек

Код:

class Solution:
def kthSmallest(self, root: Optional['TreeNode'], k: int) -> int:
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
k -= 1
if k == 0:
return node.val
node = node.right


@algoses