Найти k-й наименьший элемент в бинарном дереве поиска оптимальным способом

Question

Мне нужно найти k-й наименьший элемент в бинарном дереве поиска без использования статической / глобальной переменной. Как добиться этого эффективно? Решение, которое я имею в виду, заключается в выполнении операции в O (n), наихудшем случае, поскольку я планирую выполнить обход по всему дереву. Но в глубине души я чувствую, что здесь не используется свойство BST. Правильно ли мое предположение или есть лучшее?

Answer 1

 public int printInorder(Node node, int k) 
    { 
        if (node == null || k <= 0) //Stop traversing once you found the k-th smallest element
            return k; 

        /* first recur on left child */
        k = printInorder(node.left, k); 

        k--;
        if(k == 0) {  
            System.out.print(node.key);
        }

        /* now recur on right child */
        return printInorder(node.right, k);
    } 

Этот рекурсивный алгоритм Java останавливает рекурсию, как только найден k-й наименьший элемент.

Answer 2

Для бинарного дерева поиска, обход по порядку вернет элементы ... в порядке.

Просто выполните обход по порядку и остановитесь после обхода k элементов.

O (1) для постоянных значений k.