cf.completefrontend
GRAPHS · ADVANCED

Eulerian path (Hierholzer's algorithm)

Find a route that uses every edge exactly once, like drawing a figure without lifting the pen, by walking until stuck and splicing in detours.

Time O(n + e)Space O(n + e)2 practice problemsStep-through picture

The idea

An Eulerian path uses every edge of a graph exactly once. It is the puzzle of drawing a figure without lifting your pen or going over a line twice. If it ends where it started, it is called an Eulerian circuit.

Whether one exists depends only on counting. In a directed graph, compare each node's out-degree (edges leaving) and in-degree (edges arriving). A path exists when every node has them equal, except that at most one node has one extra out-edge (the start) and at most one has one extra in-edge (the end), and all edges are connected. For undirected graphs, the rule is: zero or two nodes have an odd number of edges.

Hierholzer's algorithm builds the path. It walks from the start, using up edges, until it gets stuck. Getting stuck means that node is the end of the remaining route, so it is written to the answer. Then it backs up and continues from the last node that still has unused edges. The answer comes out in reverse.

An everyday example

A mail carrier who must walk every street once

A mail carrier must walk every street exactly once. They set off and keep walking, crossing each street off as they go, until they reach a corner with no unwalked streets. They mark that corner as the end of their route and step back to the previous corner. If that corner still has unwalked streets, they take a loop from there that eventually returns. In the end, reading the marked corners backwards gives one walk that covers every street once.

How the example maps to the code
In the exampleIn the code
Streets not walked yetEntries left in graph[node]
Walking down a street and crossing it offstack.push(graph[node].pop())
A corner with nothing left to walkgraph[node].length === 0
Marking the corner as the end of the route so farpath.push(stack.pop())
Reading the marks backwardspath.reverse()

From the slow way to eulerian path (hierholzer's algorithm)

  1. Start with the obvious way: backtracking. From the start, try each unused edge, keep walking, and when you get stuck with edges left over, undo the last step and try another edge. It's correct, but a wrong turn may only show up much later, so the number of tries can grow exponentially.
  2. Counting tells us a lot. Each time a route passes through a node, it uses one edge in and one edge out. So in a directed graph every node needs as many edges in as out, except the start, with one extra out, and the end, with one extra in. It also tells us where a walk can get stuck: at any other node, you've used one more edge in than out, so an unused edge out must still be there. A walk from the start can only get stuck at the end.
  3. So getting stuck early isn't a dead end. If edges are left over when you reach the end, they form loops, and each loop touches a node you already passed. Instead of undoing anything, go back to the last node that still has unused edges, walk a loop from there (it must come back to that node), and insert the loop into the route.
  4. Splicing lists by hand is messy, but a stack does it for free. Push each node as you walk. When the top node has no unused edges left, pop it and write it to path: it's the end of whatever route remains. The path comes out backwards, so reverse it at the end. That loop is Hierholzer's algorithm.

How it works

  1. Build graph and a balance for each node: out-edges minus in-edges.
  2. Every node must have a balance of -1, 0, or 1, and at most one node can have 1. Otherwise return [].
  3. Start at the node with balance 1 if there is one; otherwise at the start of any edge.
  4. Keep a stack. Look at the node on top: if it still has an unused edge, remove that edge and push its other end.
  5. If it has no unused edges, pop it and add it to path.
  6. When the stack is empty, path holds the route backwards. If it used every edge (edges.length + 1 nodes), reverse and return it; otherwise the edges weren't all connected, so return [].

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function eulerianPath(n, edges) {
  2. const graph = Array.from({ length: n }, () => []);
  3. const balance = new Array(n).fill(0);
  4. for (const [from, to] of edges) {
  5. graph[from].push(to);
  6. balance[from]++;
  7. balance[to]--;
  8. }
  9. let start = edges.length > 0 ? edges[0][0] : 0;
  10. let starts = 0;
  11. for (let node = 0; node < n; node++) {
  12. if (balance[node] === 1) {
  13. start = node;
  14. starts++;
  15. } else if (balance[node] !== 0 && balance[node] !== -1) {
  16. return [];
  17. }
  18. }
  19. if (starts > 1) return [];
  20. const stack = [start];
  21. const path = [];
  22. while (stack.length > 0) {
  23. const node = stack[stack.length - 1];
  24. if (graph[node].length > 0) {
  25. stack.push(graph[node].pop());
  26. } else {
  27. path.push(stack.pop());
  28. }
  29. }
  30. return path.length === edges.length + 1 ? path.reverse() : [];
  31. }

How fast it is

TimeO(n + e)
Extra memoryO(n + e)

Every edge is removed from the graph once and every node visit is pushed and popped once. The graph, stack, and path each hold up to e + 1 entries.

  • Best caseO(n + e)

    A node with a bad balance, like 2 extra edges out, returns [] right after the balance loop, but reading the edges already took O(n + e).

  • Average caseO(n + e)

    Every valid input: each edge is pushed and popped once, and each node is checked once.

  • Worst caseO(n + e)

    Every valid input, including ones with many detours: splicing costs nothing extra because the stack does it.

Common mistakes

  • Writing each node to the answer the moment you arrive instead of when you get stuck. A wrong early turn then leaves edges unused.
  • Forgetting to reverse path at the end.
  • Skipping the connectivity check. Balanced degrees are not enough if the edges form two separate loops.
  • Using the directed degree rule on an undirected graph. For undirected graphs, count nodes with an odd number of edges.

When to use it

Look for these clues in a problem:

  • The question asks to use every edge, ticket, or connection exactly once.
  • It asks whether a figure can be drawn in one stroke.
  • Edges are items to chain end to end, such as tickets or dominoes.
  • Nodes may be visited many times, but edges only once.

Check yourself

Answer each one in your head first, then open it.

Why is a node written to path only when it has no unused edges?

Only then is it sure that nothing comes after it. Writing it on arrival would freeze a wrong turn into the route.

Why does path come out backwards?

The first node written is the end of the route, and each later node comes before the ones already written.

In the trace, why was getting stuck at node 1 with edges left not a failure?

Node 1 is the end node, so it belongs last anyway. The unused edges formed a loop through node 2, which the stack later spliced in before it.

How many nodes are in the route for 12 edges?

13, because each edge adds one node after the start. That's why the code compares path.length with edges.length + 1.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 2 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The stack is always a walk from the start: each push follows an unused edge out of the top node and removes that edge, so every edge is used at most once. A node is written to path only when it has no unused edges left, which means nothing more can follow it, and everything written before it belongs later in the final route.

Consecutive nodes in the reversed path are joined by real edges. When a node x is written, the node just below it on the stack, z, reached x by an edge. If z still has unused edges, the walk takes a detour from z. Once the walk has reached the end node, every node has as many unused edges in as out, so the detour can only get stuck back at z. Either way, the next node written is z, so in the reversed path z comes right before x.

Each step either removes an edge or pops a node, so the loop runs at most 2e + 1 times. If every edge is connected to the start, all of them get used and path has edges.length + 1 nodes. If some edges sit in a separate piece, the walk never reaches them, path comes out shorter, and the code returns [].

Going deeper

3 more ideas

Why getting stuck is the right time to write a node

With the degree rule satisfied, the only node where a walk can get stuck while unused edges remain elsewhere is the end of the route. Writing a node only when it has no unused edges means it is written after everything that must come after it. Any detour found later from an earlier node gets written before that node, which splices the loop into the route at the right place.

Getting one specific answer

A graph often has several Eulerian paths. To get the one that comes first in alphabetical (or number) order, sort each node's list in reverse, so pop() takes the smallest neighbor first. Each step then tries the smallest next node, and the splicing still keeps the path valid.

Cost

Each edge is pushed and popped once, so the walk is O(n + e). Sorting the neighbor lists for the smallest-first rule adds O(e log e).

Work it by hand

Every step in a table, with why

Seven one-way edges with one start and one end. The walk takes a wrong turn and gets stuck at the end early, and the stack splices in the missed loop.

n = 5, edges = [[2,4], [3,2], [4,3], [2,0], [0,1], [1,2], [2,1]]

StepnodeActionstackpathWhy
1-balance = [0, -1, 1, 0, 0][2][]Node 2 has one extra edge out, so it's the start; node 1 has one extra edge in, so it's the end. graph[2] is [4, 0, 1].
22take 2→1[2, 1][]pop() takes the last edge in graph[2], which leads to node 1.
31take 1→2[2, 1, 2][]Node 1's only edge goes back to 2.
42take 2→0[2, 1, 2, 0][]Node 2 still has edges to 4 and 0. It takes the one to 0.
50take 0→1[2, 1, 2, 0, 1][]The walk reaches the end node, 1, but the loop 2 → 4 → 3 → 2 is still unused.
61stuck: write 1[2, 1, 2, 0][1]Node 1 has no unused edges, so it's the last node of the route.
70stuck: write 0[2, 1, 2][1, 0]Node 0 has nothing left either, so it comes just before 1.
82take 2→4[2, 1, 2, 4][1, 0]Node 2 still has its edge to 4. This starts the detour, instead of undoing anything.
94take 4→3[2, 1, 2, 4, 3][1, 0]The detour continues.
103take 3→2[2, 1, 2, 4, 3, 2][1, 0]The detour comes back to node 2, as a loop must.
112stuck: write 2[2, 1, 2, 4, 3][1, 0, 2]Node 2 has no unused edges now, so this copy of 2 is written.
123stuck: write 3[2, 1, 2, 4][1, 0, 2, 3]From here on, every node is stuck, so the stack unwinds into path.
134stuck: write 4[2, 1, 2][1, 0, 2, 3, 4]Node 4 is written.
142stuck: write 2[2, 1][1, 0, 2, 3, 4, 2]The copy of 2 where the detour began is written.
151stuck: write 1[2][1, 0, 2, 3, 4, 2, 1]Node 1 is written.
162stuck: write 2[][1, 0, 2, 3, 4, 2, 1, 2]The start is written last, and the stack is empty.

path has 8 nodes, which is edges.length + 1, so every edge was used. Reversed, the route is [2, 1, 2, 4, 3, 2, 0, 1]: the loop through 4 and 3 was spliced in before the step to 0.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Eulerian path (Hierholzer's algorithm)O(n + e)O(n + e)You need any route, or the smallest one in order, that uses every edge exactly once.
Backtracking over edgesO(e!)O(e)Extra rules beyond the degrees, like forbidden turns, make Hierholzer's splicing invalid, and the graph is tiny.
Fleury's algorithmO(e^2)O(n + e)Rarely. It avoids crossing a bridge unless forced, which needs a bridge check at every step.

Extra memory: O(n + e): graph holds every edge, balance holds n numbers, and stack and path hold up to e + 1 nodes each.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Eulerian path (Hierholzer's algorithm) and the other approaches, on a scale where each line up is 10 times more steps.
  • Eulerian path (Hierholzer's algorithm) O(n + e)
  • Backtracking over edges O(e!)
  • Fleury's algorithm O(e^2)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Eulerian path (Hierholzer's algorithm)202,0002 million
Backtracking over edges4 millionmore than a quadrillionmore than a quadrillion
Fleury's algorithm1001 million1 trillion

Inputs that need care

6 tricky inputs
No edges: n = 3, edges = []
start is 0, the stack pops it right away, and path is [0], which equals edges.length + 1. It returns [0].
Two separate loops: [[0,1], [1,0], [2,3], [3,2]]
Every balance is 0, but the walk from 0 never reaches nodes 2 and 3. path has 3 nodes instead of 5, so it returns [].
Two possible starts: [[0,1], [2,3]]
Nodes 0 and 2 both have balance 1, so starts is 2 and it returns [].
A self-loop: [[0,1], [1,1], [1,2]]
It doesn't change any balance. The walk takes 1 → 1 like any other edge and returns [0, 1, 1, 2].
All balances 0: [[1,2], [2,0], [0,1]]
It's a circuit. start is the first edge's start, 1, and it returns [1, 2, 0, 1], ending where it began.
Nodes with no edges at all
They don't need to be visited, so they're ignored. Only edges must be used.

Variations and follow-ups

Twists interviewers add

Undirected graphs

A path exists when zero or two nodes have an odd number of edges, and the start is one of the odd ones. Each edge sits in two lists, so give each edge an id and mark it used, skipping used ids when you pop from a list.

Chaining named tickets

When nodes are names, like airport codes, map each name to an index first. To get the route that comes first in alphabetical order, sort each list from largest to smallest, so pop() always takes the smallest next name.

De Bruijn sequences

Make a node for every string of length k - 1 and an edge for every string of length k, from its first k - 1 characters to its last k - 1. A circuit through all edges spells the shortest string containing every code of length k once: for 3-digit binary codes, 0011101000, 10 characters holding all 8 codes.

When no path exists

If a delivery route must cover every street but the degrees don't allow it, repeat some streets. Pairing up the odd nodes as cheaply as possible and doubling the streets between them makes a circuit possible; this is the route inspection problem.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "use every ticket", "every edge exactly once", "draw without lifting the pen", or "chain the pieces end to end". Nodes may repeat; edges may not.
  • Start by checking existence out loud with the degree rule before any code: every node balanced, except at most one start with one extra out and one end with one extra in.
  • Test by hand a graph where the first greedy walk reaches the end too early, like the trace, and two separate loops with perfect balances, which must fail.
  • Expect "why not just do a DFS and record nodes as you visit?". Answer: a node visited early may belong late in the route. Writing nodes when they get stuck, then reversing, places every detour correctly.

Where frontend code uses it

The same idea in real UI code
  • Puzzle games in the browser that ask the player to draw a shape in one stroke check the degree rule to know whether a level is solvable.
  • Plotter and laser-cutter tools, including web-based ones, order line segments to reduce lifting the pen, which is an Eulerian path problem on the drawing's edges.
  • Travel or logistics apps that chain tickets or legs end to end into one itinerary that uses each ticket once.

Related algorithms