Arbres et BST : penser en diviser pour régner
La structure hiérarchique derrière une bonne partie des problèmes d'entretien — et le réflexe récursif qui les résout.
Un arbre est une structure hiérarchique de nœuds, chacun ayant zéro ou plusieurs enfants, sans cycle. Un arbre binaire limite chaque nœud à au plus deux enfants (gauche/droit) — c'est la structure sous-jacente de beaucoup de problèmes d'entretien.
Un arbre binaire de recherche (BST) impose un ordre : pour chaque nœud, tout le sous-arbre gauche contient des valeurs plus petites, et le sous-arbre droit des valeurs plus grandes. Ça permet recherche, insertion et suppression en O(log n) en moyenne — mais O(n) dans le pire cas si l'arbre est déséquilibré (il dégénère alors en liste chaînée).
Trois parcours en profondeur (DFS) fondamentaux, tous naturellement récursifs : préordre (racine, gauche, droite), inordre (gauche, racine, droite — donne les valeurs triées sur un BST), postordre (gauche, droite, racine). Chacun s'implémente aussi itérativement avec une pile.
Le parcours en largeur (BFS), niveau par niveau, utilise une file au lieu d'une pile — utile pour des problèmes comme « la vue de droite de l'arbre » ou « la profondeur minimale ».
Réflexe à adopter : la plupart des problèmes d'arbres se résolvent en définissant ce qu'une fonction récursive retourne pour un sous-arbre (sa hauteur, si c'est valide, sa somme...), puis en composant les résultats gauche/droite au niveau du nœud courant. C'est le pattern « diviser pour régner » appliqué à l'arbre.
Vidéo
Maximum Depth of Binary Tree - 3 Solutions (Leetcode 104) — NeetCodeQuiz
1. Dans un BST, pour un nœud donné, le sous-arbre gauche contient :
2. Quel parcours donne les valeurs d'un BST dans l'ordre trié ?
3. Le parcours en largeur (BFS) d'un arbre utilise typiquement :
4. Le pire cas de recherche dans un BST déséquilibré est :