Valider un BST et les propriétés du parcours infixe
Validez qu’un arbre binaire est un BST à l’aide de bornes minimales et maximales propagées dans l’arbre, et en vérifiant que le parcours infixe produit une séquence triée.
Valider un BST et les propriétés du parcours infixe est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 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 Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Le problème de validation d’un BST
Valider un BST (LeetCode n° 98) est un problème classique d’entretien qui met de nombreux candidats en difficulté. L’approche naïve vérifie uniquement que la valeur de chaque nœud est supérieure à celle de son enfant gauche et inférieure à celle de son enfant droit, mais cette vérification locale est insuffisante. Un nœud d’un sous-arbre peut respecter la règle locale tout en violant la propriété globale du BST. La solution correcte propage dans l’arbre des bornes minimale et maximale valides.
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')Approche par bornes minimale et maximale
Transmettez des bornes inférieure et supérieure lors de la récursion. Pour chaque nœud, vérifiez que low < node.val < high. Lors de la récursion à gauche, mettez à jour la borne supérieure avec node.val (le sous-arbre gauche doit contenir des valeurs inférieures). Lors de la récursion à droite, mettez à jour la borne inférieure avec node.val (le sous-arbre droit doit contenir des valeurs supérieures). Commencez avec low = -infinity et 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)Validation par parcours infixe
Une autre approche de validation utilise la propriété triée du parcours infixe d’un BST : recueillez la séquence infixe et vérifiez qu’elle est strictement croissante. Cette approche est élégante et facile à comprendre. Cependant, elle utilise O(n) d’espace supplémentaire pour stocker la séquence. Une version optimisée utilise un seul pointeur prev pendant le parcours afin de vérifier chaque paire sans stocker la séquence entière.
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)) # FalseComparaison des deux approches de validation
L’approche par bornes minimale et maximale s’exécute en O(n) et utilise O(h) d’espace, correspondant uniquement aux bornes présentes dans la pile d’appels. L’approche avec pointeur précédent en parcours infixe s’exécute également en O(n) et utilise O(h) d’espace. Les deux approches sont optimales. L’approche par bornes minimale et maximale est plus générale et s’adapte naturellement aux problèmes comportant des contraintes supplémentaires. Lors d’un entretien, soyez prêt à présenter les deux approches et à discuter de leurs compromis : montrer que vous connaissez les solutions possibles est un signal très positif.
# 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')Récupérer un BST : deux nœuds intervertis
Récupérer un BST (LeetCode n° 99) consiste à réparer un BST dans lequel exactement deux nœuds ont été intervertis. Lors d’un parcours infixe, un BST correctement ordonné produit une séquence triée. Si deux nœuds sont intervertis, il y aura une ou deux violations où prev.val > current.val. Le premier nœud de la première violation et le second nœud de la dernière violation sont les deux nœuds mal placés : échangez leurs valeurs.
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)Transformer un BST en tableau trié
Convertir un BST en tableau trié est très simple : effectuez un parcours infixe et recueillez les valeurs. Cette opération, qui s’exécute en O(n) et utilise O(n) d’espace, permet rapidement d’appliquer des algorithmes sur les tableaux triés (recherche binaire, deux pointeurs) aux données d’un BST. Elle constitue souvent une étape intermédiaire dans les problèmes de BST en plusieurs parties, comme « fusionner deux BST » ou « trouver la médiane d’un 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]Fusionner deux BST
Pour fusionner deux BST en un seul tableau trié, convertissez chacun en tableau trié en O(n) et O(m), puis fusionnez les deux tableaux triés à l’aide de l’étape de fusion du tri fusion en O(n+m). Temps total : O(n+m). Si vous avez besoin d’obtenir un BST équilibré, transmettez le tableau trié fusionné à l’algorithme de conversion d’un tableau trié en BST. Cette décomposition en sous-problèmes simples caractérise une solution claire et adaptée aux entretiens.
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]Compter les nœuds dans un intervalle d’un BST
Comptez le nombre de nœuds dont les valeurs appartiennent à l’intervalle [low, high]. Un parcours infixe exhaustif s’exécute en O(n). La version qui tient compte du BST élimine certaines branches : si la valeur du nœud courant est inférieure à low, il est inutile d’examiner le sous-arbre gauche, car toutes ses valeurs sont également inférieures à low. De même, éliminez le sous-arbre droit lorsque la valeur courante est supérieure à high. Le cas moyen est O(log n + k), où k représente le nombre de nœuds correspondants.
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 = 32Valeurs en double et BST strict ou non strict
L’invariant standard d’un BST utilise une inégalité stricte : les valeurs du sous-arbre gauche sont strictement inférieures et celles du sous-arbre droit strictement supérieures. Certains problèmes autorisent les doublons, en les plaçant dans le sous-arbre gauche (gauche <= racine) ou dans le sous-arbre droit (racine < droite). Lors de la validation d’un BST, vérifiez toujours la définition donnée dans l’énoncé. L’approche par bornes minimale et maximale gère les deux variantes en adaptant le caractère strict ou inclusif de la vérification des bornes.
# 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')Le parcours infixe comme outil universel pour les BST
Le parcours infixe est l’outil polyvalent des problèmes de BST. Lorsqu’un problème de BST porte sur l’ordre trié, un élément de rang k, des requêtes sur des intervalles ou les propriétés d’une séquence, demandez-vous si un parcours infixe (ou son inverse) peut fournir la réponse. La plupart des problèmes propres aux BST se réduisent à ceci : parcourir dans l’ordre trié et effectuer une opération à chaque étape. Reconnaître rapidement cette correspondance est une compétence essentielle en entretien.
# 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')Valeur la plus proche dans un BST
Trouvez le nœud dont la valeur est la plus proche d’une cible donnée. Exploitez l’ordre du BST : commencez à la racine, mémorisez la valeur la plus proche rencontrée jusqu’à présent et avancez vers la cible (allez à gauche si la cible est inférieure, à droite si elle est supérieure). Cette approche en O(h) est plus efficace qu’un parcours infixe et montre comment exploiter efficacement la propriété du BST pour réduire l’espace de recherche.
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)) # 4Vérification rapide
Évaluez 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 : la validation d’un BST avec des bornes minimale et maximale (pour éviter le piège de la vérification locale), l’alternative du pointeur précédent en parcours infixe pour la validation, ainsi que l’utilisation du parcours infixe comme outil universel des BST pour les sommes sur des intervalles, la valeur la plus proche et les opérations de fusion. Ensuite, nous exploiterons les propriétés du parcours infixe des BST pour trouver le k-ième plus petit élément.
Questions Fréquemment Posées
La leçon « Valider un BST et les propriétés du parcours infixe » est-elle gratuite ?
Oui — le texte complet de « Valider un BST et les propriétés du parcours infixe » 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 Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Valider un BST et les propriétés du parcours infixe » ?
Validez qu’un arbre binaire est un BST à l’aide de bornes minimales et maximales propagées dans l’arbre, et en vérifiant que le parcours infixe produit une séquence triée. Tu pratiques Coding 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 Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding 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 3 sur 4.
Combien de temps prend la leçon « Valider un BST et les propriétés du parcours infixe » ?
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 Coding Interview Prep ?
Oui. Chaque leçon Coding 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é