Pattern Guide
Euler Path & Circuit
"Visit every EDGE exactly once. Hierholzer's algorithm. Degree condition check."
An Euler path visits every edge exactly once. An Euler circuit does so and returns to the start. Condition for undirected: connected + 0 or 2 odd-degree nodes (0 for circuit, 2 for path). For directed: connected + each node has in-degree = out-degree (circuit), or exactly one node has out-degree - in-degree = 1 (start) and one has in-degree - out-degree = 1 (end). Hierholzer's algorithm constructs the path in O(E).
Problems you can solve with this pattern
4 problems · click any to start solving
// Directed Euler path (Hierholzer's)
function eulerPath(n, edges) {
const adj = Array.from({length: n}, () => []);
const inDeg = new Array(n).fill(0);
const outDeg = new Array(n).fill(0);
for (const [u, v] of edges) {
adj[u].push(v);
outDeg[u]++;
inDeg[v]++;
}
// Find start node: prefer node with outDeg - inDeg = 1, else any node with outDeg > 0
let start = 0;
for (let i = 0; i < n; i++) if (outDeg[i] - inDeg[i] === 1) { start = i; break; }
// Hierholzer's: iterative post-order
const stack = [start], path = [];
while (stack.length) {
const u = stack.at(-1);
if (adj[u].length) {
stack.push(adj[u].pop()); // use next edge
} else {
path.push(stack.pop()); // dead end → add to path
}
}
return path.reverse(); // O(E) total
}Hierholzer's algorithm: start at a valid start node. Follow edges greedily (DFS), marking edges as used. When stuck (no more edges), backtrack and insert current node into the result. This builds the Euler path in reverse — the recursive DFS post-order naturally handles dead-ends before continuing the main path. Key: use adjacency list with efficient edge removal (splice or pointer).
// Directed Euler path (Hierholzer's)
function eulerPath(n, edges) {
const adj = Array.from({length: n}, () => []);
const inDeg = new Array(n).fill(0);
const outDeg = new Array(n).fill(0);
for (const [u, v] of edges) {
adj[u].push(v);
outDeg[u]++;
inDeg[v]++;
}
// Find start node: prefer node with outDeg - inDeg = 1, else any node with outDeg > 0
let start = 0;
for (let i = 0; i < n; i++) if (outDeg[i] - inDeg[i] === 1) { start = i; break; }
// Hierholzer's: iterative post-order
const stack = [start], path = [];
while (stack.length) {
const u = stack.at(-1);
if (adj[u].length) {
stack.push(adj[u].pop()); // use next edge
} else {
path.push(stack.pop()); // dead end → add to path
}
}
return path.reverse(); // O(E) total
}- Undirected circuit: all vertices have even degree
- Undirected path: exactly 2 vertices have odd degree (they are start/end)
- Directed circuit: in-degree = out-degree for every vertex
- Directed path: one vertex has out - in = 1 (start), one has in - out = 1 (end)
Hierholzer's key: When stuck (no outgoing edges), pop current node to the result path, backtrack. Post-order insertion naturally handles "bridge" edges.
Complexity: O(E) with adjacency list + pointer to next unvisited edge.
Applications: Itinerary reconstruction, De Bruijn sequences, word chains (each word's last char = next word's first char).