Arbres et BST : penser en diviser pour régner
AvancéLa plupart des problèmes d'arbres se résolvent en définissant ce que retourne une fonction récursive pour un sous-arbre, puis en composant gauche et droite.
Un arbre est une hiérarchie de nœuds sans cycle ; un arbre binaire limite chaque nœud à deux enfants. Un BST (arbre binaire de recherche) impose : tout le sous-arbre gauche est plus petit, tout le sous-arbre droit plus grand.
| Opération | BST équilibré | BST dégénéré (liste) |
|---|---|---|
| Recherche, insertion, suppression | O(log n) | O(n) |
Les parcours en profondeur (DFS)#
| Parcours | Ordre | Usage |
|---|---|---|
| Préordre | racine, gauche, droite | Copier / sérialiser un arbre |
| Inordre | gauche, racine, droite | Sur un BST, donne les valeurs triées |
| Postordre | gauche, droite, racine | Calculer à partir des enfants (hauteur, suppression) |
Hauteur maximale#
Fonction récursive : la hauteur d'un nœud vaut 1 + la plus grande hauteur de ses enfants.
class TreeNode {
constructor(
public val: number,
public left: TreeNode | null = null,
public right: TreeNode | null = null,
) {}
}
function maxDepth(root: TreeNode | null): number {
if (!root) return 0; // cas de base
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
Parcours en largeur (BFS) : niveau par niveau#
On utilise une file : à chaque tour, on traite exactement les nœuds présents au niveau courant.
function levelOrder(root: TreeNode | null): number[][] {
const levels: number[][] = [];
let queue: TreeNode[] = root ? [root] : [];
while (queue.length) {
levels.push(queue.map((n) => n.val));
queue = queue.flatMap((n) => [n.left, n.right].filter((c): c is TreeNode => c !== null));
}
return levels;
}
Astuce : validez un BST avec un parcours inordre (les valeurs doivent être strictement croissantes) ou en propageant une borne min/max vers le bas. Comparer seulement un nœud à ses enfants directs est l'erreur classique.