Validación de BST y propiedades in-order
Valide un árbol binario como BST usando límites mínimos y máximos transmitidos por el árbol y comprobando que el recorrido in-order produce una secuencia ordenada.
Validación de BST y propiedades in-order es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 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.
El problema de validación de BST
Validate BST (LeetCode #98) es un problema clásico de entrevistas que hace tropezar a muchos candidatos. El enfoque ingenuo comprueba únicamente que el valor de cada nodo sea mayor que el de su hijo izquierdo y menor que el de su hijo derecho, pero esta comprobación local es insuficiente. Un nodo de un subárbol puede cumplir la regla local y, aun así, infringir la propiedad global del BST. La solución correcta propaga límites mínimo y máximo por todo el árbol.
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')Enfoque de límites mínimo y máximo
Pase límites inferior y superior durante la recursión. En cada nodo, verifique que low < node.val < high. Al recorrer el subárbol izquierdo, actualice el límite superior a node.val (el subárbol izquierdo debe contener valores menores). Al recorrer el subárbol derecho, actualice el límite inferior a node.val (el subárbol derecho debe contener valores mayores). Comience con low = -infinity y 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)Validación mediante recorrido in-order
Un enfoque alternativo de validación utiliza la propiedad de ordenación del recorrido in-order del BST: recopile la secuencia in-order y verifique que sea estrictamente creciente. Es una solución elegante y fácil de razonar. Sin embargo, utiliza un espacio adicional O(n) para almacenar la secuencia. Una versión optimizada utiliza un único puntero prev durante el recorrido para comprobar cada par sin almacenar la secuencia completa.
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)) # FalseComparación de ambos enfoques de validación
El enfoque de límites mínimo y máximo tiene un tiempo O(n) y un espacio O(h) (solo almacena los límites en la pila de llamadas). El enfoque del puntero prev en el recorrido in-order también tiene un tiempo O(n) y un espacio O(h). Ambos son óptimos. El enfoque de límites es más general y funciona correctamente al ampliarlo a problemas con restricciones adicionales. En las entrevistas, prepárese para presentar ambos y analizar sus ventajas y desventajas; demostrar que conoce las alternativas es una señal muy positiva.
# 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')Recover BST: dos nodos intercambiados
Recover BST (LeetCode #99) repara un BST en el que se han intercambiado exactamente dos nodos. Durante el recorrido in-order, un BST correctamente ordenado produce una secuencia ordenada. Si se intercambian dos nodos, habrá una o dos infracciones en las que prev.val > current.val. El primer nodo de la primera infracción y el segundo nodo de la última infracción son los dos nodos mal ubicados: intercambie sus 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)De BST a array ordenado mediante recorrido in-order
Convertir un BST en un array ordenado es trivial: realice un recorrido in-order y recopile los valores. Esta operación, con un tiempo O(n) y un espacio O(n), es una forma rápida de aplicar algoritmos para arrays ordenados (búsqueda binaria y dos punteros) a datos de un BST. A menudo sirve como paso intermedio en problemas de BST de varias partes, como 'merge two BSTs' o 'find median of 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]Fusión de dos BST
Para fusionar dos BST en un único array ordenado, convierta cada uno en un array ordenado en O(n) y O(m), respectivamente, y después fusione ambos arrays mediante el paso de fusión de merge sort en O(n+m). Tiempo total: O(n+m). Si necesita el resultado como un BST equilibrado, proporcione el array ordenado fusionado al algoritmo de conversión de array ordenado a BST. Esta descomposición en subproblemas sencillos es característica de una solución clara y fácil de seguir en una 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 nodos en un intervalo de un BST
Cuente cuántos nodos tienen valores dentro del intervalo [low, high]. Un recorrido in-order de fuerza bruta cuesta O(n). La versión que aprovecha el BST realiza podas: si el valor del nodo actual es menor que low, no tiene sentido comprobar el subárbol izquierdo (todos sus valores también son menores que low). Del mismo modo, pode el subárbol derecho cuando el valor actual sea mayor que high. En el caso promedio, la complejidad es O(log n + k), donde k es la cantidad de nodos coincidentes.
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 y BST con desigualdad estricta o no estricta
El invariante estándar de un BST utiliza una desigualdad estricta: los valores del subárbol izquierdo son estrictamente menores y los del subárbol derecho son estrictamente mayores. Algunos problemas permiten duplicados y los colocan en el subárbol izquierdo (left <= root) o en el derecho (root < right). Al validar BST, compruebe siempre la definición indicada en el enunciado. El enfoque de límites mínimo y máximo admite ambas variantes ajustando si la comprobación de los límites es estricta o 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')El recorrido in-order como herramienta universal para BST
El recorrido in-order es la herramienta multiusos de los problemas de BST. Siempre que un problema de BST pregunte por ordenación, el k-ésimo elemento, consultas de intervalos o propiedades de una secuencia, considere si un recorrido in-order (o su versión inversa) proporciona la respuesta. La mayoría de los problemas específicos de BST se reducen a lo siguiente: recorrer en orden ordenado y hacer algo en cada paso. Reconocer rápidamente esta correspondencia es una habilidad clave en las 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 más cercano en un BST
Encuentre el nodo cuyo valor sea el más cercano a un objetivo dado. Aproveche el orden del BST: comience en la raíz, mantenga el valor más cercano encontrado hasta el momento y avance hacia el objetivo (vaya a la izquierda si el objetivo es menor y a la derecha si es mayor). Este enfoque O(h) es más eficiente que un recorrido in-order y demuestra un uso eficaz de la propiedad del BST para podar el espacio de búsqueda.
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)) # 4Comprobació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ó: la validación de BST con límites mínimo y máximo (evitando el problema de la comprobación local), la alternativa del puntero prev en el recorrido in-order para la validación y el recorrido in-order como herramienta universal de BST para sumas de intervalos, valores más cercanos y operaciones de fusión. A continuación, utilizaremos las propiedades del recorrido in-order de los BST para encontrar el k-ésimo elemento menor.
Preguntas frecuentes
¿La lección «Validación de BST y propiedades in-order» es gratis?
Sí — el texto completo de «Validación de BST y propiedades in-order» 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 «Validación de BST y propiedades in-order»?
Valide un árbol binario como BST usando límites mínimos y máximos transmitidos por el árbol y comprobando que el recorrido in-order produce una secuencia ordenada. 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 3 de 4.
¿Cuánto tiempo toma la lección «Validación de BST y propiedades in-order»?
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