Inserção e Busca em BST
Implemente inserção e busca recursivas e iterativas, acompanhe o caminho pela árvore para várias chaves e analise a complexidade do pior caso em árvores não balanceadas.
Inserção e Busca em BST é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 1 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 DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
Definição da propriedade da BST
Uma árvore de busca binária satisfaz um único invariante: para cada nó, todos os valores da subárvore esquerda são estritamente menores que o valor do nó, e todos os valores da subárvore direita são estritamente maiores. Essa propriedade de ordenação — mantida em toda a subárvore, não apenas nos filhos imediatos — permite realizar busca, inserção e exclusão em O(log n) em árvores balanceadas e diferencia uma BST de uma árvore binária genérica.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Valid BST:
# 4
# / \
# 2 6
# / \ / \
# 1 3 5 7
# For node 4: left subtree {1,2,3} < 4 < right subtree {5,6,7}
# This holds recursively for EVERY node in the tree.
print('BST property: left < node < right at every level')Busca recursiva em BST
A busca em uma BST funciona como uma busca binária: compare o alvo com o valor do nó atual e faça a recursão na subárvore apropriada. Se o alvo for igual ao valor atual, retorne o nó. Se o alvo for menor, vá para a esquerda; se for maior, vá para a direita. Retorne um valor nulo ao alcançar um nó vazio. A complexidade temporal é O(h): O(log n) para árvores balanceadas e O(n) para árvores degeneradas.
def search_bst(root, val):
if not root:
return None # not found
if root.val == val:
return root # found
if val < root.val:
return search_bst(root.left, val)
else:
return search_bst(root.right, val)
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
result = search_bst(root, 2)
print(result.val if result else 'Not found') # 2
result = search_bst(root, 5)
print(result.val if result else 'Not found') # Not foundBusca iterativa em BST
A busca iterativa evita a sobrecarga da pilha de chamadas e é preferível em código de produção. Use um ponteiro curr que percorra a árvore para baixo, seguindo para a esquerda ou para a direita com base nas comparações. Trata-se de um simples laço while com três situações: nulo (não encontrado), correspondência (encontrado) ou ajuste da direção. A busca iterativa também tem complexidade O(h), mas usa espaço O(1), em vez de O(h) na versão recursiva.
def search_bst_iterative(root, val):
curr = root
while curr:
if val == curr.val:
return curr
elif val < curr.val:
curr = curr.left
else:
curr = curr.right
return None # not found
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
node = search_bst_iterative(root, 3)
print(node.val if node else 'Not found') # 3
print(search_bst_iterative(root, 9)) # NoneInserção recursiva em BST
A inserção em uma BST encontra a posição correta seguindo as mesmas decisões para a esquerda ou para a direita usadas na busca e, em seguida, anexa um novo nó à primeira posição null alcançada. A abordagem recursiva retorna a raiz (possivelmente nova) de cada subárvore: se o nó atual for nulo, retorne um novo TreeNode; caso contrário, atualize root.left ou root.right com o resultado da chamada recursiva. Esse padrão é claro e comum em soluções de entrevistas.
def insert_bst(root, val):
if not root:
return TreeNode(val) # create new node here
if val < root.val:
root.left = insert_bst(root.left, val)
elif val > root.val:
root.right = insert_bst(root.right, val)
# val == root.val: duplicate, do nothing (or handle as needed)
return root
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root = insert_bst(root, 1)
root = insert_bst(root, 5)
# Tree is now: 4, left=2(left=1), right=7(left=5)
print(root.right.left.val) # 5Inserção iterativa em BST
A inserção iterativa usa um ponteiro parent para acompanhar o último nó não nulo antes de chegar ao ponto de inserção. Percorra a árvore como na busca, mantendo o pai e a última direção seguida. Ao chegar a um valor nulo, anexe o novo nó ao lado apropriado do pai. Trate sempre separadamente o caso-limite de uma árvore vazia (a raiz é nula).
def insert_bst_iterative(root, val):
new_node = TreeNode(val)
if not root:
return new_node
curr = root
while True:
if val < curr.val:
if curr.left is None:
curr.left = new_node
break
curr = curr.left
else: # val > curr.val
if curr.right is None:
curr.right = new_node
break
curr = curr.right
return root
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root = insert_bst_iterative(root, 3)
print(root.left.right.val) # 3BST no pior caso: árvores degeneradas
Se você inserir uma sequência ordenada em uma BST, obterá uma árvore degenerada que se transforma em uma lista encadeada. A busca, a inserção e a exclusão passam a ter complexidade O(n). É por isso que existem BSTs balanceadas, como árvores AVL e árvores rubro-negras. Em entrevistas, mencione sempre esse pior caso quando perguntarem sobre a complexidade de uma BST: dizer “O(log n) em média e O(n) no pior caso para árvores não balanceadas” demonstra profundidade de entendimento.
# Inserting 1, 2, 3, 4, 5 into a BST:
# 1
# \
# 2
# \
# 3
# \
# 4
# \
# 5
# This is a right-skewed tree: search is O(n) not O(log n)
root = None
for val in [1, 2, 3, 4, 5]:
root = insert_bst(root, val)
# Verify the skew
node = root
depth = 0
while node:
depth += 1
node = node.right
print(f'Height: {depth}') # 5 = O(n), not O(log n)Encontrando o mínimo e o máximo
Em uma BST, o valor mínimo está sempre no nó mais à esquerda (continue indo para a esquerda até encontrar um valor nulo), e o máximo está no nó mais à direita. Essas operações O(h) são usadas com frequência como sub-rotinas na exclusão em BST (para encontrar o sucessor em ordem) e em consultas de intervalo. Dominar essas funções auxiliares economiza tempo em entrevistas.
def find_min(root):
while root.left:
root = root.left
return root
def find_max(root):
while root.right:
root = root.right
return root
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(7)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.right = TreeNode(9)
print(find_min(root).val) # 1
print(find_max(root).val) # 9Sucessor e predecessor em ordem
O sucessor em ordem de um nó é o nó com o menor valor maior que o valor dele. Se o nó tiver uma subárvore direita, o sucessor será find_min(node.right). Se não tiver uma subárvore direita, o sucessor será o ancestral mais baixo para o qual o nó fornecido está na subárvore esquerda. Compreender isso é fundamental para problemas de exclusão em BST e de iteradores de BST.
def inorder_successor(root, p):
successor = None
while root:
if p.val < root.val:
successor = root # possible successor
root = root.left
else:
root = root.right
return successor
def inorder_predecessor(root, p):
predecessor = None
while root:
if p.val > root.val:
predecessor = root # possible predecessor
root = root.right
else:
root = root.left
return predecessor
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
p = root.left # node with val=2
print(inorder_successor(root, p).val) # 3
print(inorder_predecessor(root, p).val) # 1Análise da complexidade da busca em BST
O desempenho de uma BST depende inteiramente da altura da árvore. Em uma BST balanceada com n nós, a altura é O(log n), resultando em busca, inserção e exclusão em O(log n). Em uma BST degenerada, a altura é O(n), resultando em O(n) para todas as operações. Python não oferece uma BST balanceada integrada, ao contrário do TreeMap do Java; portanto, você precisa implementar árvores AVL ou rubro-negras por conta própria, usar sortedcontainers.SortedList ou recorrer a um montículo em casos de uso de filas de prioridades.
# Python's BST alternatives:
# 1. heapq - min/max heap, O(log n) push/pop
# 2. sortedcontainers.SortedList (third-party, often allowed)
# 3. Manual AVL or Red-Black (rarely required in interviews)
# When interviews say 'use a BST':
# - LeetCode: implement TreeNode-based solution
# - Real interview: mention sortedcontainers or Java TreeMap equivalent
# - O(log n) operations matter when you need ordered access
# For pure insert/lookup without ordering: use dict (O(1) average)
print('Use heap for priority, dict for lookup, BST for ordered range')Inserção em BST: casos-limite
Verifique sempre se sua inserção trata de: árvore vazia (retorne um novo nó como raiz), valores duplicados (defina se deve ignorá-los, inseri-los à esquerda ou inseri-los à direita — e seja consistente) e valores muito grandes ou muito pequenos. Em entrevistas, declare sua suposição sobre duplicatas antes de escrever o código. A convenção mais comum nos problemas do LeetCode é que todos os valores sejam distintos, salvo indicação contrária.
def insert_bst_no_duplicates(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insert_bst_no_duplicates(root.left, val)
elif val > root.val:
root.right = insert_bst_no_duplicates(root.right, val)
# else: val == root.val -> duplicate, skip
return root
# Test all edge cases:
root = None
root = insert_bst_no_duplicates(root, 5) # empty tree
root = insert_bst_no_duplicates(root, 5) # duplicate
root = insert_bst_no_duplicates(root, 3)
root = insert_bst_no_duplicates(root, 7)
print(root.val, root.left.val, root.right.val) # 5 3 7BST a partir de um vetor ordenado
A construção de uma BST balanceada por altura a partir de um vetor ordenado (LeetCode #108) usa divisão e conquista: o elemento central torna-se a raiz, a metade esquerda torna-se a subárvore esquerda e a metade direita torna-se a subárvore direita. Isso garante uma árvore balanceada com altura O(log n). A complexidade temporal é O(n), pois cada elemento é processado uma vez.
def sorted_array_to_bst(nums):
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = sorted_array_to_bst(nums[:mid])
root.right = sorted_array_to_bst(nums[mid+1:])
return root
nums = [-10, -3, 0, 5, 9]
root = sorted_array_to_bst(nums)
print(root.val) # 0 (middle element)
print(root.left.val) # -3
print(root.right.val) # 9Verificação rápida
Verifique sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu: propriedade da BST (subárvore esquerda estritamente menor e subárvore direita estritamente maior), busca e inserção tanto recursivas quanto iterativas, com complexidade de tempo O(h), e árvores degeneradas no pior caso, nas quais a altura é igual a n. A seguir, abordaremos a exclusão em BST e seus três casos.
Perguntas Frequentes
A aula “Inserção e Busca em BST” é grátis?
Sim — o texto completo de “Inserção e Busca em BST” é 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 DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “Inserção e Busca em BST”?
Implemente inserção e busca recursivas e iterativas, acompanhe o caminho pela árvore para várias chaves e analise a complexidade do pior caso em árvores não balanceadas. Você pratica DSA 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 DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA 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 1 de 4.
Quanto tempo leva a aula “Inserção e Busca em BST”?
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 DSA Interview Prep?
Sim. Cada aula de DSA 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