---
title: "Eulerian path (Hierholzer's algorithm)"
url: https://algopath.pro/patterns/eulerian-path
language: en
summary: "Walk a graph using every one of its edges exactly once. Push a node the moment it gets stuck, then read the answer backwards."
updated: 2026-08-24
---

# Eulerian path (Hierholzer's algorithm)

Walk a graph using every one of its edges exactly once. Push a node the moment it gets stuck, then read the answer backwards.

## 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.

- `at JFK, edges to A and B` Take A first when the smallest route is wanted.
- `at A, then back to JFK` The only edge out of A returns to JFK.
- `at B: no edges left` B is stuck, so it is pushed first.
- `push JFK, A, JFK` Each node is pushed once it runs dry.
- `reversed: JFK, A, JFK, B` Reading the stack backwards gives the route.

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

- 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.

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

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

## 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.

```javascript
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();
}
```

## 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.

## JavaScript

```javascript
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();
}
```

## Python

```python
def eulerian_path(tickets, start):
    adj = {}
    for frm, to in tickets:
        adj.setdefault(frm, []).append(to)
    for frm in adj:
        adj[frm].sort(reverse=True)  # pop smallest first
    route = []
    stack = [start]
    while stack:
        node = stack[-1]
        if adj.get(node):
            stack.append(adj[node].pop())
        else:
            route.append(stack.pop())  # dead end: record and back up
    return route[::-1]
```

## PHP

```php
function eulerianPath(array $tickets, string $start): array {
    $adj = [];
    foreach ($tickets as [$from, $to]) {
        $adj[$from][] = $to;
    }
    foreach ($adj as $from => &$list) {
        rsort($list); // pop smallest first
    }
    unset($list);
    $route = [];
    $stack = [$start];
    while ($stack) {
        $node = end($stack);
        if (!empty($adj[$node])) {
            $stack[] = array_pop($adj[$node]);
        } else {
            $route[] = array_pop($stack); // dead end: record and back up
        }
    }
    return array_reverse($route);
}
```