Descrição do Problema

Dado o nó raiz de uma árvore binária, determine se ela é uma Árvore de Busca Binária (BST) válida.

Definição de BST válida:

• A subárvore esquerda de um nó contém apenas nós com valores menores que o valor do nó.
• A subárvore direita de um nó contém apenas nós com valores maiores que o valor do nó.
• Tanto a subárvore esquerda quanto a direita devem ser também árvores de busca binária.

Observação importante: Não é suficiente comparar um nó apenas com seus filhos imediatos. A propriedade de BST exige que todos os nós na subárvore esquerda sejam menores e todos na subárvore direita sejam maiores do que o nó atual.

Exemplos Ilustrativos

Exemplo 1:

Entrada: raiz = [2,1,3]
Saída: true

Explicação: A estrutura satisfaz a definição de BST.

Exemplo 2:

Entrada: raiz = [5,1,4,null,null,3,6]
Saída: false

Explicação: O nó raiz é 5. Seu filho direito é 4, mas o problema mais grave ocorre na subárvore direita, onde o nó 3 é menor que a raiz 5, violando a propriedade global da BST.

Exemplo 3 (Caso Comum de Erro):

Entrada: raiz = [5,4,6,null,null,3,7]
Saída: false

Explicação: Embora cada relação pai-filho pareça correta (4<5<6, 3<6<7), o nó 3 na subárvore direita é menor que a raiz 5, violando a propriedade da BST.

Abordagens de Solução

Abordagem 1: Percurso In-Order (Recomendada)

Princípio: O percurso in-order (esquerda → raiz → direita) de uma BST produz uma sequência estritamente crescente.

Passos:

1. Realize um percurso in-order na árvore.
2. Mantenha o registro do último valer visitado.
3. Se o valor atual for menor ou igual ao último valor, a árvore não é uma BST.
4. Caso contrário, atualize o último valor e continue o percurso.

Observação: A sequência deve ser estritamente crescente, sem valores repetidos.

Abordagem 2: Recursão com Limites Superior e Inferior

Princípio: Cada nó na árvore deve estar dentro de um intervalo válido (min, max) que se atualiza durante a travessia.

Passos:

1. Inicialmente, a raiz pode ter qualquer valor (intervalo de -∞ a +∞).
2. Ao recursar para a esquerda, o limite superior se torna o valor do nó atual.
3. Ao recursar para a direita, o limite inferior se torna o valor do nó atual.
4. Se o valor do nó atual estiver fora do intervalo, a árvore é inválida.

Utilize tipos de dados de maior precisão (como long ou int64) para evitar problemas de estouro numérico nos limites.

Abordagem 3: Percurso In-Order Iterativo

Esta é uma variação da Abordagem 1, mas utiliza uma pilha explicitamente para simular a recursão. É uma alternativa mais segura para árvores muito profundas, pois evita o estouro da pilha de chamadas de função.

Implementação do Código

Exemplo em Java

// Método 1: Percurso In-Order (Recursivo)
class VerificadorBST {
    private Long ultimoVisitado = null;

    public boolean ehValida(TreeNode raiz) {
        if (raiz == null) return true;
        if (!ehValida(raiz.esquerda)) return false;
        if (ultimoVisitado != null && raiz.valor <= ultimoVisitado) return false;
        ultimoVisitado = (long) raiz.valor;
        return ehValida(raiz.direita);
    }
}

// Método 2: Validação com Intervalos (Recursivo)
class VerificadorBSTComIntervalos {
    public boolean ehValida(TreeNode raiz) {
        return validar(raiz, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean validar(TreeNode no, long min, long max) {
        if (no == null) return true;
        if (no.valor <= min || no.valor >= max) return false;
        return validar(no.esquerda, min, no.valor) &&
               validar(no.direita, no.valor, max);
    }
}

Exemplo em Python

# Método 1: Percurso In-Order (Recursivo)
class Solucao:
    def isValidBST(self, raiz):
        self.ultimo_visitado = None
        return self._percorrer_em_ordem(raiz)

    def _percorrer_em_ordem(self, no):
        if no is None:
            return True
        if not self._percorrer_em_ordem(no.esquerda):
            return False
        if self.ultimo_visitado is not None and no.valor <= self.ultimo_visitado:
            return False
        self.ultimo_visitado = no.valor
        return self._percorrer_em_ordem(no.direita)

# Método 2: Validação com Intervalos (Recursivo)
class SolucaoComLimites:
    def isValidBST(self, raiz):
        return self._validar(raiz, float('-inf'), float('inf'))

    def _validar(self, no, minimo, maximo):
        if no is None:
            return True
        if no.valor <= minimo or no.valor >= maximo:
            return False
        return self._validar(no.esquerda, minimo, no.valor) and \
               self._validar(no.direita, no.valor, maximo)

Demonstração Passo a Passo

Para a árvore [5,1,4,null,null,3,6]:

Usando o Percurso In-Order:

Sequência de visitas: 1 → 5 → 3 → 4 → 6

Análise: Ao encontrar 3 depois de 5, a condição de crescimento estrito falha. A função retorna false.

Usando Limites de Intervalo:

• Nó raiz (5): Intervalo (-∞, ∞) - Válido.
• Filho esquerdo (1): Intervalo (-∞, 5) - Válido.
• Filho direito (4): Intervalo (5, ∞) - Inválido, pois 4 < 5. A validação falha imediatamente.

Note que, neste caso, a abordagem com limites pode detectar a invalidação em um nível mais alto da árvore.

Análise de Complexidade

Todas as abordagens visitam cada nó uma única vez, resultando em complexidade de tempo linear.

Considerações Finais

• Erro Comum: A validação de uma BST requer uma verificação global da orddenação, não apenas a relação entre um nó e seus filhos diretos.
• Tratamento de Limites: Para evitar erros em casos de teste com valores extremos, utilize tipos de dados com maior alcance (como long em Java/C++ ou float('inf') em Python).
• Variação: Se a definição permitisse valores duplicados (uma BST "não estrita"), a condição <= poderia ser alterada para <.