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.
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')