K-esimo più piccolo, somma degli intervalli e da BST ad array ordinato
Sfrutti il percorso in-order ordinato per trovare l'elemento k-esimo più piccolo in O(k) e sommare i valori in un intervallo in O(log n + k)
K-esimo più piccolo, somma degli intervalli e da BST ad array ordinato è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
K-esimo elemento più piccolo in un BST
Kth Smallest Element in a BST (LeetCode #230) è un classico problema che sfrutta direttamente l'attraversamento in-order ordinato. Poiché l'in-order visita i nodi in ordine crescente, è sufficiente contare i nodi durante l'attraversamento e restituire il valore quando il conteggio raggiunge k. La complessità è O(h + k), dove h è l'altezza, necessaria per raggiungere il nodo più a sinistra, e k è il numero di passi nell'attraversamento 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-esimo elemento più piccolo: versione iterativa con stack
La versione iterativa usa il pattern dello stack esplicito per l'attraversamento in-order. Inserisca nello stack i nodi sinistri fino a raggiungere null, quindi estragga un nodo e incrementi il conteggio. Quando il conteggio raggiunge k, restituisca il valore del nodo corrente. Questo evita il limite di ricorsione di Python per gli alberi molto profondi e mantiene una complessità di O(h + k) in tempo e O(h) in spazio. Nei colloqui, spesso viene richiesta la versione iterativa dopo quella ricorsiva.
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-esimo elemento più grande in un BST
Kth Largest usa l'attraversamento in-order inverso (destra → radice → sinistra), che visita i nodi in ordine decrescente. Conti k passi e restituisca il valore del nodo corrente. È il procedimento simmetrico rispetto alla ricerca del k-esimo elemento più piccolo e ha complessità O(h + k) in tempo. In alternativa, calcoli kth_smallest(root, total_count - k + 1) se conosce la dimensione dell'albero, ma l'approccio in-order inverso è più 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)Somma degli elementi di un BST in un intervallo
Range Sum of BST (LeetCode #938) richiede la somma di tutti i valori in [low, high]. Sfrutti la proprietà del BST per eliminare rami: se il valore del nodo corrente è minore di low, l'intero sottoalbero sinistro è anch'esso al di sotto di low, quindi lo si può ignorare. Se il valore corrente è maggiore di high, ignori il sottoalbero destro. In questo modo si eliminano molti rami ed è più efficiente di una scansione in-order completa.
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 = 32Conteggio dei nodi in un intervallo
Il conteggio dei nodi nell'intervallo [low, high] segue la stessa logica di eliminazione dei rami. Un'alternativa usa bisect_left/bisect_right sull'array in-order, ma l'attraversamento diretto del BST ha complessità O(log n + k), mentre la conversione preventiva in un array richiede sempre O(n). Scelga l'attraversamento diretto, a meno che non debba rispondere a molte query su intervalli; in tal caso, la costruzione di un BST arricchito con i conteggi dei sottoalberi consente una complessità O(log n) per query.
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 in array ordinato (algoritmo completo)
Convertire un BST in un array ordinato richiede O(n) in tempo e O(n) in spazio. Usi l'attraversamento in-order e aggiunga ogni valore all'array. Questo è il punto di partenza per problemi composti da più passaggi, come «unire due BST», «trovare la mediana di un BST» o «verificare se due BST hanno la stessa sequenza in-order». L'array risultante supporta l'accesso O(1) per indice, la ricerca binaria e le tecniche a due puntatori, che il BST non può fornire direttamente.
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 aumentato: dimensioni dei sottoalberi
Un BST aumentato memorizza informazioni aggiuntive in ogni nodo, ad esempio la dimensione del relativo sottoalbero. Con le dimensioni dei sottoalberi, trovare il k-esimo elemento più piccolo diventa un'operazione O(log n): in ogni nodo, se la dimensione del sottoalbero sinistro è k-1, il nodo corrente è la risposta; se la dimensione del sottoalbero sinistro è >= k, si procede ricorsivamente a sinistra; altrimenti si sottrae e si procede a destra. Questa è la struttura dati alla base degli alberi con statistiche d'ordine usati nella programmazione 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')Trovare tutti i valori in un BST compresi tra due nodi
Per restituire tutti i valori strettamente compresi tra due nodi p e q (dove p.val < q.val), combini la visita in ordine con la potatura dell'intervallo: inizi a raccogliere i valori dopo aver superato p.val e ti fermi dopo q.val. Si tratta di una generalizzazione della somma su un intervallo e restituisce la sequenza ordinata compresa tra i due valori richiesti in tempo 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 di un BST
La mediana di un BST è il valore centrale della visita in ordine. Per n nodi, la mediana si trova all'indice n // 2 (con indicizzazione a partire da 0). Può raccogliere l'intero array ordinato e accedere all'elemento tramite l'indice, oppure effettuare due passaggi: prima contare n nodi, quindi eseguire una seconda visita in ordine e fermarsi al nodo n // 2-esimo. In alternativa, può usare la ricerca del k-esimo elemento più piccolo 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])K valori più vicini a un obiettivo
Trovi i k valori di un BST più vicini a un obiettivo. Un approccio a due puntatori consiste nel convertire il BST in un array ordinato e usare una finestra scorrevole di dimensione k. In alternativa, può usare un max-heap di dimensione k, in cui inserisce le distanze ed estrae un elemento quando la dimensione supera k. L'approccio con array ordinato richiede tempo O(n) ed è semplice; quello con heap richiede O(n log k), ma funziona in un contesto di elaborazione in 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]Sfruttare la proprietà dell'ordine dei successori
Molti problemi sui BST si riducono alla ricerca dell'elemento successivo o precedente nell'ordine ordinato: operazioni eseguibili in O(log n) usando la navigazione nel BST. L'iteratore creato in precedenza fornisce un'operazione next con costo ammortizzato O(1). Combinando le conoscenze sul k-esimo elemento più piccolo, sulla somma su un intervallo e sul valore più vicino, può risolvere la maggior parte dei problemi sui BST dei colloqui chiedendosi: «In che modo l'ordinamento della visita in ordine semplifica questo problema?». Questo modello generale è la sua bussola per risolvere i problemi sui 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')Verifica rapida
Verifichi la sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato a trovare il k-esimo elemento più piccolo e più grande usando la visita in ordine e la visita in ordine inverso in O(h+k), a calcolare la somma su un intervallo con la potatura del BST per eseguire query efficienti sugli intervalli e a convertire un BST in un array ordinato come base per gli algoritmi basati su array. Ora passeremo agli heap e alle code con priorità.
Domande Frequenti
La lezione «K-esimo più piccolo, somma degli intervalli e da BST ad array ordinato» è gratuita?
Sì — il testo completo di «K-esimo più piccolo, somma degli intervalli e da BST ad array ordinato» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «K-esimo più piccolo, somma degli intervalli e da BST ad array ordinato»?
Sfrutti il percorso in-order ordinato per trovare l'elemento k-esimo più piccolo in O(k) e sommare i valori in un intervallo in O(log n + k) Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «K-esimo più piccolo, somma degli intervalli e da BST ad array ordinato»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Inserimento e ricerca in un BST
- Eliminazione da un BST: tre casi
- Convalidare un BST e le proprietà in-order
- K-esimo più piccolo, somma degli intervalli e da BST ad array ordinato