K-ésimo elemento más pequeño

Lección 12 de 16 del curso Árbol AVL - Serie de Estructuras de Datos #10 de Coddy.

Los siguientes desafíos utilizan la clase AVLTree terminada que acabas de construir, proporcionada como un archivo bloqueado. Cada desafío incluye un nuevo archivo solution donde escribes una función que USA el árbol.

Un recorrido in-order de cualquier árbol de búsqueda binaria (las rotaciones no cambian esto) visita los valores en orden ordenado. Por lo tanto, el k-ésimo valor más pequeño es simplemente el elemento en el índice k - 1 de ese recorrido.

Desafío

Fácil

Escribe una función kthSmallest(tree, k) que devuelva el k-ésimo valor más pequeño en el árbol (indexado desde 1). Puedes asumir que k es válido.

Pruébalo tú mismo

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "avltree.h"
#include "solution.h"

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line1[4096];
    fgets(line1, sizeof(line1), stdin);
    char* tok = strtok(line1, " \n");
    while (tok != NULL) {
        AVLTree_insert(tree, atoi(tok));
        tok = strtok(NULL, " \n");
    }
    char line2[256];
    fgets(line2, sizeof(line2), stdin);
    int p0 = atoi(strtok(line2, " \n"));
    int result = kthSmallest(tree, p0);
    printf("%d\n", result);
    return 0;
}