Escreva uma função não-recursiva que retorne o menor valor de uma árvore binária (não ordenada)

Passo 1

A questão pede para escrever uma função iterativa (não-recursiva) que percorra uma árvore binária genérica (não ordenada) e retorne o menor valor armazenado em qualquer dos seus nós. O conteúdo principal aqui é varredura completa de árvore (tree traversal) usando uma estrutura auxiliar (pilha ou fila).

Passo 2

Vamos representar cada nó da árvore com um objeto que tenha os atributos valor, esquerda e direita. A função terá assinatura como menor_valor(arvore) e receberá a raiz da árvore. Para percorrer sem recursão, vamos usar uma pilha (stack) que armazena nós ainda a visitar.

Passo 3

Inicializamos verificando se a raiz é nula. Se for, podemos retornar None ou lançar uma exceção, pois não há valor a retornar. Caso contrário, criamos a pilha contendo apenas o nó raiz e definimos min_val igual a arvore.valor.

Passo 4

Enquanto a pilha não estiver vazia, retiramos (pop) o nó do topo. Comparamos o valor desse nó com min_val e atualizamos min_val caso seja menor. Em seguida, empilhamos seus filhos não nulos (primeiro esquerda, depois direita, ou vice-versa — a ordem não afeta o resultado).

Passo 5

Quando a pilha esvaziar, já teremos visitado todos os nós. Neste ponto, min_val conterá o menor valor encontrado, e podemos retorná-lo.

Resposta

def menor_valor(arvore):
# Se a árvore estiver vazia, não há valor a retornar
if arvore is None:
return None
# Inicializa min_val com o valor da raiz e prepara a pilha
min_val = arvore.valor
stack = [arvore]

# Percorre toda a árvore de forma iterativa
while stack:
    nodo = stack.pop()
    # Atualiza o menor valor se encontrar um valor menor
    if nodo.valor < min_val:
        min_val = nodo.valor
    # Empilha filhos não nulos para continuar a varredura
    if nodo.direita is not None:
        stack.append(nodo.direita)
    if nodo.esquerda is not None:
        stack.append(nodo.esquerda)

return min_val

Exercícios relacionados