Escreva uma função que retorna verdadeiro se uma árvore é binária de busca e falso caso contrário

Passo 1

O enunciado pede uma função que receba a raiz de uma árvore binária e devolva verdadeiro se ela obedecer às propriedades de uma árvore binária de busca (BST) e falso caso contrário. Para resolver isso, vamos usar conceitos de recursão e intervalos de valores (limites mínimo e máximo) que cada nó pode assumir.

Passo 2

Em uma BST, para todo nó com valor v:
  • Todos os valores na subárvore esquerda devem ser menores que v.
  • Todos os valores na subárvore direita devem ser maiores que v.
    Isso vale recursivamente para cada nó, ou seja, cada subárvore também deve satisfazer a condição de BST.

Passo 3

A ideia do algoritmo é passar, em cada chamada recursiva, dois limites minimo e maximo. Inicialmente, definimos esses limites como -infty e +infty. Ao visitar um nó de valor v:
  1. Se v não estiver no intervalo (minimo,,maximo), retornamos falso.
  2. Chamamos recursivamente o filho esquerdo com limites (minimo,,v) e o filho direito com limites (v,,maximo).
  3. A árvore é BST somente se ambas as chamadas retornarem verdadeiro.

Passo 4

Segue o pseudocódigo da função em estilo Python. A função principal é eh_bst(raiz), que invoca um helper recursivo com os limites iniciais.

Passo 5

No pior caso, cada nó é visitado exatamente uma vez, e em cada visita fazemos apenas comparações e duas chamadas recursivas. A complexidade de tempo é O(n), onde n é o número de nós da árvore. A complexidade de espaço (além da árvore) é a profundidade da recursão, no pior caso O(n) em árvores degeneradas e O(h) em árvores balanceadas, sendo h a altura da árvore.

Resposta

def eh_bst(raiz):
def helper(no, minimo, maximo):
if no is None:
return True
# Se o valor do nó não está dentro dos limites válidos, não é BST
if no.valor <= minimo or no.valor >= maximo:
return False
# Verifica recursivamente as subárvores com novos limites
return (helper(no.esquerda, minimo, no.valor)
and helper(no.direita, no.valor, maximo))
# Limites iniciais são -infinito e +infinito
return helper(raiz, float(’-inf’), float(‘inf’))

Exercícios relacionados