Escreva uma função que exclui todos os nós de uma árvore binária de busca com ID par.

Passo 1

Estamos com uma árvore binária de busca (BST) e queremos escrever uma função que remova todos os nós cujo campo ID seja par.

Passo 2

Para percorrer todos os nós e decidir quais excluir, podemos usar uma travessia recursiva (por exemplo, pós-ordem), de forma que ao visitar cada nó já tenhamos processado seus filhos.
Para excluir um nó na BST, precisamos lidar com três casos: nó folha (sem filhos), nó com um filho e nó com dois filhos. No caso de dois filhos, substituímos o valor do nó pelo valor mínimo da subárvore direita (sucessor) e removemos esse sucessor recursivamente.

Passo 3

Vamos implementar primeiro uma função auxiliar delete_node(root, key) que exclui o nó de valor key na BST mantendo a propriedade de busca.
Por fim, escrevemos a função remove_even_nodes(root) que faz uma pós-ordem: visita filhos, e então, se root.id for par, chama delete_node para excluí-lo.

Passo 4

Resultado final: a função remove_even_nodes retorna a nova raiz da BST sem nós de ID par.

Resposta

Definição de um nó da BST

class Node:
def init(self, id, left=None, right=None):
self.id = id
self.left = left
self.right = right

Função auxiliar para deletar um nó com valor key

def delete_node(root, key):
if root is None:
return None
if key < root.id:
root.left = delete_node(root.left, key)
elif key > root.id:
root.right = delete_node(root.right, key)
else:
# Caso 1: sem filhos
if root.left is None and root.right is None:
return None
# Caso 2: um filho
if root.left is None:
return root.right
if root.right is None:
return root.left
# Caso 3: dois filhos -> encontrar sucessor (mínimo à direita)
succ = root.right
while succ.left:
succ = succ.left
root.id = succ.id
root.right = delete_node(root.right, succ.id)
return root

Função que remove todos os nós com ID par

def remove_even_nodes(root):
if root is None:
return None
# primeiro processa subárvores
root.left = remove_even_nodes(root.left)
root.right = remove_even_nodes(root.right)
# depois, se o ID é par, exclui este nó
if root.id % 2 == 0:
root = delete_node(root, root.id)
return root

Exercícios relacionados