¿Cómo puede determinar eficientemente el k-ésimo elemento máximo en un árbol de búsqueda binario?

Encontré que esta publicación tiene un análisis detallado de esta pregunta.

Pero en pocas palabras, debe tener en cuenta el hecho de que el recorrido en orden de un BST le dará todos los elementos en orden. Entonces, la idea básica aquí es hacer un recorrido en orden del árbol y luego generar el elemento k-ésimo.

Algunas personas almacenarán los resultados transversales en una matriz para encontrar el elemento k-ésimo. Sin embargo, es innecesario y usará memoria adicional. El truco aquí es usar un contador entero para indicar el índice actual del nodo que está visitando. Entonces, cuando el contador llega a k, sabes que este es el elemento k-ésimo en la matriz y puedes simplemente generarlo.

La manera simple sería simplemente hacer un recorrido inverso en orden. Algo como

  contador = 0
 función transversal (nodo)
   if (el nodo tiene un hijo correcto)
     transversal (derecha)
   contador + = 1
   si (contador == k)
     terminar // nodo es lo que quieres
   si (el nodo ha dejado hijo)
     transversal (izquierda)

En un árbol con n nodos, lo anterior tiene un peor caso de n + nk pasos (el árbol es solo una lista vinculada con la raíz siendo la más pequeña, debe ir hasta el final y volver) y un mejor caso de k pasos (el árbol es una lista vinculada con la raíz siendo la más grande, solo tiene que pasar al niño izquierdo k veces)