MST & Euler Paths

At a glance

The instinct

These two ideas share a section because both are about edges rather than nodes, and both have a short greedy algorithm that is easy to forget under pressure.

• Minimum spanning tree (MST): you must link all n nodes into one connected network and pay for each edge you keep. The cheapest network is always a tree with exactly n - 1 edges. Kruskal sorts edges and greedily keeps any edge that joins two different components; Prim grows one tree outward, always adding the cheapest edge that leaves it.
• Euler path: you must traverse every edge exactly once (every ticket, every transition). Hierholzer does a DFS that consumes edges, and appends a node to the answer only when it has no unused edges left; the reversed list is the path.

Recognise it

Not this pattern if...

• You need the cheapest route between two nodes: that is shortest path (Dijkstra), and an MST does not give it.
• Every node (not edge) must be visited once: that is a Hamiltonian path, which is exponential - think bitmask DP or backtracking.
• You only need to know whether things are connected: union-find or BFS alone is enough.

Memory hack

Analogy for Euler paths: you are a mail carrier who must walk every street exactly once. You set off and keep walking until you hit a corner with no unwalked streets - that corner must be the end of your route, so you write it at the bottom of your log. Backing up, any corner that still has unwalked streets launches a side loop that gets spliced in automatically.

Say it out loud in the interview:

1. "Am I connecting everything (MST) or traversing every edge (Euler)?"
2. MST: "Sort edges, union-find to skip cycles, stop at n - 1 edges." For a complete graph of points, "Prim with an array, O(n²), no heap needed."
3. Euler: "Check the degree condition, pick the right start node, post-order DFS consuming edges, reverse."

How it works

Why greedy is safe for MST (the cut property): split the nodes into any two groups; the cheapest edge crossing between them belongs to some MST. Kruskal's "cheapest edge that joins two components" is always such a crossing edge, so it never makes a mistake.

When does an Euler path exist?

In both cases all edges must lie in one connected component.

flowchart TD
    A[Problem about edges] --> B{Connect all nodes at minimum total cost?}
    B -- yes --> C{Dense / complete graph?}
    C -- yes --> D[Prim with arrays O of n squared]
    C -- no --> E[Kruskal: sort edges + union-find]
    B -- no --> F{Use every edge exactly once?}
    F -- yes --> G[Check degrees, pick start]
    G --> H[Hierholzer: DFS, append on backtrack, reverse]
    F -- no --> I[Probably shortest path or plain BFS/DFS]

Java template

import java.util.*;

class MinimumSpanningTree {
    static int[] parent;

    static int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }

    // Kruskal. edges[i] = {u, v, w}. Returns total weight, or -1 if graph is disconnected.
    static long kruskal(int n, int[][] edges) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));
        long total = 0;
        int used = 0;
        for (int[] e : edges) {
            int ru = find(e[0]), rv = find(e[1]);
            if (ru == rv) continue;                   // would close a cycle
            parent[ru] = rv;
            total += e[2];
            if (++used == n - 1) break;
        }
        return used == n - 1 ? total : -1;
    }

    // Prim on a dense/complete graph. cost(i, j) is computed on the fly.
    static long primDense(int n, int[][] pts) {
        long[] best = new long[n];
        boolean[] inTree = new boolean[n];
        Arrays.fill(best, Long.MAX_VALUE);
        best[0] = 0;
        long total = 0;
        for (int step = 0; step < n; step++) {
            int u = -1;
            for (int i = 0; i < n; i++)
                if (!inTree[i] && (u == -1 || best[i] < best[u])) u = i;
            inTree[u] = true;
            total += best[u];
            for (int v = 0; v < n; v++) {
                if (inTree[v]) continue;
                long w = Math.abs(pts[u][0] - pts[v][0]) + Math.abs(pts[u][1] - pts[v][1]); // edge cost
                if (w < best[v]) best[v] = w;
            }
        }
        return total;
    }
}

import java.util.*;

class EulerPath {
    // Hierholzer on a directed multigraph; smallest lexical order via min-heaps.
    static List<String> eulerPath(List<List<String>> edges, String start) {
        Map<String, PriorityQueue<String>> adj = new HashMap<>();
        for (List<String> e : edges)
            adj.computeIfAbsent(e.get(0), k -> new PriorityQueue<>()).offer(e.get(1));

        LinkedList<String> path = new LinkedList<>();
        Deque<String> stack = new ArrayDeque<>();
        stack.push(start);                            // start = node with out - in = 1, else any node with edges
        while (!stack.isEmpty()) {
            PriorityQueue<String> out = adj.get(stack.peek());
            if (out != null && !out.isEmpty()) {
                stack.push(out.poll());               // consume one edge
            } else {
                path.addFirst(stack.pop());           // stuck: record on the way back
            }
        }
        return path;                                  // size == edges + 1 if a full Euler path exists
    }
}

Complexity

For Min Cost to Connect All Points, E = n²/2, so array-based Prim at O(n²) beats Kruskal at O(n² log n).

Variations

• MST on implicit complete graph: Min Cost to Connect All Points - edge weight is Manhattan distance; Prim with arrays avoids building n² edges.
• MST with a virtual node: Optimize Water Distribution in a Village - "build a well" becomes an edge to an extra node 0, then run Kruskal.
• Edge classification: Find Critical and Pseudo-Critical Edges in MST - rerun Kruskal excluding or forcing each edge.
• Lexical Euler path: Reconstruct Itinerary - min-heap adjacency, start from "JFK", append on backtrack.
• De Bruijn / Euler circuit: Cracking the Safe - nodes are (n-1)-digit strings, each of the k digits is an outgoing edge; walking every edge once yields the shortest string containing all codes.
• Euler path with start detection: Valid Arrangement of Pairs - start at the node whose out-degree exceeds in-degree by one.

Common mistakes

• Greedy lexical DFS without backtracking. Always taking the smallest neighbour can strand you before all tickets are used; Hierholzer's post-order splicing is what fixes it.
• Not checking for disconnection in Kruskal. If fewer than n - 1 edges were added, no spanning tree exists.
• Skipping path compression / union by rank. Union-find degenerates to O(n) per call on long chains.
• Materialising all n² edges for a point set and running out of memory or time; use dense Prim.
• Wrong start node for an Euler path. In a directed graph start at the out - in = 1 node; in an undirected graph start at an odd-degree vertex.

All practice problems

3 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.