Padrão 3: Árvore de busca binária (BST)
Uma BST é uma árvore binária com uma regra de ouro: para todo nó, tudo à esquerda é menor e tudo à direita é maior. Essa única regra dá busca, inserção e remoção em O(h) — e revela uma propriedade mágica na travessia em-ordem.
Tente primeiro: Validate Binary Search Tree
Antes de ler a teoria, tente resolver. Pode começar pela força bruta, pode errar — a ideia é sentir o problema. A teoria vem logo abaixo.
Verifique se uma árvore binária é uma BST válida: para todo nó, todos os valores da subárvore esquerda são menores que ele, e todos os da direita são maiores — recursivamente.
Exemplo: [2,1,3] → true. [5,1,4,null,null,3,6] → false (o 3 e o 6 estão à direita do 5, mas o 3 < 5).
Tentou? O erro nº 1 é comparar cada nó só com seus filhos diretos — e passar em árvores que não são BSTs válidas. A teoria abaixo mostra por que é preciso pensar em intervalos.
A teoria: a regra vale para a subárvore inteira
A regra da BST não é local ("maior que o pai") — é global: toda a subárvore esquerda de um nó é menor que ele, e toda a direita é maior. Por isso validar comparando só pai e filho falha:
5
/ \
1 4 ← 4 < 5? sim. Mas 4 está à DIREITA do 5...
/ \ ...e 3 < 5 também! NÃO é BST válida.
3 6
A forma correta: cada nó tem um intervalo permitido (mínimo, máximo) que
se estreita conforme você desce. Ao ir para a esquerda, o valor do nó
vira o novo máximo; ao ir para a direita, vira o novo mínimo:
valido(no, minimo, maximo):
se no é None → True
se não (minimo < no.val < maximo) → False
return valido(no.left, minimo, no.val) e valido(no.right, no.val, maximo)
A propriedade mágica: in-order = ordem crescente
Lembra das travessias (aula 1)? Numa BST, a travessia em-ordem (esquerda → nó → direita) visita os valores em ordem crescente. Faz sentido: você sempre visita tudo que é menor (esquerda) antes do nó, e tudo que é maior (direita) depois. Isso resolve uma família de problemas — Kth Smallest Element, por exemplo, é só "pare na k-ésima visita da travessia em-ordem".
Busca numa BST: O(h)
Procurar um valor numa BST é como a busca binária (seção Binary!): compare com o nó; se o alvo é menor, vá à esquerda; se maior, à direita. Cada passo descarta metade da árvore (uma subárvore inteira). Veja a busca descer — note como ela ignora ramos inteiros:
Custa O(h): log n numa árvore balanceada, n numa degenerada. É a mesma lógica de "cortar pela metade" da busca binária, agora na estrutura da árvore.
Repare no LCA (menor ancestral comum) numa BST: ele é o nó onde os valores
p e q "se separam" (um vai para a esquerda, o outro para a direita, ou um
deles é o próprio nó). A regra da BST diz exatamente para que lado cada um
está — então achamos o LCA em O(h) só descendo.
A lição
A regra da BST (esquerda < nó < direita, para toda a subárvore) é o que transforma uma árvore comum numa estrutura de busca. Sempre que vir "BST" no enunciado, pense: (1) posso usar a regra para descer só por um lado (busca O(h))? (2) a travessia em-ordem (crescente) ajuda?
🧠 Quiz de fixação
0/41. Qual é a regra que define uma BST?
2. Por que validar uma BST comparando cada nó só com seus filhos diretos está errado?
3. Que ordem a travessia em-ordem produz numa BST, e por quê?
4. Por que a busca numa BST é O(h)?
Resumo
- BST: esquerda < nó < direita, para toda a subárvore (regra global).
- Validar exige um intervalo (min, max) que se estreita ao descer — não só comparar pai/filho.
- Travessia em-ordem = crescente (resolve Kth Smallest).
- Busca/LCA em O(h), descendo só por um lado — a busca binária das árvores.
Próxima aula: reconstruir e serializar árvores.