Jour 39 Day 39 · mercredi 30 septembre 2026 Wednesday 30 September 2026 CS Intermédiaire

Structures & parcours : listes, arbres, graphes Structures & traversals: lists, trees, graphs

Complexités des structures de base, BST et ses parcours, BFS/DFS et représentations de graphes : le cœur des questions d'algo en entretien — avec les réflexes pour choisir la bonne structure au bon moment. Complexities of the basic structures, the BST and its traversals, BFS/DFS and graph representations: the core of interview algorithm questions — with the reflexes to pick the right structure at the right time.

L’essentiel

Quasiment toute question d’algo en entretien commence par un choix de structure de données. Rappel express des briques de base :

Tableau — mémoire contiguë : accès par index en O(1) et très cache-friendly ; mais insérer ou supprimer au milieu décale tout, O(n).
Liste chaînée — des nœuds reliés par pointeurs : insertion/suppression O(1) si on tient déjà le nœud, mais accès et recherche O(n) (on suit les pointeurs un à un).
Pile (stack, LIFO) — push/pop au sommet en O(1) : call stack, undo, DFS, parsing d’expressions.
File (queue, FIFO) — enqueue/dequeue en O(1) : files de tâches, buffers, BFS.
Hash map — recherche/insertion en O(1) moyen : l’outil par défaut dès qu’on associe des clés à des valeurs.

Structure	Accès	Recherche	Insertion	Suppression
Tableau	O(1)	O(n)	O(n)	O(n)
Liste chaînée	O(n)	O(n)	O(1)*	O(1)*
Pile / File	—	—	O(1)	O(1)
Hash map	—	O(1) moy.	O(1) moy.	O(1) moy.
BST équilibré	—	O(log n)	O(log n)	O(log n)
Heap	O(1) min/max	—	O(log n)	O(log n)

* une fois le nœud en main — le trouver reste O(n).

Comment ça marche

Arbres : BST et heap

Un arbre est une hiérarchie sans cycle : une racine, des nœuds, des feuilles. Le BST (binary search tree) y ajoute un invariant : pour chaque nœud, tout le sous-arbre gauche est plus petit, tout le sous-arbre droit plus grand. Chercher, insérer, supprimer : on élimine la moitié de l’arbre à chaque étape → O(log n)… si l’arbre est équilibré. Insérez des valeurs déjà triées et il dégénère en liste chaînée à O(n) — d’où les arbres auto-équilibrés (AVL, rouge-noir) qui se rééquilibrent par rotations pour garantir O(log n), une phrase qui suffit en entretien.

Le heap (tas binaire) relâche l’invariant : chaque parent est simplement ≤ ses enfants (min-heap). Le minimum est à la racine en O(1), insertion et extraction en O(log n) : c’est l’implémentation standard de la priority queue (ordonnanceurs, Dijkstra, « top k éléments »).

Les parcours

              8
            /   \
           3     10
          / \      \
         1   6      14
            / \    /
           4   7  13

In-ordre   (G,N,D) : 1 3 4 6 7 8 10 13 14  ← trié !
Pré-ordre  (N,G,D) : 8 3 1 6 4 7 10 14 13
Post-ordre (G,D,N) : 1 4 7 6 3 13 14 10 8
BFS (par niveaux)  : 8 3 10 1 6 14 4 7 13

DFS (depth-first) plonge au fond avant de revenir — il s’écrit naturellement en récursif, la call stack servant de pile. BFS (breadth-first) explore par niveaux et exige une vraie file. Les trois ordres de DFS sur un arbre binaire : pré-ordre (copier/sérialiser), in-ordre, post-ordre (libérer les enfants avant le parent, calculer les tailles de dossiers).

💡 La propriété star — le parcours in-ordre d’un BST produit les valeurs dans l’ordre trié. Les entretiens l’adorent : « valide ce BST » (in-ordre strictement croissant ?), « k-ième plus petit élément » (le k-ième visité en in-ordre).

Concepts clés à maîtriser

