Eliminación en BST: tres casos
Gestione la eliminación de una hoja, de un nodo con un hijo y de un nodo con dos hijos usando el sucesor in-order, e implemente el algoritmo desde cero.
Eliminación en BST: tres casos es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Por qué es difícil eliminar en un BST
La eliminación en un BST es la más compleja de las tres operaciones principales, porque al quitar un nodo debe conservar la propiedad del BST en todo el árbol. Hay tres casos distintos según los hijos del nodo: no tiene hijos (es una hoja), tiene un hijo o tiene dos hijos. Cada caso requiere una estrategia diferente. A los entrevistadores les gusta este problema porque evalúa la manipulación de punteros, la consideración de casos extremos y el conocimiento del concepto de sucesor en inorden.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Three cases for deleting a node:
# Case 1: Leaf node (no children) -> simply remove it
# Case 2: One child -> replace node with its child
# Case 3: Two children -> replace value with in-order successor
# then delete the in-order successor
print('BST delete: 3 cases based on number of children')Caso 1: eliminar un nodo hoja
Un nodo hoja no tiene hijos. La eliminación es sencilla: devuelva None desde la llamada recursiva, lo que hace que el padre establezca su puntero (izquierdo o derecho) en null. Este es el caso base que deben gestionar primero todas las implementaciones de eliminación en BST. Verifique que funcione para el caso especial en el que el árbol tiene un solo nodo (la raíz es una hoja).
def find_min(node):
while node.left:
node = node.left
return node
# Demonstrating leaf deletion:
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.left.left = TreeNode(1) # leaf
root.left.right = TreeNode(4) # leaf
# To delete node 1 (leaf): set root.left.left = None
root.left.left = None
print(root.left.left) # None -- deleted
print(root.left.val) # 3 still intactCaso 2: nodo con un hijo
Cuando un nodo tiene exactamente un hijo, sustitúyalo por ese hijo. Devuelva el hijo no nulo de la llamada recursiva para que se actualice el puntero del padre y omita el nodo eliminado. Esto funciona igual tanto si el único hijo está a la izquierda como a la derecha: basta con devolver el que exista.
# Demonstrating one-child deletion:
# Tree: 5
# / \
# 3 7
# \
# 4
# Delete node 3 (has only right child 4):
# Result: 5
# / \
# 4 7
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.left.right = TreeNode(4)
# In the recursive implementation:
# When we reach node 3 and it has no left child,
# we return root.right (node 4) to the parent.
# Parent sets its left pointer to 4, skipping 3.
print('One-child case: return the surviving child')Caso 3: nodo con dos hijos
Cuando un nodo tiene dos hijos, no podemos eliminarlo sin más. En su lugar, busque el sucesor in-order del nodo (el valor más pequeño del subárbol derecho), copie su valor en el nodo actual y, después, elimine el sucesor in-order del subárbol derecho. El sucesor tiene como máximo un hijo (no tiene hijo izquierdo), por lo que su eliminación corresponde al Caso 1 o al Caso 2, que ya sabemos cómo resolver.
# Demonstrating two-child deletion:
# Tree: 5
# / \
# 3 7
# / \
# 6 9
# Delete node 5 (two children 3 and 7):
# In-order successor = 6 (smallest in right subtree)
# Step 1: replace 5's value with 6
# Step 2: delete 6 from right subtree
# Result: 6
# / \
# 3 7
# \
# 9
print('Two-child case: replace with in-order successor')Implementación completa de eliminación en BST
La eliminación recursiva completa combina los tres casos. Busque el nodo que se debe eliminar comparando valores y, después, gestione el caso correspondiente. El patrón de devolver la raíz (posiblemente modificada) en cada nivel y asignarla de nuevo a root.left o root.right gestiona de forma elegante todas las actualizaciones de punteros sin realizar un seguimiento explícito del padre. La complejidad temporal es O(h).
def delete_node(root, key):
if not root:
return None # key not found
if key < root.val:
root.left = delete_node(root.left, key)
elif key > root.val:
root.right = delete_node(root.right, key)
else: # found the node to delete
if not root.left: # Case 1 or 2: no left child
return root.right
if not root.right: # Case 2: no right child
return root.left
# Case 3: two children -> find in-order successor
successor = find_min(root.right)
root.val = successor.val # copy successor value up
root.right = delete_node(root.right, successor.val) # delete successor
return root
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)
root = delete_node(root, 5)
print(root.val) # 6 (successor replaced 5)¿Por qué usar el sucesor in-order?
Se utiliza el sucesor in-order (el mínimo del subárbol derecho) en lugar del máximo del subárbol izquierdo porque ambas son opciones válidas: cualquiera de las dos conserva la propiedad de BST. El predecesor in-order (el máximo del subárbol izquierdo) también funciona. Algunas implementaciones alternan entre ambos para mantener el árbol equilibrado. En las entrevistas, se espera con más frecuencia la versión con el sucesor in-order; mencione que el predecesor funciona igual de bien.
# Both approaches are valid for two-child deletion:
# Option A: Replace with in-order SUCCESSOR (min of right subtree)
# - Successor goes to current position
# - Delete successor from right subtree
# Option B: Replace with in-order PREDECESSOR (max of left subtree)
# - Predecessor goes to current position
# - Delete predecessor from left subtree
def find_max(node):
while node.right:
node = node.right
return node
# Using predecessor:
def delete_node_pred(root, key):
if not root:
return None
if key < root.val:
root.left = delete_node_pred(root.left, key)
elif key > root.val:
root.right = delete_node_pred(root.right, key)
else:
if not root.left:
return root.right
if not root.right:
return root.left
pred = find_max(root.left)
root.val = pred.val
root.left = delete_node_pred(root.left, pred.val)
return root
print('Both successor and predecessor deletion are correct')Eliminación de todos los nodos con un valor
Una variante le pide eliminar todos los nodos cuyos valores estén dentro de un intervalo o cumplan una condición. En un BST, esto es eficiente: recorra recursivamente el subárbol correspondiente según las comparaciones y aplique la operación de eliminación donde se cumpla la condición. La estructura recursiva de la eliminación en un BST se extiende naturalmente a estos casos sin requerir un recorrido adicional independiente.
# Delete all nodes with values outside [low, high]
def trim_bst(root, low, high):
if not root:
return None
if root.val < low:
# Entire left subtree is also < low, skip to right
return trim_bst(root.right, low, high)
if root.val > high:
# Entire right subtree is also > high, skip to left
return trim_bst(root.left, low, high)
# Current node is within range
root.left = trim_bst(root.left, low, high)
root.right = trim_bst(root.right, low, high)
return root
root = TreeNode(3)
root.left = TreeNode(0)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
root.left.right.left = TreeNode(1)
root = trim_bst(root, 1, 3)
print(root.val, root.left.val) # 3 2Patrón del iterador de BST
El iterador de BST (LeetCode #173) devuelve los elementos en orden ascendente, uno a la vez, con un tiempo promedio de O(1) y un espacio de O(h). Impleméntelo con una pila que simule el recorrido in-order iterativo: al construirlo, inserte en la pila todos los nodos izquierdos desde la raíz. En next(), extraiga el elemento superior e inserte en la pila todos los nodos izquierdos del subárbol derecho. Se trata de un desenrollado controlado del algoritmo in-order iterativo.
class BSTIterator:
def __init__(self, root):
self.stack = []
self._push_left(root)
def _push_left(self, node):
while node:
self.stack.append(node)
node = node.left
def next(self):
node = self.stack.pop()
if node.right:
self._push_left(node.right)
return node.val
def has_next(self):
return bool(self.stack)
root = TreeNode(7)
root.left = TreeNode(3)
root.right = TreeNode(15)
root.right.left = TreeNode(9)
it = BSTIterator(root)
while it.has_next():
print(it.next(), end=' ') # 3 7 9 15Análisis de complejidad de la eliminación de nodos
La eliminación en un BST se ejecuta en un tiempo O(h), donde h es la altura del árbol. En un BST equilibrado, esto equivale a O(log n). En un árbol degenerado, la complejidad empeora hasta O(n). Encontrar el sucesor in-order añade como máximo un recorrido adicional O(h) del subárbol derecho, lo que no cambia la complejidad general. La complejidad espacial es O(h) debido a la pila de llamadas en la implementación recursiva.
# Complexity summary for BST operations:
# Operation | Balanced | Skewed
# ----------|-----------|-------
# Search | O(log n) | O(n)
# Insert | O(log n) | O(n)
# Delete | O(log n) | O(n)
# Min/Max | O(log n) | O(n)
# In-order | O(n) | O(n) (visits all nodes)
# The key: BST guarantees these complexities only when balanced.
# Python standard library has no balanced BST.
# Use sortedcontainers.SortedList for O(log n) ops in practice.
print('All BST core ops are O(h): O(log n) balanced, O(n) skewed')Two Sum en un BST
Two Sum IV en un BST pregunta si existe algún par de nodos cuya suma sea un objetivo. Un enfoque utiliza un conjunto: el recorrido in-order recopila los valores mientras comprueba si target - current ya existe en el conjunto. Un enfoque más elegante utiliza simultáneamente un iterador de BST hacia delante y otro hacia atrás, como dos punteros; así evita espacio adicional aparte de O(h) para la pila de cada iterador.
def find_target_bst(root, k):
seen = set()
def inorder(node):
if not node:
return False
if inorder(node.left):
return True
if k - node.val in seen:
return True
seen.add(node.val)
return inorder(node.right)
return inorder(root)
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.right.right = TreeNode(7)
print(find_target_bst(root, 9)) # True (2+7)
print(find_target_bst(root, 28)) # FalseConvertir un BST en un greater sum tree
El greater sum tree (LeetCode #538) sustituye el valor de cada nodo por la suma de todos los valores mayores o iguales que él en el BST. La idea clave es realizar un recorrido in-order inverso (right → root → left) para visitar los nodos en orden decreciente y mantener una suma acumulada. Esto se ejecuta en un tiempo O(n) y un espacio O(h).
def bst_to_gst(root):
acc = [0] # running accumulated sum
def reverse_inorder(node):
if not node:
return
reverse_inorder(node.right) # visit larger values first
acc[0] += node.val
node.val = acc[0] # replace with cumulative sum
reverse_inorder(node.left)
reverse_inorder(root)
return root
root = TreeNode(4)
root.left = TreeNode(1)
root.right = TreeNode(6)
root.right.left = TreeNode(5)
root.right.right = TreeNode(7)
bst_to_gst(root)
print(root.val) # 4+5+6+7 = 22
print(root.right.val) # 5+6+7 = 18Comprobación rápida
Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección aprendió: los tres casos de eliminación en un BST (hoja, un hijo y dos hijos), la técnica del sucesor in-order para eliminar nodos con dos hijos y patrones recursivos claros, como el iterador de BST y la conversión de BST en un greater sum tree. A continuación, validaremos la corrección de los BST y aprovecharemos las propiedades del recorrido in-order.
Preguntas frecuentes
¿La lección «Eliminación en BST: tres casos» es gratis?
Sí — el texto completo de «Eliminación en BST: tres casos» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Eliminación en BST: tres casos»?
Gestione la eliminación de una hoja, de un nodo con un hijo y de un nodo con dos hijos usando el sucesor in-order, e implemente el algoritmo desde cero. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «Eliminación en BST: tres casos»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Inserción y búsqueda en BST
- Eliminación en BST: tres casos
- Validación de BST y propiedades in-order
- Enésimo menor, suma de rangos y conversión de BST a array ordenado