Inserción y búsqueda en BST
Implemente la inserción y la búsqueda recursivas e iterativas, siga la ruta por el árbol para distintas claves y analice la complejidad del peor caso en árboles no equilibrados.
Inserción y búsqueda en BST es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 1 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 DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
Definición de la propiedad del BST
Un Binary Search Tree cumple una invariante: para cada nodo, todos los valores de su subárbol izquierdo son estrictamente menores que el valor del nodo y todos los valores de su subárbol derecho son estrictamente mayores. Esta propiedad de orden —que se mantiene en todo el subárbol, no solo en los hijos inmediatos— permite realizar búsquedas, inserciones y eliminaciones en O(log n) en árboles equilibrados, y distingue un BST de un árbol binario genérico.
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')Búsqueda recursiva en un BST
La búsqueda en un BST funciona como la búsqueda binaria: compare el objetivo con el valor del nodo actual y recurra en el subárbol correspondiente. Si el objetivo es igual al valor actual, devuelva el nodo. Si el objetivo es menor, vaya a la izquierda; si es mayor, vaya a la derecha. Devuelva null si llega a un nodo vacío. La complejidad temporal es O(h): O(log n) en árboles equilibrados y O(n) en árboles sesgados.
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 foundBúsqueda iterativa en un BST
La búsqueda iterativa evita la sobrecarga de la pila de llamadas y se prefiere en el código de producción. Utilice un puntero curr que recorra el árbol siguiendo la dirección izquierda o derecha según las comparaciones. Se trata de un bucle while sencillo con tres casos: null (no encontrado), coincidencia (encontrado) o ajuste de dirección. La búsqueda iterativa también es O(h), pero utiliza O(1) de espacio frente a O(h) en la versión 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)) # NoneInserción recursiva en un BST
La inserción en un BST encuentra la posición correcta siguiendo las mismas decisiones izquierda/derecha que la búsqueda y luego adjunta un nodo nuevo en la primera posición null alcanzada. El enfoque recursivo devuelve la raíz (posiblemente nueva) de cada subárbol: si el nodo actual es null, devuelva un TreeNode nuevo; de lo contrario, actualice root.left o root.right con el resultado de la llamada recursiva. Este patrón es claro y habitual en las soluciones 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) # 5Inserción iterativa en un BST
La inserción iterativa utiliza un puntero parent para realizar un seguimiento del último nodo distinto de null antes de llegar al punto de inserción. Recorra el árbol como en la búsqueda, registrando el padre y la última dirección seguida. Cuando llegue a null, adjunte el nodo nuevo al lado correspondiente del padre. Gestione siempre por separado el caso extremo del árbol vacío (la raíz es null).
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 en el peor caso: árboles sesgados
Si inserta una secuencia ordenada en un BST, obtiene un árbol sesgado que degenera en una lista enlazada. La búsqueda, la inserción y la eliminación pasan a tener una complejidad O(n). Por eso existen los BST equilibrados (árboles AVL y árboles rojo-negro). En las entrevistas, mencione siempre este peor caso cuando le pregunten por la complejidad de un BST: decir «O(log n) en promedio, O(n) en el peor caso para árboles no equilibrados» demuestra una comprensión profunda.
# 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)Cómo encontrar el mínimo y el máximo
En un BST, el valor mínimo siempre se encuentra en el nodo situado más a la izquierda (siga avanzando a la izquierda hasta llegar a null), y el máximo está en el nodo situado más a la derecha. Estas operaciones O(h) se utilizan con frecuencia como subrutinas en la eliminación de BST (para encontrar el sucesor en inorden) y en las consultas de rangos. Aprender estas funciones auxiliares de memoria ahorra tiempo en las 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) # 9Sucesor y predecesor en inorden
El sucesor en inorden de un nodo es el nodo con el menor valor que sea mayor que él. Si el nodo tiene un subárbol derecho, el sucesor es find_min(node.right). Si no tiene subárbol derecho, el sucesor es el ancestro más profundo para el que el nodo dado se encuentra en el subárbol izquierdo. Comprender esto es fundamental para los problemas de eliminación e 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álisis de la complejidad de búsqueda en un BST
El rendimiento de un BST depende por completo de la altura del árbol. En un BST equilibrado con n nodos, la altura es O(log n), lo que proporciona búsquedas, inserciones y eliminaciones en O(log n). En un BST sesgado, la altura es O(n), por lo que todas las operaciones tienen complejidad O(n). Python no tiene un BST equilibrado integrado (a diferencia de TreeMap de Java), por lo que debe implementar un árbol AVL o rojo-negro, usar sortedcontainers.SortedList o recurrir a un heap para casos de uso de colas de prioridad.
# 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')Insertar en un BST: casos extremos
Verifique siempre que la inserción gestione: árbol vacío (devuelva el nodo nuevo como raíz), valores duplicados (defina si debe ignorarlos, insertarlos a la izquierda o insertarlos a la derecha; sea coherente) y valores muy grandes o muy pequeños. En las entrevistas, indique su suposición sobre los duplicados antes de programar. La convención más común en los problemas de LeetCode es que todos los valores son distintos, salvo que se indique lo contrario.
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 un arreglo ordenado
La construcción de un BST equilibrado en altura a partir de un arreglo ordenado (LeetCode #108) utiliza divide y vencerás: el elemento central se convierte en la raíz, la mitad izquierda en el subárbol izquierdo y la mitad derecha en el subárbol derecho. Esto garantiza un árbol equilibrado con una altura O(log n). La complejidad temporal es O(n), ya que cada elemento se procesa una 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) # 9Comprobación rápida
Compruebe 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ó: propiedad del BST (subárbol izquierdo estrictamente menor y subárbol derecho estrictamente mayor), búsqueda e inserción tanto recursivas como iterativas en O(h) y árboles sesgados en el peor caso, donde la altura es igual a n. A continuación, abordará la eliminación en BST y sus tres casos.
Preguntas frecuentes
¿La lección «Inserción y búsqueda en BST» es gratis?
Sí — el texto completo de «Inserción y búsqueda en BST» 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 DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Inserción y búsqueda en BST»?
Implemente la inserción y la búsqueda recursivas e iterativas, siga la ruta por el árbol para distintas claves y analice la complejidad del peor caso en árboles no equilibrados. Practicas DSA 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 DSA Interview Prep?
No se requiere experiencia previa. DSA 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 1 de 4.
¿Cuánto tiempo toma la lección «Inserción y búsqueda en BST»?
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 DSA Interview Prep?
Sí. Cada lección de DSA 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