Graphe — des sommets et des arêtes, orientées ou non, pondérées ou non. Un arbre n’est qu’un graphe connexe sans cycle.
Liste vs matrice d’adjacence — liste ({sommet: [voisins]}) : O(V+E) en mémoire, parfaite pour les graphes creux, c’est-à-dire presque tous les cas réels. Matrice V×V : test « A→B ? » en O(1) mais O(V²) en mémoire — réservée aux graphes denses ou minuscules.
BFS = plus court chemin non pondéré — en explorant par niveaux, on atteint chaque sommet la première fois par un chemin au nombre d’arêtes minimal. C’est LA justification à donner en entretien.
Dijkstra en survol — dès que les arêtes ont des poids (positifs), BFS ne suffit plus : Dijkstra le généralise en remplaçant la file par une priority queue qui sort toujours le sommet à distance minimale.
Cycles — détecter un cycle : DFS avec trois états (non visité / en cours / terminé) — retomber sur un sommet « en cours » = cycle. Sans cycle, un graphe orienté admet un tri topologique : l’ordre de traitement des dépendances.
Cas réels partout — npm install : graphe de dépendances, tri topologique pour l’ordre d’installation, détection de cycles ; GPS et routage réseau : Dijkstra/A* ; le DOM : un arbre, querySelector le parcourt en profondeur ; réseaux sociaux : BFS pour les degrés de séparation ; garbage collector : parcours d’atteignabilité depuis les racines.

BFS canonique, avec une vraie file :

from collections import deque

def bfs(graph, start):
    """Distances (en arêtes) depuis start — graphe non pondéré."""
    dist = {start: 0}               # visité ⇔ présent dans dist
    queue = deque([start])          # une FILE : c'est ça, BFS
    while queue:
        node = queue.popleft()      # FIFO : le plus ancien d'abord
        for neighbor in graph[node]:
            if neighbor not in dist:      # jamais vu ?
                dist[neighbor] = dist[node] + 1
                queue.append(neighbor)    # niveau suivant
    return dist   # dist[x] = plus court chemin start → x

🎤 En entretien — « BFS ou DFS, quand ? » BFS quand la distance compte : plus court chemin non pondéré, exploration par niveaux, cible probablement proche — coût mémoire proportionnel à la largeur. DFS quand il faut tout explorer ou analyser la structure : détection de cycles, tri topologique, backtracking, îlots dans une grille — mémoire proportionnelle à la profondeur, et trois lignes en récursif. Si les deux marchent (compter des composantes connexes), prendre le plus simple à écrire : DFS.

En entretien

« Tableau ou liste chaînée : quand choisir quoi ? » — Tableau par défaut : accès O(1), cache-friendly. Liste chaînée seulement si on insère/supprime en tenant déjà la position (LRU cache, file d’attente chaînée) sans jamais avoir besoin d’accès par index. En pratique, les tableaux dynamiques gagnent presque toujours grâce au cache CPU.

« Vérifie qu’un arbre binaire est un BST. » — Le piège : comparer chaque nœud à son seul parent ne suffit pas — un nœud du sous-arbre gauche peut violer un ancêtre lointain. Correct : propager des bornes (min, max) en descendant, ou vérifier que l’in-ordre est strictement croissant.

« Comment détecter un cycle dans un graphe de dépendances ? » — DFS à trois états : blanc (jamais vu), gris (en cours de visite), noir (terminé). Une arête vers un sommet gris = cycle. Alternative : tri topologique de Kahn — s’il n’épuise pas tous les sommets, il y a un cycle. C’est ce que fait un bundler face à des imports circulaires.

« Pourquoi BFS donne-t-il le plus court chemin ? » — Parce qu’il explore par niveaux : tous les sommets à distance k sont visités avant ceux à distance k+1, donc la première visite d’un sommet emprunte un chemin minimal en arêtes. Dès que les arêtes sont pondérées, ça tombe : Dijkstra prend le relais.

« C’est quoi une priority queue, et un usage concret ? » — Une file où l’on extrait toujours l’élément de priorité minimale (ou maximale), implémentée par un heap : extraction O(log n), minimum en O(1). Usages : Dijkstra, ordonnanceur de tâches, « top k », fusion de k listes triées.

Pièges & idées reçues

⚠️ Le visited oublié — sur un graphe (contrairement à un arbre), oublier de marquer les sommets visités transforme BFS/DFS en boucle infinie au premier cycle — et en explosion exponentielle même sans cycle (chemins en losange revisités). Marquer au moment d’empiler/enfiler, pas à la visite, sinon un même sommet entre deux fois dans la file.

