Nth value of a binary search tree

I've seen the response from @pcccj and I agree with what it says, about returning the item , not just writing its value. There are a number of ways to do this, from a genius algorithm that manipulates the return of the search function with mastery to a simple algorithm but using the C tools.

As I'm not that smart, here's a simple algorithm;)

#include<stdio.h>
#include<stdlib.h>

// Declara o formato dos nodos da árvore, e cria o tipo
struct nodo {
    int Elemento;
    struct nodo *Esquerda;
    struct nodo *Direita;
};

typedef struct nodo Nodo;

// Insere elementos na árvore
void InsereNodo(Nodo **raiz, Nodo *item) {
    if (!*raiz) {
        *raiz = item;
        return;
    }

    if (item->Elemento < (*raiz)->Elemento)
        InsereNodo(&(*raiz)->Esquerda, item);
    else
        InsereNodo(&(*raiz)->Direita, item);
}

// Escreve o valor de cada elemento da árvore, in-order
void ListarEmOrdem(Nodo *raiz){
    if (raiz->Esquerda)
        ListarEmOrdem(raiz->Esquerda);

    printf("%d\n", raiz->Elemento);

    if (raiz->Direita)
        ListarEmOrdem(raiz->Direita);
}

// Percorre a árvore, por profundidade, parando ao encontrar o n-ésimo elemento
void ProcuraProfundidade(Nodo *raiz, int **posicao, int limite, Nodo **NodoEncontrado){
    if (raiz->Esquerda)
        ProcuraProfundidade(raiz->Esquerda, posicao, limite, NodoEncontrado);

    if (!*NodoEncontrado){
        if((**posicao)++ == limite){
            *NodoEncontrado = raiz;
            return;
        }

        if (raiz->Direita)
            ProcuraProfundidade(raiz->Direita, posicao, limite, NodoEncontrado);
    }
}

// Função intermediária de busca; mantém uma assinatura decente e lida com exceções
Nodo* Procura(Nodo *raiz, int posicao){
    if (posicao < 1)
        return NULL;
    else if (!raiz)
        return raiz;
    else {
        Nodo *NodoEncontrado = NULL;
        int *inicial = malloc(sizeof(int));
        *inicial = 1;
        ProcuraProfundidade(raiz, &inicial, posicao, &NodoEncontrado);
        return NodoEncontrado;
    }
}


int main(int argc, char **argv){
    Nodo *raiz, *atual;
    int i;

    raiz = NULL;

    // Cria uma árvore de 7 elementos aleatórios
    for (i = 0; i < 7; i++) {
        atual = (Nodo*)malloc(sizeof(Nodo));
        atual->Esquerda = atual->Direita = NULL;
        atual->Elemento = rand();
        InsereNodo(&raiz, atual);
    }

    // Escreve todos os elementos da árvore
    printf("Lista de elementos\n----------\n");
    ListarEmOrdem(raiz);

    // Procura por todas as posições, de 0 a n+1, para cobrir pelo menos 2 casos de erro
    printf("\n\nResultado das buscas\n----------\n");
    for (i = 0; i <= 8; i++){
        atual = Procura(raiz, i);
        if (atual)
            printf("%d: %d\n", i, atual->Elemento);
        else
            printf("%d: %p\n", i, atual);
    }

    return EXIT_SUCCESS;
}

Basically, the search works exactly the same as the writing function, but adds stop conditions to avoid fetching the entire tree when you reach the position you'd like.

For control, use 2 pointers so that each sub-call of the function controls the same values. This is the part where I exchange a genius algorithm for using language tools effectively. It works that's a wonder!

Ultimately, the end result is closer to what you would naturally imagine:

If you want to know more about pointers: link

A super simple way to get around the difficulties of this problem is to use global variables for the search parameters and pro return value, which allows to keep the recursive function focused exclusively on the iteration:

static int n_arvore;
static int k_alvo;
static int k_esimo_elemento;

void percorrerArvore(Nodo* T){
    if (T != NULL){
        percorrerArvore(T->Esquerda);

        if(n_arvore == k_alvo){ k_esimo_elemento = T->Elemento; }    
        +n_arvore;

        percorrerArvore(T->Direita);
    }
}

void kEsimoElemento(int k, Nodo * T){
    n_arvore = 0;
    k_alvo = k;
    percorrerArvore(T);
    if(k < n_arvore){
        return k_esimo_elemento;
    }else{
        /* Árvore não tem elementos o suficiente */
    }
}

If you do not want to use globals, you can package the state into a struct:

struct kElemState {
    int n_arvore;
    int k_alvo;
    int k_esimo_elemento;
}

void percorrerArvore(struct kElemState *state, Nodo* T){ ... }

void kEsimoElemento(int k, Nodo * T){
    struct kElemState s;
    s.n_arvore = 0;
    s.k_alvo = k;
    percorrerArvore(&s, T);
    if(k < s.n_arvore){
        return s.k_esimo_elemento;
    }else{
        /* Árvore não tem elementos o suficiente */
    }
}

The same would be true if we could declare the function percorreArvore within the function nEsimoElemento , with n_arvore being local variables of nEsimoElemento . This would combine the simplicity of the version with global variables with the locale of the version with struct. Unfortunately, C does not have this functionality.

Otherwise, you can also add an optimization to stop recursion once you find the element you are looking for. There are many ways to do this, here is just one example:

int percorrerArvore(Nodo* T){
    if (T != NULL){
        percorrerArvore(T->Esquerda);

        if(k_alvo < n_arvore){ return; }

        if(k_alvo == n_arvore){ k_esimo_elemento = T->Elemento; }    
        +n_arvore;

        if(k_alvo < n_arvore){ return; }

        percorrerArvore(T->Direita);
    }
}

The ideal would be for the function to return the final value (T>> Element) through return , rather than printf() . But I had no idea.

Maybe someone can complete it.

int Kth(Nodo* T, int cont, int pos)
{
    if (T != NULL)
    {
        cont = Kth(T->Esquerda, cont, pos);

        if(cont != 0)
        {
            if(cont == pos)
            {
                printf("%d\n",T->Elemento);

                return T->Elemento;///o ideal seria que ele retornasse o valor de T->Elemento por aqui, e não pelo PRINTF, só que n sei como fazer
            }

            cont = cont +1;
        }

        cont = Kth(T->Direita, cont, pos);

        return cont;

    }
    else
    {
        if(cont == 0)
            return (cont +1);

        return cont;
    }
}