Eulerian path (Hierholzer's algorithm)

How does Eulerian path (Hierholzer's algorithm) work?

Check the degrees before anything else. An undirected path allows at most two nodes with an odd degree.

In a directed graph, at most one node may have an extra outgoing edge. That node has to be the start.

Walk forward greedily and delete each edge as you use it. A used edge is never walked again.

When a node has no edges left, push it onto an output stack. It is stuck, so it belongs near the end.

Step back to the previous node and carry on. Any unused edges there are still reachable.

Reverse the output stack at the very end. That puts the path in the right order.

1. at JFK, edges to A and BTake A first when the smallest route is wanted.
2. at A, then back to JFKThe only edge out of A returns to JFK.
3. at B: no edges leftB is stuck, so it is pushed first.
4. push JFK, A, JFKEach node is pushed once it runs dry.
5. reversed: JFK, A, JFK, BReading the stack backwards gives the route.

function eulerianPath(tickets, start) {
    const adj = {};
    for (const [from, to] of tickets) {
        (adj[from] ||= []).push(to);
    }
    for (const from in adj) adj[from].sort().reverse(); // pop smallest first
    const route = [];
    const stack = [start];
    while (stack.length) {
        const node = stack[stack.length - 1];
        if (adj[node] && adj[node].length) {
            stack.push(adj[node].pop());
        } else {
            route.push(stack.pop()); // dead end: record and back up
        }
    }
    return route.reverse();
}

A worked example of Eulerian path (Hierholzer's algorithm)

Rebuild a travel itinerary

You get a list of flight tickets. Every ticket must be used exactly once, starting at JFK.

When several routes exist, return the smallest in alphabetical order.

Sort each airport's destinations so the smallest is taken first.

Walk greedily and push an airport once it has no tickets left. Reverse the stack at the end.

function findItinerary(tickets) {
    const graph = new Map();
    for (const [from, to] of tickets) {
        if (!graph.has(from)) graph.set(from, []);
        graph.get(from).push(to);
    }
    // reversed, so pop() hands back the smallest destination
    for (const list of graph.values()) list.sort().reverse();

    const route = [];
    const stack = ["JFK"];

    while (stack.length) {
        const airport = stack[stack.length - 1];
        const next = graph.get(airport);

        if (next && next.length) {
            stack.push(next.pop()); // the ticket is used up
        } else {
            route.push(stack.pop()); // stuck, so this airport ends the route
        }
    }

    return route.reverse();
}

When should you use Eulerian path (Hierholzer's algorithm)?

These phrases in a problem statement point here:

• •use every edge exactly once
• •reconstruct an itinerary from tickets
• •one-stroke drawing / draw without lifting the pen
• •walk every road/domino exactly once
• •flights or dominoes must chain into one trip

What is Eulerian path (Hierholzer's algorithm) confused with?

• Graph BFS / DFS: A traversal has to reach every node. This one has to use every edge.
• Backtracking: Trying routes and undoing them is exponential. This walk never has to take a step back.
• Connected components: Every edge must sit in one component, which is one of the conditions here. Counting groups is not the goal.
• Stack (LIFO): The stack is what makes the walk work. This page is about when to push onto it.

Common mistakes with Eulerian path (Hierholzer's algorithm)

• Returning the path in walk order

  The output stack has to be reversed. Walk order puts the dead ends in the wrong place.

• Not deleting the edge you used

  The same edge is then walked forever. Remove it at the moment you take it.

• Skipping the degree check

  Plenty of graphs have no such walk at all. Test the degrees before starting.

• Reaching for backtracking

  Trying and undoing routes explodes on a large graph. The stack rule never needs a retry.

Which interview problems use Eulerian path (Hierholzer's algorithm)?

• Reconstruct itinerary: Directed edges, with alphabetical order as the tie-break.
• Valid arrangement of pairs: The start is decided by the degrees.
• Cracking the safe: A de Bruijn sequence is an Eulerian circuit.
• Eulerian circuit check: Every degree even, and all edges in one component.
• Domino chain: Each domino is an edge between two numbers.
• Rebuild a genome from fragments: The overlap graph carries an Eulerian path.
• The bridges of Konigsberg: The original proof that no such walk exists.

What is the time and space complexity of Eulerian path (Hierholzer's algorithm)?

O(E)

V nodes and E edges give O(E log E) once the edges are sorted. Without sorting it is O(E).