« Un BST est équilibré par nature » — non : insérer 1, 2, 3, … le dégénère en liste O(n). Les structures de production (std::map, TreeMap) sont auto-équilibrées, un BST naïf ne l’est pas.
Valider un BST en ne regardant que le parent — le classique des entretiens : l’invariant porte sur tout le sous-arbre, pas sur l’enfant direct.
BFS avec une pile — remplacez la file par une pile et vous obtenez un DFS : c’est la structure de stockage qui fait l’algorithme.
DFS récursif sur un graphe profond — 10⁵ nœuds en ligne = stack overflow ; version itérative avec pile explicite.
« Hash map O(1), donc toujours mieux » — pas d’ordre, pas de « plus proche voisin », pas de parcours trié : un BST ou un heap fait ce qu’un hash map ne sait pas faire.
Dijkstra avec des poids négatifs — résultats silencieusement faux ; il faut Bellman-Ford dans ce cas.

Pour aller plus loin

VisuAlgo : BST, heap, parcours de graphes animés pas à pas — le meilleur outil pour « voir » les algos
Red Blob Games — Introduction to A* : BFS → Dijkstra → A*, interactif et progressif
Big-O Cheat Sheet : toutes les complexités sur une page
NeetCode Roadmap : la progression trees → graphs avec les problèmes classiques d’entretien
S’exercer : implémenter BFS et DFS sur un petit graphe en dict Python, puis ajouter la détection de cycle — 30 lignes qui couvrent la moitié des questions d’algo

The essentials

Almost every interview algorithm question starts with a data structure choice. Express recap of the building blocks:

Array — contiguous memory: O(1) access by index and very cache-friendly; but inserting or deleting in the middle shifts everything, O(n).
Linked list — nodes connected by pointers: O(1) insertion/deletion if you already hold the node, but O(n) access and search (you follow pointers one by one).
Stack (LIFO) — push/pop at the top in O(1): call stack, undo, DFS, expression parsing.
Queue (FIFO) — enqueue/dequeue in O(1): task queues, buffers, BFS.
Hash map — O(1) average search/insertion: the default tool whenever you map keys to values.

Structure	Access	Search	Insertion	Deletion
Array	O(1)	O(n)	O(n)	O(n)
Linked list	O(n)	O(n)	O(1)*	O(1)*
Stack / Queue	—	—	O(1)	O(1)
Hash map	—	O(1) avg.	O(1) avg.	O(1) avg.
Balanced BST	—	O(log n)	O(log n)	O(log n)
Heap	O(1) min/max	—	O(log n)	O(log n)

* once you hold the node — finding it is still O(n).

How it works

Trees: BST and heap

A tree is a hierarchy without cycles: a root, nodes, leaves. The BST (binary search tree) adds an invariant: for every node, the entire left subtree is smaller, the entire right subtree larger. Search, insert, delete: you eliminate half the tree at each step → O(log n)… if the tree is balanced. Insert already-sorted values and it degenerates into a linked list at O(n) — hence self-balancing trees (AVL, red-black) that rebalance through rotations to guarantee O(log n), one sentence that’s enough in an interview.

The heap (binary heap) relaxes the invariant: each parent is simply ≤ its children (min-heap). The minimum sits at the root in O(1), insertion and extraction in O(log n): it’s the standard implementation of the priority queue (schedulers, Dijkstra, “top k elements”).

The traversals

              8
            /   \
           3     10
          / \      \
         1   6      14
            / \    /
           4   7  13

In-order   (L,N,R) : 1 3 4 6 7 8 10 13 14  ← sorted!
Pre-order  (N,L,R) : 8 3 1 6 4 7 10 14 13
Post-order (L,R,N) : 1 4 7 6 3 13 14 10 8
BFS (by levels)    : 8 3 10 1 6 14 4 7 13

DFS (depth-first) dives to the bottom before coming back — it writes naturally as recursion, the call stack serving as the stack. BFS (breadth-first) explores level by level and requires an actual queue. The three DFS orders on a binary tree: pre-order (copy/serialize), in-order, post-order (free the children before the parent, compute folder sizes).

💡 The star property — the in-order traversal of a BST produces the values in sorted order. Interviews love it: “validate this BST” (strictly increasing in-order?), “k-th smallest element” (the k-th visited in-order).

Key concepts to master

