Validando BST e Propriedades da Ordem
Valide uma árvore binária como BST usando limites mínimo e máximo propagados pela árvore e verificando se o percurso em ordem produz uma sequência ordenada.
Validando BST e Propriedades da Ordem é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
O problema de validação de BST
Validar BST (LeetCode #98) é um problema clássico de entrevistas que confunde muitos candidatos. A abordagem ingênua verifica apenas se o valor de cada nó é maior que o filho esquerdo e menor que o filho direito, mas essa verificação local é insuficiente. Um nó de uma subárvore pode satisfazer a regra local e ainda violar a propriedade global de BST. A solução correta propaga limites mínimo e máximo válidos pela árvore.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Why local check fails:
# 5
# / \
# 1 4
# / \
# 3 6
# Node 4's children (3, 6) satisfy local rule,
# but 4 < 5 and is in the RIGHT subtree -- BST violated!
print('Local check is insufficient -- use min/max bounds')Abordagem dos limites mínimo/máximo
Transmita os limites inferior e superior pelas chamadas recursivas. Em cada nó, verifique se low < node.val < high. Ao fazer a chamada recursiva à esquerda, atualize o limite superior para node.val (a subárvore esquerda deve conter valores menores). Ao fazer a chamada recursiva à direita, atualize o limite inferior para node.val (a subárvore direita deve conter valores maiores). Comece com low = -infinity e high = +infinity.
def is_valid_bst(root, low=float('-inf'), high=float('inf')):
if not root:
return True
if not (low < root.val < high):
return False
return (is_valid_bst(root.left, low, root.val) and
is_valid_bst(root.right, root.val, high))
# Valid BST:
valid = TreeNode(5)
valid.left = TreeNode(3)
valid.right = TreeNode(7)
print(is_valid_bst(valid)) # True
# Invalid BST (3 is in wrong subtree conceptually):
invalid = TreeNode(5)
invalid.left = TreeNode(1)
invalid.right = TreeNode(4)
invalid.right.left = TreeNode(3)
invalid.right.right = TreeNode(6)
print(is_valid_bst(invalid)) # False (4 < 5 in right subtree)Validação por travessia em ordem
Uma abordagem alternativa de validação usa a propriedade de ordenação da travessia em ordem da BST: colete a sequência em ordem e verifique se ela é estritamente crescente. Essa abordagem é elegante e fácil de compreender. No entanto, ela usa espaço adicional O(n) para armazenar a sequência. Uma versão otimizada usa um único ponteiro prev durante a travessia para verificar cada par sem armazenar a sequência inteira.
def is_valid_bst_inorder(root):
prev = [float('-inf')]
def inorder(node):
if not node:
return True
if not inorder(node.left):
return False
if node.val <= prev[0]: # not strictly increasing
return False
prev[0] = node.val
return inorder(node.right)
return inorder(root)
valid = TreeNode(5)
valid.left = TreeNode(3)
valid.right = TreeNode(7)
valid.left.left = TreeNode(1)
valid.left.right = TreeNode(4)
print(is_valid_bst_inorder(valid)) # True
invalid = TreeNode(5)
invalid.left = TreeNode(6) # 6 > 5 in left subtree!
print(is_valid_bst_inorder(invalid)) # FalseComparação entre as duas abordagens de validação
A abordagem dos limites mínimo/máximo tem tempo O(n) e espaço O(h) (apenas os limites na pilha de chamadas). A abordagem do ponteiro anterior em ordem também tem tempo O(n) e espaço O(h). Ambas são ideais. A abordagem dos limites mínimo/máximo é mais geral e funciona de forma clara quando estendida a problemas com restrições adicionais. Em entrevistas, esteja preparado para apresentar as duas e discutir as vantagens e desvantagens — demonstrar conhecimento de alternativas é um forte indicativo de domínio.
# Both approaches:
# Time: O(n) -- visit each node once
# Space: O(h) -- call stack depth
# h = O(log n) balanced, O(n) skewed
# When to choose which:
# min/max bounds:
# - Cleaner for trees with constraints beyond BST
# - No global state (purely functional)
# in-order prev:
# - More intuitive (sorted sequence check)
# - Easier to convert to iterative with a stack
print('Both O(n) time, O(h) space -- choose by clarity')Recuperar BST: dois nós trocados
Recuperar BST (LeetCode #99) corrige uma BST na qual exatamente dois nós foram trocados. Durante a travessia em ordem, uma BST corretamente ordenada produz uma sequência ordenada. Se dois nós forem trocados, haverá uma ou duas violações em que prev.val > current.val. O primeiro nó da primeira violação e o segundo nó da última violação são os dois nós em posições incorretas — troque seus valores.
def recover_tree(root):
first = second = prev = None
def inorder(node):
nonlocal first, second, prev
if not node:
return
inorder(node.left)
if prev and prev.val > node.val:
if not first:
first = prev # first violator
second = node # always update second
prev = node
inorder(node.right)
inorder(root)
# Swap values of the two misplaced nodes
if first and second:
first.val, second.val = second.val, first.val
root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.right.left = TreeNode(2) # 2 and 3 are swapped
recover_tree(root)
print(root.val, root.right.left.val) # 2, 3 (fixed)BST em ordem para vetor ordenado
Converter uma BST em um vetor ordenado é trivial: faça uma travessia em ordem e colete os valores. Essa operação, com tempo O(n) e espaço O(n), é uma maneira rápida de aplicar algoritmos para vetores ordenados (pesquisa binária, dois ponteiros) a dados de uma BST. Ela costuma ser uma etapa intermediária em problemas de BST com várias partes, como «mesclar duas BSTs» ou «encontrar a mediana de uma BST».
def bst_to_sorted_array(root):
result = []
def inorder(node):
if not node:
return
inorder(node.left)
result.append(node.val)
inorder(node.right)
inorder(root)
return result
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)
print(bst_to_sorted_array(root)) # [1, 2, 3, 4, 5, 6, 7]Mesclando duas BSTs
Para mesclar duas BSTs em um único vetor ordenado, converta cada uma em um vetor ordenado em O(n) e O(m), respectivamente, e então mescle os dois vetores ordenados usando a etapa de intercalação do algoritmo de ordenação por intercalação em O(n+m). Tempo total: O(n+m). Se precisar do resultado como uma BST equilibrada, passe o vetor ordenado mesclado ao algoritmo de conversão de vetor ordenado para BST. Essa decomposição em subproblemas simples é característica de uma solução clara e fácil de apresentar em uma entrevista.
def merge_two_bsts(root1, root2):
def inorder(node, arr):
if not node:
return
inorder(node.left, arr)
arr.append(node.val)
inorder(node.right, arr)
arr1, arr2 = [], []
inorder(root1, arr1)
inorder(root2, arr2)
# Merge two sorted arrays
merged = []
i = j = 0
while i < len(arr1) and j < len(arr2):
if arr1[i] <= arr2[j]:
merged.append(arr1[i]); i += 1
else:
merged.append(arr2[j]); j += 1
merged.extend(arr1[i:])
merged.extend(arr2[j:])
return merged
r1 = TreeNode(2); r1.left = TreeNode(1); r1.right = TreeNode(4)
r2 = TreeNode(3); r2.left = TreeNode(0); r2.right = TreeNode(5)
print(merge_two_bsts(r1, r2)) # [0, 1, 2, 3, 4, 5]Contar nós no intervalo de uma BST
Conte quantos nós têm valores no intervalo [low, high]. Uma varredura em ordem por força bruta leva O(n). A versão que aproveita a BST elimina ramos desnecessários: se o valor do nó atual for menor que o limite inferior, não faz sentido verificar a subárvore esquerda (todos os valores nela também são menores que o limite inferior). Da mesma forma, elimine a subárvore direita quando o valor atual for maior que o limite superior. O caso médio é O(log n + k), em que k é a quantidade de nós correspondentes.
def range_sum_bst(root, low, high):
if not root:
return 0
total = 0
if low <= root.val <= high:
total += root.val
if root.val > low: # left subtree may have values >= low
total += range_sum_bst(root.left, low, high)
if root.val < high: # right subtree may have values <= high
total += range_sum_bst(root.right, low, high)
return total
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
print(range_sum_bst(root, 7, 15)) # 7 + 10 + 15 = 32Valores duplicados e BST estrita versus não estrita
O invariante padrão de uma BST usa desigualdade estrita: os valores da subárvore esquerda são estritamente menores e os da subárvore direita são estritamente maiores. Alguns problemas permitem duplicatas, colocando-as na subárvore esquerda (esquerda <= raiz) ou na subárvore direita (raiz < direita). Ao validar BSTs, sempre verifique a definição apresentada no enunciado. A abordagem dos limites mínimo/máximo trata ambas as variantes ajustando se a verificação do limite deve ser estrita ou inclusiva.
# Strict BST (LeetCode default): left < root < right
def is_valid_strict(root, lo=float('-inf'), hi=float('inf')):
if not root:
return True
if not (lo < root.val < hi): # STRICT inequalities
return False
return (is_valid_strict(root.left, lo, root.val) and
is_valid_strict(root.right, root.val, hi))
# Non-strict BST (allows duplicates in right): left <= root < right
def is_valid_nonstrict(root, lo=float('-inf'), hi=float('inf')):
if not root:
return True
if not (lo <= root.val < hi): # NOTE: <= for left side
return False
return (is_valid_nonstrict(root.left, lo, root.val + 1) and
is_valid_nonstrict(root.right, root.val, hi))
print('Always clarify strict vs non-strict with interviewer')A travessia em ordem como ferramenta universal para BSTs
A travessia em ordem é o canivete suíço dos problemas de BST. Sempre que um problema de BST perguntar sobre ordem crescente, o k-ésimo elemento, consultas de intervalo ou propriedades de sequências, considere se uma varredura em ordem (ou em ordem inversa) fornece a resposta. A maioria dos problemas específicos de BST se reduz a: percorrer em ordem crescente e fazer algo a cada etapa. Reconhecer rapidamente essa correspondência é uma habilidade importante em entrevistas.
# Problems solved elegantly with in-order:
# 1. Validate BST: check prev <= curr during in-order
# 2. Kth smallest: count k steps in in-order
# 3. Kth largest: count k steps in REVERSE in-order
# 4. Closest value to target: find crossover in in-order
# 5. BST to sorted array: collect in-order into list
# 6. Recover BST: find 1-2 violations in in-order
# 7. Sum of range [lo, hi]: accumulate during in-order
# The key insight: in-order visits BST nodes in sorted order.
# All sorted-order reasoning translates to in-order DFS.
print('In-order = sorted access = foundation of BST reasoning')Valor mais próximo em uma BST
Encontre o nó cujo valor é o mais próximo de um determinado alvo. Use a ordenação da BST: comece pela raiz, mantenha o controle do valor mais próximo encontrado até o momento e avance na direção do alvo (vá para a esquerda se o alvo for menor e para a direita se for maior). Essa abordagem O(h) é mais eficiente que uma varredura em ordem e demonstra o uso eficaz da propriedade da BST para eliminar partes do espaço de busca.
def closest_value(root, target):
closest = root.val
curr = root
while curr:
if abs(curr.val - target) < abs(closest - target):
closest = curr.val
if target < curr.val:
curr = curr.left
elif target > curr.val:
curr = curr.right
else:
break # exact match
return closest
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(closest_value(root, 3.714286)) # 4Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu: a validação de BST com limites mínimo/máximo (evitando o problema da verificação local), a alternativa do ponteiro anterior em ordem para validação e a travessia em ordem como ferramenta universal de BST para somas de intervalos, valores mais próximos e operações de mesclagem. A seguir, usaremos as propriedades da travessia em ordem da BST para encontrar o k-ésimo menor elemento.
Perguntas Frequentes
A aula “Validando BST e Propriedades da Ordem” é grátis?
Sim — o texto completo de “Validando BST e Propriedades da Ordem” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Validando BST e Propriedades da Ordem”?
Valide uma árvore binária como BST usando limites mínimo e máximo propagados pela árvore e verificando se o percurso em ordem produz uma sequência ordenada. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “Validando BST e Propriedades da Ordem”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Inserção e Busca em BST
- Exclusão em BST: Três Casos
- Validando BST e Propriedades da Ordem
- K-ésimo Menor, Soma de Intervalo e BST para Array Ordenado