Escreva uma função não-recursiva que retorne o k-ésimo menor valor de uma árvore binária de busca.

Passo 1

O enunciado pede uma função não-recursiva pra achar o k-ésimo menor elemento de uma árvore binária de busca. O conteúdo aqui é percurso em-ordem (in-order) em BST, pois esse percurso retorna os valores em ordem crescente, e a gente vai usar uma pilha pra simular a recursão.

Passo 2

Pra resolver, a gente vai empurrar todos os nós à esquerda do raiz numa pilha até chegar à folha mais à esquerda. Isso corresponde ao primeiro elemento em ordem.
Depois, repetimos: enquanto a pilha não estiver vazia e o contador for menor que k, fazemos pop do topo da pilha (é o próximo nó em ordem). A cada pop, incrementamos um contador. Se esse contador atingir k, esse nó é o k-ésimo menor e a gente retorna o valor dele.
Quando fazemos pop num nó, precisamos considerar o seu filho direito: colocamos ali na pilha e voltamos a empurrar toda a sua subárvore esquerda. Assim repetimos o passo 2 até achar o k-ésimo.

Passo 3

Se a pilha esvaziar antes de chegar em k, significa que k é maior que o número de nós da árvore; podemos então retornar um erro ou algum valor especial.

Passo 4

Segue o código em Python como exemplo de implementação:

Resposta

def kth_smallest(root, k):
    # root: nó da BST; k: inteiro positivo
    stack = []
    current = root
    count = 0

    # Empurra todos os nós à esquerda
    while current:
        stack.append(current)
        current = current.left

    # Processa nós em ordem crescente
    while stack:
        node = stack.pop()
        count += 1
        if count == k:
            return node.val
        # Se houver subárvore direita, empurra-a e seus filhos à esquerda
        right = node.right
        while right:
            stack.append(right)
            right = right.left

    # Se k for maior que o número de nós
    raise ValueError('k maior que quantidade de nós da árvore')

Exercícios relacionados