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

Passo 1

O enunciado pede uma função não-recursiva que, dada a raiz de uma árvore binária de busca (BST), retorne o menor valor armazenado nela. O conteúdo envolve a propriedade fundamental de uma BST e percursos iterativos.

Passo 2

Em uma árvore binária de busca, vale a regra: todo nó da subárvore esquerda tem valor menor que o nó atual. Logo, o menor valor está sempre no nó mais à esquerda (o “leftmost”).

Passo 3

Para resolver sem recursão, começamos no nó raiz e, enquanto existir um filho à esquerda, seguimos esse ponteiro. Quando chegarmos a um nó que não tem filho esquerdo, encontramos o menor valor.

Passo 4

Agora, basta transformar essa ideia num código simples em Python, tratando também o caso de árvore vazia para evitar erros.

Resposta

def find_min(root):
    """
    Retorna o menor valor de uma árvore binária de busca de forma não-recursiva.
    Se a árvore estiver vazia (root for None), retorna None.
    """
    if root is None:
        return None

    current = root
    while current.left is not None:
        current = current.left

    return current.value

Exercícios relacionados