Este artigo aborda três desafios fundamentais envolvendo estruturas de árvores binárias, com foco em otimizações específicas para árvores de busca binária (BST) e estratégias recursivas robustas para árvores genéricas.

Diferença Absoluta Mínima entre Nós em uma BST

Dado o nó raiz de uma árvore de busca binária, calcule a menor diferença absoluta entre os valores de quaisquer dois nós distintos. A propriedade fundamental da BST — onde um percurso em ordem produz uma sequência ordenada — permite resolver esse problema em tempo linear sem necessidade de armazenamento adicional.

A abordagem consiste em realizar uma travessia em ordem (in-order), mantendo referência ao valor do nó anterior visitado. Em cada passo, calcula-se a diferença entre o valor atual e o anterior, atualizando o mínimo global sempre que uma diferença menor for encontrada.

class Solution {
    private Integer valorAnterior = null;
    private int diferencaMinima = Integer.MAX_VALUE;

    public int minDiffInBST(TreeNode raiz) {
        percorrerEmOrdem(raiz);
        return diferencaMinima;
    }

    private void percorrerEmOrdem(TreeNode no) {
        if (no == null) return;

        percorrerEmOrdem(no.left);

        if (valorAnterior != null) {
            int diff = no.val - valorAnterior;
            if (diff < diferencaMinima) {
                diferencaMinima = diff;
            }
        }
        valorAnterior = no.val;

        percorrerEmOrdem(no.right);
    }
}

Identificação de Todos os Valores Modais em uma BST

Dada uma BST que pode conter valores duplicados, retorne todos os elementos que ocorrem com a maior frequência. Ao contrário de soluções baseadas em hashmaps, aproveita-se a ordenação implícita da travessia em ordem para detectar agrupamentos contíguos de valores iguais, reduzindo o uso de memória e evitando sobrecarga de estruturas auxiliares.

O algoritmo rastreia dinamicamente a contagem corrente do valor atual, compara-a com a contagem máxima observada até então, e atualiza a lista de modas conforme necessário — limpando-a ao encontrar uma nova frequência superior ou adicionando ao conjunto ao igualar a frequência máxima.

class Solution {
    private Integer valorPrecedente = null;
    private int contagemAtual = 0;
    private int frequenciaMaxima = 0;
    private final List<Integer> resultados = new ArrayList<>();

    public int[] findMode(TreeNode raiz) {
        explorarEmOrdem(raiz);
        return resultados.stream().mapToInt(Integer::intValue).toArray();
    }

    private void explorarEmOrdem(TreeNode no) {
        if (no == null) return;

        explorarEmOrdem(no.left);

        if (valorPrecedente != null && no.val == valorPrecedente) {
            contagemAtual++;
        } else {
            contagemAtual = 1;
        }

        if (contagemAtual > frequenciaMaxima) {
            frequenciaMaxima = contagemAtual;
            resultados.clear();
            resultados.add(no.val);
        } else if (contagemAtual == frequenciaMaxima) {
            resultados.add(no.val);
        }

        valorPrecedente = no.val;

        explorarEmOrdem(no.right);
    }
}

Localização do Ancestral Comum Mais Profundo

Para duas referências arbitrárias de nós em uma árvore binária não ordenada, determine o nó mais profundo que seja ancestral de ambos. A solução emprega uma estratégia recursiva pós-ordem: cada chamada retorna null se nenhum dos nós-alvo for encontrado na subárvore, ou retorna a referência do nó correspondente assim que localizado. O ancestral comum é identificado quando ambas as chamadas recursivas (esquerda e direita) retornam valores não nulos — indicando que os dois nós estão em subárvores distintas do nó atual.

Caso um dos nós seja exatamente o nó atual, e o outro esteja em alguma subárvore descendente, o nó atual também é o ancestral comum — condição capturada pela verificação inicial na assinatura recursiva.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode raiz, TreeNode alvoA, TreeNode alvoB) {
        if (raiz == null || raiz == alvoA || raiz == alvoB) {
            return raiz;
        }

        TreeNode esquerda = lowestCommonAncestor(raiz.left, alvoA, alvoB);
        TreeNode direita = lowestCommonAncestor(raiz.right, alvoA, alvoB);

        if (esquerda != null && direita != null) {
            return raiz;
        }
        return (esquerda != null) ? esquerda : direita;
    }
}