Graph — vertices and edges, directed or not, weighted or not. A tree is just a connected acyclic graph.
Adjacency list vs matrix — list ({vertex: [neighbors]}): O(V+E) memory, perfect for sparse graphs, i.e. almost every real-world case. V×V matrix: “A→B?” test in O(1) but O(V²) memory — reserved for dense or tiny graphs.
BFS = unweighted shortest path — by exploring level by level, you reach each vertex for the first time through a path with the minimum number of edges. That’s THE justification to give in an interview.
Dijkstra at a glance — as soon as edges have (positive) weights, BFS is no longer enough: Dijkstra generalizes it by replacing the queue with a priority queue that always pops the vertex with the smallest distance.
Cycles — detecting a cycle: DFS with three states (unvisited / in progress / done) — hitting an “in progress” vertex = cycle. Without cycles, a directed graph admits a topological sort: the processing order for dependencies.
Real cases everywhere — npm install: dependency graph, topological sort for install order, cycle detection; GPS and network routing: Dijkstra/A*; the DOM: a tree, querySelector walks it depth-first; social networks: BFS for degrees of separation; garbage collectors: reachability traversal from the roots.

Canonical BFS, with an actual queue:

from collections import deque

def bfs(graph, start):
    """Distances (in edges) from start — unweighted graph."""
    dist = {start: 0}               # visited ⇔ present in dist
    queue = deque([start])          # a QUEUE: that's what BFS is
    while queue:
        node = queue.popleft()      # FIFO: oldest first
        for neighbor in graph[node]:
            if neighbor not in dist:      # never seen?
                dist[neighbor] = dist[node] + 1
                queue.append(neighbor)    # next level
    return dist   # dist[x] = shortest path start → x

🎤 In an interview — “BFS or DFS, when?” BFS when distance matters: unweighted shortest path, level-by-level exploration, target probably close — memory cost proportional to the width. DFS when you must explore everything or analyze structure: cycle detection, topological sort, backtracking, islands in a grid — memory proportional to the depth, and three lines of recursion. If both work (counting connected components), pick the simplest to write: DFS.

In an interview

“Array or linked list: when do you pick which?” — Array by default: O(1) access, cache-friendly. Linked list only when you insert/delete while already holding the position (LRU cache, chained queue) and never need index access. In practice, dynamic arrays win almost every time thanks to the CPU cache.

“Check that a binary tree is a BST.” — The trap: comparing each node to its parent alone isn’t enough — a node in the left subtree can violate a distant ancestor. Correct: propagate (min, max) bounds while descending, or check the in-order traversal is strictly increasing.

“How do you detect a cycle in a dependency graph?” — Three-state DFS: white (never seen), gray (being visited), black (done). An edge to a gray vertex = cycle. Alternative: Kahn’s topological sort — if it doesn’t exhaust all vertices, there’s a cycle. That’s what a bundler does when facing circular imports.

“Why does BFS give the shortest path?” — Because it explores by levels: all vertices at distance k are visited before those at distance k+1, so the first visit of a vertex uses a path with the minimum number of edges. As soon as edges are weighted, this breaks: Dijkstra takes over.

“What’s a priority queue, and one concrete use?” — A queue where you always extract the minimum-priority (or maximum) element, implemented with a heap: O(log n) extraction, O(1) minimum. Uses: Dijkstra, task schedulers, “top k”, merging k sorted lists.

Pitfalls & misconceptions

⚠️ The forgotten visited — on a graph (unlike a tree), forgetting to mark visited vertices turns BFS/DFS into an infinite loop at the first cycle — and into exponential blowup even without one (diamond-shaped paths revisited). Mark when enqueuing/pushing, not when visiting, otherwise the same vertex enters the queue twice.

“A BST is balanced by nature” — no: inserting 1, 2, 3, … degenerates it into an O(n) list. Production structures (std::map, TreeMap) are self-balancing, a naive BST is not.
Validating a BST by only checking the parent — the interview classic: the invariant covers the whole subtree, not just the direct child.
BFS with a stack — swap the queue for a stack and you get DFS: the storage structure is the algorithm.
Recursive DFS on a deep graph — 10⁵ nodes in a line = stack overflow; go iterative with an explicit stack.
“Hash map is O(1), so always better” — no ordering, no “nearest neighbor”, no sorted iteration: a BST or a heap does what a hash map can’t.
Dijkstra with negative weights — silently wrong results; you need Bellman-Ford in that case.

Going further

VisuAlgo: BST, heap, graph traversals animated step by step — the best tool to “see” the algorithms
Red Blob Games — Introduction to A*: BFS → Dijkstra → A*, interactive and progressive
Big-O Cheat Sheet: every complexity on one page
NeetCode Roadmap: the trees → graphs progression with the classic interview problems
Practice: implement BFS and DFS on a small graph as a Python dict, then add cycle detection — 30 lines that cover half of all algorithm questions

S'entraîner sur ce sujet → Practice this topic →