Nth value of a binary search tree

Question

I’ve been trying to create a recursive function from the function that lists a binary tree in order.

This function would return the term N-th, in order, from a binary search tree.

Each node is in the following format:

typedef struct nodo
{
    int Elemento;

    struct Nodo *Esquerda;

    struct Nodo *Direita;

}Nodo;

Function that lists the elements of a tree in order, and which I am basing myself on.

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

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

            ListarEmOrdem(T->Direita);
        }
    }

Example of the function:

Entrada: ponteiro para a raíz duma árvore e N
Saída: N-elemento

Elements of a tree in order: 2,5,8,44 e 78

se F(T,4)

então, F(T,4) retorna = `44`

How is the procedure?

Answer 1

I saw the @pcccj reply and agree with what it says, about returning the item, and not just write down its value. There are several ways to do this, from a genius algorithm that masterfully manipulates the return of the search function to a simple algorithm that makes use of C’s tools.

Since 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 whole tree when you reach the position you would like.

For control, it uses 2 pointers-to-pointers, so that each sub-call of the function controls the same values. This is the part where I trade a genius algorithm for actually using language tools. It works like a dream!

At the end of the day, the end result is closer than you would naturally imagine:

1. walk through the tree

2. for each element add one to the counter

3. if the meter is equal to the position you want

   4. return the element

If you want to know more about pointers: http://www.mtm.ufsc.br/~Azeredo/cursoC/aulas/c600.html

Answer 2

A super simple way to get around the difficulties of this problem is to use global variables for the search parameters and return value pro, which allows you to keep the recursive function focused exclusively on 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 don’t want to use global, you can package the state in 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 legal thing would be 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 locality of the struct version. Unfortunately, C does not have this feature.

Other than that, you can also add an optimization to stop recursion after you find the element you’re looking for. There are many ways to do this, this one is just an 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);
    }
}

Answer 3

The ideal would be for the function to return the final value (T->Element) through a return, and not of a printf(). But I had no idea.

Maybe someone can complete.

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;
    }
}