K-ième plus petit élément, somme d’intervalle et BST vers tableau trié
Exploitez le parcours infixe trié pour trouver le k-ième plus petit élément en O(k) et additionner les valeurs d’un intervalle en O(log n + k).
K-ième plus petit élément, somme d’intervalle et BST vers tableau trié est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.
K-ième plus petit élément dans un BST
Le k-ième plus petit élément dans un BST (LeetCode n° 230) est un problème classique qui exploite directement le parcours infixe trié. Comme le parcours infixe visite les nœuds dans l’ordre croissant, il suffit de compter les nœuds au fur et à mesure du parcours et de renvoyer la valeur lorsque le compteur atteint k. La complexité temporelle est O(h + k), où h représente la hauteur (pour atteindre le nœud le plus à gauche) et k le nombre d’étapes du parcours infixe.
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-ième plus petit élément : approche itérative avec une pile
La version itérative utilise le modèle de parcours infixe avec une pile explicite. Empilez les nœuds gauches jusqu’à atteindre une valeur nulle, puis dépilez et comptez. Lorsque le compteur atteint k, renvoyez la valeur du nœud courant. Cette approche évite la limite de récursion de Python pour les arbres très profonds et offre également une complexité temporelle de O(h + k) et une complexité spatiale de O(h). Les recruteurs demandent souvent la version itérative après la version récursive.
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-ième plus grande valeur dans un BST
Le k-ième plus grand élément utilise un parcours infixe inversé (droite → racine → gauche), qui visite les nœuds dans l’ordre décroissant. Comptez k étapes et renvoyez la valeur du nœud courant. Cette approche est symétrique de celle du k-ième plus petit élément et s’exécute en O(h + k). Vous pouvez également calculer kth_smallest(root, total_count - k + 1) si vous connaissez la taille de l’arbre, mais l’approche par parcours infixe inversé est plus élégante.
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)Somme sur un intervalle d’un BST
Somme sur un intervalle d’un BST (LeetCode n° 938) demande la somme de toutes les valeurs dans [low, high]. Exploitez la propriété du BST pour éliminer des branches : si la valeur du nœud courant est inférieure à la borne inférieure, tout le sous-arbre gauche est également inférieur à cette borne ; ignorez-le. Si la valeur courante est supérieure à la borne supérieure, ignorez le sous-arbre droit. Cette méthode élimine de nombreuses branches et est plus efficace qu’un parcours infixe complet.
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 = 32Compter les nœuds dans un intervalle
Compter les nœuds dans un intervalle [low, high] suit la même logique d’élimination des branches. Une autre approche utilise bisect_left/bisect_right sur le tableau infixe, mais le parcours direct du BST s’exécute en O(log n + k), tandis que la conversion préalable en tableau s’exécute toujours en O(n). Choisissez le parcours direct, sauf si vous devez traiter de nombreuses requêtes sur des intervalles ; dans ce cas, la construction d’un BST enrichi avec le nombre de nœuds de chaque sous-arbre permet de répondre à chaque requête 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 vers tableau trié (algorithme complet)
Convertir un BST en tableau trié s’exécute en O(n) et utilise O(n) d’espace. Utilisez un parcours infixe et ajoutez chaque valeur à la suite. C’est le point de départ de problèmes en plusieurs étapes : « fusionner deux BST », « trouver la médiane d’un BST » ou « vérifier que deux BST ont la même séquence infixe ». Le tableau obtenu permet un accès en O(1) par indice, la recherche binaire et les techniques à deux pointeurs, que le BST lui-même ne peut pas fournir directement.
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 augmenté : tailles des sous-arbres
Un BST augmenté stocke des informations supplémentaires à chaque nœud, comme la taille de son sous-arbre. Grâce aux tailles des sous-arbres, kth-smallest s'exécute en O(log n) : à chaque nœud, si la taille du sous-arbre gauche vaut k-1, le nœud courant est la réponse ; si la taille du sous-arbre gauche est >= k, poursuivez récursivement à gauche ; sinon, soustrayez cette taille et poursuivez à droite. C'est la structure de données qui sous-tend les arbres de statistiques d'ordre utilisés en programmation compétitive.
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')Trouver toutes les valeurs d'un BST entre deux nœuds
Pour renvoyer toutes les valeurs strictement comprises entre deux nœuds p et q (où p.val < q.val), combinez un parcours dans l'ordre avec un élagage par intervalle : commencez à collecter les valeurs dès que vous dépassez p.val et arrêtez-vous après q.val. Il s'agit d'une généralisation de la somme sur intervalle, qui fournit la séquence triée comprise entre les deux valeurs recherchées 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]Médiane d'un BST
La médiane d'un BST est la valeur centrale du parcours dans l'ordre. Pour n nœuds, la médiane se trouve à l'indice n // 2 (avec un indexage à partir de 0). Vous pouvez soit construire le tableau trié complet et y accéder à cet indice, soit effectuer deux parcours : comptez d'abord les nœuds, puis réalisez un second parcours dans l'ordre en vous arrêtant au nœud n // 2. Vous pouvez également utiliser kth-smallest avec 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 valeurs les plus proches de la cible
Trouvez les k valeurs d'un BST les plus proches d'une cible. Une approche à deux pointeurs consiste à convertir le BST en tableau trié et à utiliser une fenêtre glissante de taille k. Vous pouvez également utiliser un tas max de taille k, dans lequel vous insérez les distances avec push et effectuez pop lorsque la taille dépasse k. L'approche fondée sur un tableau trié s'exécute en O(n) et reste simple ; celle fondée sur un tas s'exécute en O(n log k), mais fonctionne dans un contexte de traitement en flux.
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]Exploiter la propriété d'ordre des successeurs
De nombreux problèmes sur les BST se réduisent à trouver l'élément suivant ou précédent dans l'ordre trié : ces opérations s'exécutent en O(log n) grâce à la navigation dans le BST. L'itérateur que nous avons construit précédemment fournit l'opération suivante en O(1) amorti. En combinant vos connaissances sur kth-smallest, la somme sur intervalle et les valeurs les plus proches, vous pouvez résoudre la plupart des problèmes d'entretien sur les BST en vous demandant : « Comment l'ordre trié du parcours dans l'ordre simplifie-t-il ce problème ? » Ce méta-modèle est votre boussole pour résoudre les problèmes sur les 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')Vérification rapide
Vérifiez votre compréhension des concepts de Structures de données & algorithmes — Préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris à trouver le k-ième plus petit et le k-ième plus grand élément à l'aide des parcours dans l'ordre et dans l'ordre inverse en O(h+k), à calculer une somme sur intervalle avec élagage du BST pour effectuer efficacement des requêtes sur des intervalles, et à convertir un BST en tableau trié comme base pour les algorithmes fondés sur des tableaux. Nous allons ensuite étudier les tas et les files de priorité.
Questions Fréquemment Posées
La leçon « K-ième plus petit élément, somme d’intervalle et BST vers tableau trié » est-elle gratuite ?
Oui — le texte complet de « K-ième plus petit élément, somme d’intervalle et BST vers tableau trié » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « K-ième plus petit élément, somme d’intervalle et BST vers tableau trié » ?
Exploitez le parcours infixe trié pour trouver le k-ième plus petit élément en O(k) et additionner les valeurs d’un intervalle en O(log n + k). Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?
Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.
Combien de temps prend la leçon « K-ième plus petit élément, somme d’intervalle et BST vers tableau trié » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?
Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Insertion et recherche dans un BST
- Suppression dans un BST : trois cas
- Valider un BST et les propriétés du parcours infixe
- K-ième plus petit élément, somme d’intervalle et BST vers tableau trié