Escreva uma função que encontra o valor máximo em uma árvore de busca binária.

Passo 1

O enunciado pede para escrever uma função que, dada uma árvore de busca binária (BST), retorna o maior valor armazenado nela. O conteúdo aqui é a propriedade de BST e a iteração em estruturas encadeadas.

Passo 2

Em uma BST, todo nó à direita de um dado nó contém valor maior do que o próprio nó. Logo, o maior valor da árvore estará sempre no nó mais à direita (aquele que não tem filho direito).
Podemos criar um algoritmo iterativo que comece na raiz e percorra sucessivamente o ponteiro direito até encontrar um nó cuja referência direita seja nula. Esse nó é o de maior valor.

Passo 3

A seguir está a implementação em pseudocódigo (estilo Python) da função find_max de forma iterativa:
def find_max(root):
if root is None:
raise ValueError(“Árvore vazia não tem máximo”)
current = root
while current.right is not None:
current = current.right
return current.value

Passo 4

A complexidade desse método é O(h), onde h é a altura da árvore. No pior caso (árvore degenerada), h = n e a complexidade é O(n). No melhor caso (árvore balanceada), h = log n e o método roda em O(log n).

Resposta

def find_max(root):
if root is None:
raise ValueError(“Árvore vazia não tem máximo”)
current = root
while current.right is not None:
current = current.right
return current.value

Exercícios relacionados