Enésimo menor, suma de rangos y conversión de BST a array ordenado
Aproveche el recorrido in-order ordenado para encontrar el elemento kth-smallest en O(k) y sumar valores dentro de un rango en O(log n + k).
Enésimo menor, suma de rangos y conversión de BST a array ordenado es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 4 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.
K-ésimo menor en un BST
Kth Smallest Element in a BST (LeetCode #230) es un problema clásico que aprovecha directamente el recorrido in-order ordenado. Como el recorrido in-order visita los nodos en orden ascendente, basta con contar los nodos durante el recorrido y devolver el valor cuando el contador llegue a k. El tiempo es O(h + k), donde h es la altura (para llegar al nodo más a la izquierda) y k es la cantidad de pasos del recorrido in-order.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def kth_smallest(root, k):
count = [0]
result = [None]
def inorder(node):
if not node or result[0] is not None:
return
inorder(node.left)
count[0] += 1
if count[0] == k:
result[0] = node.val
return
inorder(node.right)
inorder(root)
return result[0]
root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kth_smallest(root, 1)) # 1
print(kth_smallest(root, 2)) # 2K-ésimo menor: versión iterativa con pila
La versión iterativa utiliza el patrón de recorrido in-order con una pila explícita. Inserte los nodos izquierdos en la pila hasta llegar a null y, después, extraiga nodos y cuéntelos. Cuando el contador llegue a k, devuelva el valor del nodo actual. Esto evita el límite de recursión de Python en árboles muy profundos y también tiene un tiempo O(h + k) y un espacio O(h). A menudo, los entrevistadores solicitan la versión iterativa después de la recursiva.
def kth_smallest_iterative(root, k):
stack = []
curr = root
count = 0
while curr or stack:
while curr: # go as far left as possible
stack.append(curr)
curr = curr.left
curr = stack.pop() # process node
count += 1
if count == k:
return curr.val
curr = curr.right # move to right subtree
return -1 # k out of range
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.left.left.left = TreeNode(1)
print(kth_smallest_iterative(root, 3)) # 3K-ésimo mayor en un BST
Kth Largest utiliza un recorrido in-order inverso (right → root → left), que visita los nodos en orden descendente. Cuente k pasos y devuelva el valor del nodo actual. Es el equivalente simétrico de k-ésimo menor y se ejecuta en un tiempo O(h + k). Como alternativa, calcule kth_smallest(root, total_count - k + 1) si conoce el tamaño del árbol, pero el enfoque in-order inverso es más elegante.
def kth_largest(root, k):
count = [0]
result = [None]
def reverse_inorder(node):
if not node or result[0] is not None:
return
reverse_inorder(node.right) # visit LARGER values first
count[0] += 1
if count[0] == k:
result[0] = node.val
return
reverse_inorder(node.left)
reverse_inorder(root)
return result[0]
root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kth_largest(root, 1)) # 4 (largest)
print(kth_largest(root, 2)) # 3 (2nd largest)Suma de un intervalo en un BST
Range Sum of BST (LeetCode #938) solicita la suma de todos los valores en [low, high]. Aproveche la propiedad del BST para realizar podas: si el valor del nodo actual es menor que low, todo el subárbol izquierdo también está por debajo de low; omítalo. Si el valor actual es mayor que high, omita el subárbol derecho. Esto poda muchas ramas y es más eficiente que un recorrido in-order completo.
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 might have values >= low
total += range_sum_bst(root.left, low, high)
if root.val < high: # right subtree might 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 = 32Contar nodos en un intervalo
Contar nodos en un intervalo [low, high] sigue la misma lógica de poda. Como alternativa, puede utilizar bisect_left/bisect_right sobre el array in-order, pero el recorrido directo del BST tiene una complejidad O(log n + k), mientras que convertir primero los datos en un array siempre cuesta O(n). Elija el recorrido directo, a menos que necesite responder muchas consultas de intervalos; en ese caso, construir un BST aumentado con recuentos de subárboles permite responder cada consulta en O(log n).
def count_range(root, low, high):
if not root:
return 0
count = 0
if low <= root.val <= high:
count += 1
if root.val > low:
count += count_range(root.left, low, high)
if root.val < high:
count += count_range(root.right, low, high)
return count
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(count_range(root, 6, 15)) # 7, 10, 15 = 3BST a array ordenado: algoritmo completo
Convertir un BST en un array ordenado cuesta un tiempo O(n) y un espacio O(n). Utilice un recorrido in-order y añada cada valor. Este es el punto de partida para problemas de varios pasos: 'merge two BSTs', 'find the median of a BST' o 'check if two BSTs have the same in-order sequence'. El array resultante permite acceso O(1) por índice, búsqueda binaria y técnicas de dos punteros que el propio BST no puede proporcionar directamente.
def bst_to_sorted(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(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)
print(bst_to_sorted(root)) # [1, 3, 4, 5, 6, 8, 9]
# Binary search on the resulting sorted array:
import bisect
arr = bst_to_sorted(root)
print(bisect.bisect_left(arr, 6)) # 4 (index of 6)BST aumentado: tamaños de subárboles
Un BST aumentado almacena información adicional en cada nodo, como el tamaño de su subárbol. Con los tamaños de los subárboles, kth-smallest pasa a ejecutarse en O(log n): en cada nodo, si el tamaño del subárbol izquierdo es k-1, el nodo actual es la respuesta; si el tamaño izquierdo es >= k, continúe recursivamente por la izquierda; de lo contrario, reste y continúe por la derecha. Esta es la estructura de datos en la que se basan los árboles de estadísticos de orden utilizados en programación competitiva.
class AugNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.size = 1 # subtree size
def get_size(node):
return node.size if node else 0
def update_size(node):
if node:
node.size = 1 + get_size(node.left) + get_size(node.right)
def kth_smallest_aug(root, k):
left_size = get_size(root.left)
if k == left_size + 1:
return root.val # current node is kth
elif k <= left_size:
return kth_smallest_aug(root.left, k)
else:
return kth_smallest_aug(root.right, k - left_size - 1)
print('Augmented BST: O(log n) kth smallest with subtree sizes')Encontrar todos los valores de un BST entre dos nodos
Para devolver todos los valores estrictamente comprendidos entre dos nodos p y q (donde p.val < q.val), combine el recorrido in-order con la poda por rango: empiece a recopilar valores una vez que supere p.val y deténgase después de q.val. Esta es una generalización de la suma de rangos y proporciona la secuencia ordenada entre los dos valores consultados en O(h + k).
def values_between(root, low, high):
result = []
def inorder(node):
if not node:
return
if node.val > low: # might be values > low on left
inorder(node.left)
if low < node.val < high: # strictly between
result.append(node.val)
if node.val < high: # might be values < high on right
inorder(node.right)
inorder(root)
return result
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.left = TreeNode(12)
root.right.right = TreeNode(18)
print(values_between(root, 6, 15)) # [7, 10, 12]Mediana de un BST
La mediana de un BST es el valor central del recorrido in-order. Para n nodos, la mediana se encuentra en el índice n // 2 (indexado desde 0). Puede recopilar el array ordenado completo y acceder a ese índice, o realizar dos pasadas: primero cuente n nodos y después haga un segundo recorrido in-order que se detenga en el nodo n // 2. Como alternativa, utilice kth-smallest con k = n // 2 + 1.
def count_nodes(root):
if not root:
return 0
return 1 + count_nodes(root.left) + count_nodes(root.right)
def median_of_bst(root):
n = count_nodes(root)
if n == 0:
return None
k = n // 2 + 1 # (n+1)/2-th element for odd, n/2+1-th for even
return kth_smallest(root, k)
def kth_smallest(root, k):
count = [0]; result = [None]
def inorder(node):
if not node or result[0] is not None: return
inorder(node.left)
count[0] += 1
if count[0] == k: result[0] = node.val; return
inorder(node.right)
inorder(root); return result[0]
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
print(median_of_bst(root)) # 4 (middle of [1,3,4,5,8])Los k valores más cercanos al objetivo
Encuentre los k valores de un BST más cercanos a un objetivo. Un enfoque de dos punteros consiste en convertir el BST en un array ordenado y utilizar una ventana deslizante de tamaño k. Como alternativa, utilice un max-heap de tamaño k en el que inserte las distancias y elimine elementos cuando el tamaño supere k. El enfoque basado en un array ordenado requiere O(n) tiempo y es sencillo; el enfoque basado en un heap requiere O(n log k), pero funciona en un contexto de procesamiento en streaming.
import heapq
def closest_k_values(root, target, k):
# Collect sorted values
arr = []
def inorder(node):
if not node: return
inorder(node.left)
arr.append(node.val)
inorder(node.right)
inorder(root)
# Two-pointer sliding window of size k
left, right = 0, k - 1
while right < len(arr) - 1:
if abs(arr[left] - target) <= abs(arr[right + 1] - target):
break # left is closer, don't advance
left += 1
right += 1
return arr[left:right + 1]
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(closest_k_values(root, 3.7, 2)) # [3, 4]Aprovechar la propiedad del orden de los sucesores
Muchos problemas de BST se reducen a encontrar el siguiente o el elemento anterior en el orden ordenado, operaciones que se ejecutan en O(log n) mediante la navegación del BST. El iterador que construimos anteriormente proporciona un siguiente con un coste amortizado de O(1). Si combina sus conocimientos sobre kth-smallest, suma de rangos y valores más cercanos, podrá resolver la mayoría de los problemas de entrevistas sobre BST preguntándose: «¿Cómo simplifica esto el orden ordenado del recorrido in-order?». Este metapatrón es su brújula para resolver problemas de BST.
# Meta-pattern for BST problems:
# Step 1: What sorted-order property does this exploit?
# Step 2: Is in-order (ascending) or reverse in-order (descending) needed?
# Step 3: Can I prune using BST ordering to avoid O(n) scan?
# Quick reference:
# kth smallest -> in-order, stop at kth node
# kth largest -> reverse in-order, stop at kth node
# range sum -> in-order + BST pruning
# closest value -> walk toward target, track best
# median -> kth with k = n//2+1
# sorted array -> full in-order
# validate -> in-order prev check or min/max bounds
print('Sorted in-order is the universal BST problem tool')Comprobació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 ha aprendido: a encontrar el kth smallest y el kth largest mediante recorridos in-order y reverse in-order en O(h+k); a calcular la suma de rangos con poda del BST para realizar consultas de rango eficientes; y a convertir un BST en un array ordenado como base para algoritmos basados en arrays. A continuación exploraremos los heaps y las colas de prioridad.
Preguntas frecuentes
¿La lección «Enésimo menor, suma de rangos y conversión de BST a array ordenado» es gratis?
Sí — el texto completo de «Enésimo menor, suma de rangos y conversión de BST a array ordenado» 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 «Enésimo menor, suma de rangos y conversión de BST a array ordenado»?
Aproveche el recorrido in-order ordenado para encontrar el elemento kth-smallest en O(k) y sumar valores dentro de un rango en O(log n + k). 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 4 de 4.
¿Cuánto tiempo toma la lección «Enésimo menor, suma de rangos y conversión de BST a array ordenado»?
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