- Le rituel TAP. Invariant, variant, conclusion, complexité — c00, pas 1. Ici il change de forme : il n'y a plus de boucle, donc plus d'« entrée de tour » où réciter l'invariant. Le pas 3 dit où il se loge.
- Invariant = conteneur + tranche + « exactement ». c00, pas 2. Sur un arbre, la tranche est le sous-arbre de n et le conteneur est la valeur renvoyée : l'invariant devient un contrat.
- Variant = entier ≥ 0 strictement décroissant. c00, pas 3. Ce n'est pas un indice : c'est la taille du sous-arbre, qui perd au moins le nœud courant à chaque appel.
- Complexité composée. c00, pas 5. Le temps est facile (O(1) par nœud) ; ce qui se discute est l'espace, et il ne vaut pas O(1) — pas 4.
- Les flèches de c04. Un arbre est une liste chaînée qui bifurque : mêmes pointeurs, même absence d'indice. La différence tient en un mot — il y a deux suites possibles, donc il faut une pile pour retenir celle qu'on n'a pas prise.
up. C'est ce qui rend la pile nécessaire : la remontée n'existe que dans les appels.
H2La récursion est autorisée, et la pile d'appels compte dans l'espace. Dire « O(1) » d'un DFS récursif est faux : c'est O(h), et h peut valoir n.
H3BST strict : pas de doublons, donc les bornes sont des inégalités strictes. Autoriser les doublons impose de choisir un côté et de remplacer un « < » par un « ≤ » — autre énoncé, autre code.
H4Conventions chiffrées, à annoncer avant de coder : la hauteur se compte en nœuds (arbre vide 0, feuille 1), le diamètre en arêtes. Les deux conventions coexistent dans la nature ; seule l'ambiguïté coûte.
H5On énonce le squelette et les phrases. Le corps se remplit devant l'interlocuteur : une sheet de coding ne contient jamais la solution complète.
La chaîne
Le signal, et le contre-signal tronc
Une structure hiérarchique sans cycle, et une question qui porte sur un sous-arbre : hauteur, diamètre, chemin, somme, validité BST, niveaux. Toutes ont la même forme — la réponse pour n se fabrique à partir des réponses pour ses enfants.
Le contre-signal est net : un graphe avec cycles. Sans cycle et avec un seul parent, on ne peut pas revenir sur ses pas, donc rien à mémoriser ; dès qu'un cycle existe il faut un ensemble de vus, et c'est c06.
« La question porte sur un sous-arbre et un sous-arbre est un arbre, donc j'écris une fonction qui répond pour un nœud en appelant ses enfants, donc tout ce que j'ai à décider est ce qu'elle promet et quand elle traite le nœud. »
L'arbre A, par niveaux : [4, 2, 6, 1, 3, 5, 7]. Racine 4 ; enfants 2 et 6 ; feuilles 1, 3, 5, 7. Parfaitement équilibré, 7 nœuds, hauteur 3. Il sert à tout : les trois ordres, la hauteur, le diamètre, les niveaux.
L'arbre B, le contre-exemple : [5, 1, 6, ∅, ∅, 4, 7]. Racine 5, enfants 1 et 6, et sous 6 les enfants 4 et 7. Il passe le test « gauche < nœud < droit » à tous les nœuds et n'est pas un BST — pas 6.
Trois familles de questions, un seul geste. Agréger (hauteur, somme, diamètre) : post-ordre. Ordonner (BST trié, k-ième plus petit) : in-ordre. Copier, sérialiser, propager vers le bas (bornes, somme restante) : pré-ordre.
Ce que la sheet n'aborde pas. Les arbres n-aires (une boucle sur enfants remplace l et r, rien d'autre ne change) et l'équilibrage (AVL, rouge-noir) : autre sujet, autre sheet.
Le pattern : un seul choix, quand on traite le nœud tronc
Toute fonction récursive sur un arbre a la même charpente : un cas de base sur None, deux appels, une combinaison.
Les deux appels sont figés — gauche puis droit. La seule liberté est la place de n.valeur : avant les appels (pré), entre les deux (in), après (post). Trois ordres, trois usages : pré descend de l'information (copier, sérialiser, propager des bornes), in range (l'in-ordre d'un BST est trié), post remonte (hauteur, diamètre, libérer).
« Le cas de base est l'arbre vide et la combinaison est une ligne, donc il ne me reste qu'une décision : je traite le nœud avant, entre ou après les appels, donc je choisis pré si je descends une information, in si je veux l'ordre, post si je remonte une valeur. »
Trois lignes. Le nœud est traité après les deux appels (le 1 + s'applique à ce qui remonte) : c'est un post-ordre, et c'est le cas de tout ce qui agrège.
Les trois ordres sur A, chacun sur une ligne — la valeur du nœud écrite avant, entre, après :
- pré (nœud, g, d) →
4, 2, 1, 3, 6, 5, 7— copier, sérialiser, descendre des bornes. - in (g, nœud, d) →
1, 2, 3, 4, 5, 6, 7— trié, et c'est là tout le test du BST. - post (g, d, nœud) →
1, 3, 2, 5, 7, 6, 4— hauteur, diamètre, libérer.
La même fonction, la même récursion. Ces trois suites sortent du même parcours : les nœuds sont visités dans le même ordre physique, seule change la ligne où l'on écrit la valeur. C'est ce que la figure fait voir.
L'arbre A. La position horizontale est l'ordre in-ordre : les abscisses valent 1 à 7 de gauche à droite, et les valeurs aussi — c'est exactement ce que dit « l'in-ordre d'un BST est trié ». Clique pré, in, post : les nœuds se numérotent dans l'ordre de visite, le chemin vert est la pile d'appels (racine → nœud courant), et le compteur de droite l'écrit — au 3e pas du pré-ordre, pile = [4, 2, 1], trois cadres, jamais plus de 3 pour cet arbre. Clique hauteur : le même post-ordre, mais chaque nœud reçoit ce que renvoie f — les feuilles 1, puis 2 et 6 à 2, la racine à 3. Le fait à retenir : les trois boutons parcourent l'arbre identiquement, seule la ligne où l'on écrit change.
L'invariant est le contrat de f tronc
Il n'y a pas de boucle, donc pas d'« entrée de tour » où réciter l'invariant. Il se loge ailleurs : dans ce que f promet, et il se vérifie en deux points, exactement comme pour une boucle.
Initialisation — le cas de base : h(None) = 0, l'arbre vide n'a aucun nœud sur aucun chemin. Préservation — la combinaison : si les deux appels tiennent leur promesse, le plus long chemin depuis n est le nœud n plus le plus long des deux, donc 1 + max(…) tient la promesse à son tour.
« Je suppose le contrat vrai pour les deux enfants, donc le plus long chemin depuis le nœud vaut un de plus que le meilleur des deux, donc la combinaison tient le contrat, donc il est vrai partout puisqu'il est vrai sur l'arbre vide. »
Post-ordre sur A, dans l'ordre où les valeurs remontent : h(1) = 1, h(3) = 1, h(2) = 2, h(5) = 1, h(7) = 1, h(6) = 2, h(4) = 3. Chaque valeur n'utilise que les deux qui viennent d'être posées — jamais rien d'autre. C'est le bouton « hauteur » de la figure 1.
Vérifié à l'exécution. Ce squelette confronté à un comptage de niveaux par BFS (implémentation indépendante) sur 200 000 arbres aléatoires (0 à 8 nœuds, formes et valeurs tirées au hasard) : 0 désaccord.
Le diamètre : deux quantités, une seule remontée. Le contrat dit « je renvoie la hauteur » et « je mets à jour un maximum global avec hg + hd ». Sur A, à la racine : 2 + 2 = 4 arêtes — le chemin 1 – 2 – 4 – 6 – 5. Le piège est de croire que le diamètre passe par la racine ; il passe par le nœud qui maximise la somme, et c'est précisément pour ça que le maximum est global et non renvoyé.
Le test de trente secondes. Avant d'écrire le corps : « qu'est-ce que f promet, exactement, sur le sous-arbre de n ? » Si la phrase ne se dit pas en une ligne, le code ne se trouvera pas.
Le variant, et l'espace qui n'est pas O(1)
Le variant est la taille du sous-arbre : un entier ≥ 0, et chaque appel le fait décroître strictement — le sous-arbre d'un enfant a perdu au moins le nœud courant. Terminaison acquise, sans compter les nœuds.
L'espace est le seul chiffre qu'on rate. Il ne dépend pas de n mais de h : O(log n) si l'arbre est équilibré, O(n) s'il dégénère en liste. Et la pile est bien réelle — elle plante.
« Chaque nœud est visité une fois et coûte O(1), donc le temps est linéaire, et la récursion garde un cadre par ancêtre du nœud courant, donc l'espace est la profondeur de la pile, donc O(h) — qui vaut n quand l'arbre dégénère. »
| arbre | pile = h |
|---|---|
| A équilibré, n = 7 | 3 cadres |
| A dégénéré, n = 7 | 7 cadres |
| parfait, n ≈ 106 | 20 cadres |
| liste, n = 1 000 | RecursionError |
Le seuil, mesuré. Avec la limite CPython par défaut (sys.getrecursionlimit() = 1000), h passe jusqu'à une chaîne de 997 nœuds et lève RecursionError à 998 — les quelques cadres manquants sont ceux de l'appelant. Un arbre parfait de hauteur 20 porte 1 048 575 nœuds et ne coûte que 20 cadres ; une liste de 1 000 nœuds, elle, plante. C'est h qui décide, jamais n.
La sortie de secours, et ce qu'elle coûte. DFS itératif avec une pile explicite : même O(h), mais sur le tas, donc pas de RecursionError. sys.setrecursionlimit marche aussi — à condition de le dire : on déplace la limite, on ne la supprime pas, et le segfault remplace l'exception.
BFS : la taille de la file dit où finit le niveau
Quand la question parle de niveaux — « par profondeur », « le plus proche », « vue de droite » — le DFS ne convient plus : il plonge. Une file donne l'ordre par niveaux, mais la file mélange les niveaux, puisqu'on y ajoute les enfants pendant qu'on retire les parents.
k = len(file) capturé avant la boucle du niveau ⇒ les k premiers défilés sont exactement ce niveauUne seule ligne porte toute l'idée : for _ in range(len(q)). Elle fige k au moment où la file ne contient que le niveau courant — après, elle contient déjà des enfants.
« La file ne contient que le niveau courant juste avant d'entamer le niveau, donc sa taille à cet instant est le nombre de nœuds du niveau, donc je la capture avant de défiler, donc les k nœuds suivants forment le niveau et tout ce qui s'empile derrière est le suivant. »
Sur A. Tailles capturées : 1, puis 2, puis 4 — niveaux [4], [2, 6], [1, 3, 5, 7]. Trois tours de la boucle extérieure ⇒ hauteur 3, calculée sans récursion : c'est l'implémentation indépendante qui a servi de témoin au pas 3.
Sans la capture (while q à l'intérieur au lieu de for _ in range(len(q))) : la boucle intérieure vide la file et tout ce qu'on y ajoute. Résultat sur A : un seul niveau, [4, 2, 6, 1, 3, 5, 7] — l'ordre par niveaux est juste, le découpage a disparu, et aucune erreur n'est levée.
Profondeur minimale. Premier niveau qui contient une feuille. Sur A : niveau 3. Sur B : niveau 2 — le nœud 1 est une feuille. C'est le cas où le BFS bat le DFS : il s'arrête à la première feuille rencontrée au lieu d'explorer tout l'arbre.
Coût. O(n) en temps comme le DFS ; en espace, la largeur maximale et non la hauteur — O(n/2) sur un arbre parfait. Les deux parcours échangent exactement leur faiblesse : profond et étroit pour le DFS, large et plat pour le BFS.
k = len(q) capturé avant de défilerLes cases sont les nœuds de A dans l'ordre où la file les rend — c'est-à-dire l'ordre par niveaux, 4, 2, 6, 1, 3, 5, 7 ; l'indice sous chaque case est son rang de défilement. Fais « pas › » : le cadre vert est le niveau en cours de traitement, c'est-à-dire les k cases que la capture vient de figer, et l'ambre ce qui est déjà sorti. Regarde la ligne du bas : k vaut 1, puis 2, puis 4, et à chaque fois le cadre vert contient exactement k cases. La capture est ce qui dessine les frontières : sans elle, le vert couvrirait les sept cases d'un coup, l'ordre resterait bon et les niveaux auraient disparu.
Le BST se valide par des bornes, pas par les enfants tronc
La propriété BST n'est pas locale. Elle dit : tout le sous-arbre gauche est < n, tout le droit est > n — pas seulement les deux enfants. La récursion qui la vérifie descend donc une information : c'est un pré-ordre.
Appel initial valid(racine, −∞, +∞). Chaque descente resserre une borne et garde l'autre : un nœud hérite ainsi des contraintes de tous ses ancêtres, pas seulement de son parent.
« La propriété porte sur tout le sous-arbre et pas sur les enfants, donc chaque nœud doit tenir dans un intervalle, donc je descends cet intervalle en le resserrant à chaque pas, donc un nœud voit les contraintes de tous ses ancêtres et pas seulement celle de son père. »
B = [5, 1, 6, ∅, ∅, 4, 7]. Test local à chaque nœud : 1 < 5 < 6 ✓, 4 < 6 < 7 ✓ — valide partout. Test par bornes : la racine reçoit (−∞, +∞), le nœud 6 reçoit (5, +∞), et son fils gauche 4 reçoit (5, 6). Or 4 ∉ (5, 6) : refusé. Le 4 est sous le droit de 5, donc il devait dépasser 5.
Le témoin qui ne ment pas. L'in-ordre de B vaut 1, 5, 4, 6, 7 — pas trié, le 4 arrive après le 5. C'est la seconde façon de valider un BST, et elle est équivalente : 0 désaccord entre « bornes » et « in-ordre strictement croissant » sur 200 000 arbres aléatoires.
Combien de faux positifs ? Sur ces 200 000 arbres (0 à 7 nœuds, valeurs dans 1…7), 67 015 passent le test local ; parmi eux 3 183 ne sont pas des BST — 4,75 %. Un test au hasard a donc toutes les chances de passer : le bug ne se révèle pas à l'essai.
Le squelette. valid(n, lo, hi) : None ⇒ vrai ; sinon lo < n.val < hi et valid(n.gauche, lo, n.val) et valid(n.droit, n.val, hi). Quatre lignes, et les deux None initiaux (plutôt que ±inf) évitent de comparer des flottants à des entiers.
L'arbre B, [5, 1, 6, ∅, ∅, 4, 7]. Clique test local : chaque nœud interne compare sa valeur à ses enfants et tout passe au vert — 1 < 5 < 6, 4 < 6 < 7. Clique bornes : le même arbre reçoit l'intervalle que ses ancêtres lui imposent, affiché sous chaque nœud ; la racine a (−∞, +∞), le nœud 6 hérite de (5, +∞) parce qu'il est à droite de 5, et son fils gauche n'a plus droit qu'à (5, 6). Le 4 passe au rouge : il respecte son père et viole son grand-père. Ce que la figure fait voir : le vert du premier bouton ne regarde qu'une arête à la fois, les bornes du second descendent depuis la racine — et c'est exactement la différence entre un test qui accepte des arbres faux et un test qui conclut.
Où ça casse casse
Le cas fatal est silencieux : valider un BST en comparant chaque nœud à ses seuls enfants. Aucune exception, aucun ralentissement — la fonction renvoie True sur un arbre qui n'est pas un BST, poliment.
Le mécanisme : la contrainte d'un nœud ne vient pas de son parent mais de tous ses ancêtres, et un test local n'en voit qu'un. Chaque fois qu'on descend à gauche on plafonne, à droite on planche ; ces bornes s'accumulent, et le test local les jette.
« Le test local ne regarde qu'une arête, donc il ignore les bornes héritées des ancêtres, donc il accepte un nœud qui viole son grand-père, donc il renvoie vrai sur un arbre qui n'est pas un BST, sans lever la moindre erreur. »
Trois nœuds suffisent-ils ? Non — avec trois nœuds, parent et grand-parent se confondent. Il en faut quatre, et B est le plus petit témoin utile : [5, 1, 6, ∅, ∅, 4, 7]. Version réduite à quatre nœuds : 5, à droite 6, sous 6 à gauche 4. Le test local voit 4 < 6 et dit oui ; les bornes voient 4 ∉ (5, +∞) et disent non.
La phrase qui tue. « Le 4 est dans le sous-arbre droit de 5, donc il doit dépasser 5 — et il vaut 4. » Elle se dit sans dessiner.
Mesuré. Sur 200 000 arbres tirés au hasard, le test local et le test par bornes divergent 3 183 fois — soit 4,75 % des arbres que le test local accepte. Un cas sur vingt : assez rare pour survivre à trois essais à la main, assez fréquent pour tomber en entretien.
Le deuxième silence, même famille. « Feuille » veut dire aucun enfant. Écrire if n.l is None or n.r is None au lieu de and dans un « chemin de somme cible » traite un nœud à un seul enfant comme une feuille : sur l'arbre 1 → (gauche) 2, cible 1, la version fautive répond vrai (le chemin 1 s'arrête à la racine) alors que le seul chemin racine→feuille vaut 3 ; et pour la cible 3 elle répond faux. Mesuré : 16,8 % de désaccords sur 200 000 tirages.
RecursionErrorvers 1 000 niveaux. Un arbre dégénéré (une liste) atteint la limite CPython — mesuré : 998 nœuds avecsys.getrecursionlimit() = 1000. Réponse : DFS itératif avec une pile explicite, ousys.setrecursionlimiten le disant — on déplace la limite, on ne la retire pas.- Feuille = « pas d'enfant ».
n.l is None and n.r is None. Avecor, un nœud à un seul enfant devient une feuille : chemin de somme faux, profondeur minimale fausse — et rien ne plante. - BFS par niveaux sans capturer
len(q)avant la boucle du niveau : les niveaux fusionnent en un seul. L'ordre reste correct, la structure disparaît. - Le maximum du diamètre en variable « globale ». Sans
nonlocal(ou un objet mutable, ou un attribut), l'affectation crée une variable locale à l'appel et le maximum ne remonte pas : la fonction renvoie la valeur initiale, souvent 0.
Résumé
- Récursion = contrat. L'invariant est ce que f(n) promet sur le sous-arbre de n ; vrai sur
None, préservé par la combinaison. - Pré / in / post : le seul choix est quand on traite le nœud. Pré descend, in range — l'in-ordre d'un BST est trié —, post remonte.
- Variant = taille du sous-arbre. O(n) en temps, O(h) en espace : jamais O(1), et O(n) si l'arbre dégénère.
- BFS par niveaux :
k = len(q)capturé au début du niveau ; sans ça les niveaux fusionnent, sans erreur. - BST : bornes propagées depuis la racine, jamais les seuls enfants.
[5, 1, 6, ∅, ∅, 4, 7]passe le test local et n'est pas un BST — 4 ∉ (5, 6).
Chaîne verbalisée — une prise, à voix haute
- Quel est l'invariant d'une fonction récursive sur un arbre ?Son contrat sur le sous-arbre : ce que f(n) promet de renvoyer pour le sous-arbre de n. Il se vérifie en deux points, comme pour une boucle — vrai sur None (le cas de base), préservé par la combinaison des deux appels.
- Quel ordre pour la hauteur, pour un BST trié, pour sérialiser ?Post, in, pré. Post remonte une valeur agrégée, in donne l'ordre croissant d'un BST, pré descend de l'information — une copie, une sérialisation, des bornes.
- Pourquoi « gauche < nœud < droit » ne valide-t-il pas un BST ?Parce que la contrainte d'un nœud vient de tous ses ancêtres, pas de son seul parent. Contre-exemple : racine 5, à droite 6, et sous 6 à gauche un 4. Le test local passe ; les bornes donnent (5, 6) pour ce 4, et il est dehors.
- Complexité en espace d'un DFS récursif ?O(h), la profondeur de la pile d'appels : O(log n) si l'arbre est équilibré, O(n) s'il dégénère en liste — et à mille niveaux, RecursionError. Jamais O(1).
- Comment un BFS sait-il où finit un niveau ?En capturant len(q) juste avant de défiler le niveau : à cet instant la file ne contient que ce niveau, donc sa taille en est le nombre de nœuds. Sans la capture, les enfants ajoutés en cours de route fusionnent tous les niveaux en un seul.
Ponts et cartes
coding::arbres (le signal, le contrat de f, le variant, O(h) en espace) · coding::dfs (pré / in / post et ce que chacun sert, la pile = le chemin racine → courant) · coding::bfs (la file, len(q) capturé, la profondeur minimale) · coding::bst (les bornes propagées et le contre-exemple à quatre nœuds).
Une carte qui résiste après cette chaîne est une carte à refondre, pas une section à relire.