Minimum Spanning Tree Interview Questions
Last updated 2026-11-19
A minimum spanning tree connects every vertex of a weighted undirected graph using the cheapest set of edges, with no cycles. Kruskal and Prim are the two standard algorithms, and interviewers like the topic because it combines sorting, heaps and union-find in one problem.
This page covers both algorithms and the common disguises: connecting cities, linking points on a plane, water distribution and edge classification. Each problem has Python and Java code, complexity and edge cases. The union-find structure used throughout is explained on union-find interview questions, and shortest paths on Dijkstra interview questions.
| Kruskal | Sort edges, union-find, O(E log E) |
|---|---|
| Prim | Grow a tree with a heap, O(E log V) |
| Edges in tree | Exactly V - 1 |
| Important contrast | MST does not give shortest paths |
The pattern and when to spot it
Spot an MST when the task is to connect everything as cheaply as possible and the cost is a sum over edges, such as laying cable, building roads or linking points. If the graph is dense or implicit, such as points on a plane with a distance formula, array-based Prim at O(n^2) avoids building all edges. For sparse edge lists, sorting plus union-find, Kruskal, is shorter to write.
Two correctness ideas are worth stating aloud. The cut property says the cheapest edge crossing any split of the vertices belongs to some MST. The cycle property says the heaviest edge on any cycle is never needed. Extensions follow naturally: a virtual node models optional wells in the water distribution problem, and the bottleneck path between two vertices lies on the MST.
Mistakes to avoid
- Confusing an MST with a shortest path tree. The cheapest tree overall does not give cheapest routes from one source.
- Forgetting to check connectivity: a result with fewer than V-1 edges means no spanning tree exists.
- Using Prim with a heap but not skipping vertices already in the tree.
- Assuming the MST is unique. Equal weights allow several trees with the same total.
- Overflowing int when summing large weights.
Minimum Spanning Tree Interview Questions: questions with worked answers
1 Kruskal algorithm: weight of the minimum spanning tree
easySort all edges by weight, then add each edge if it joins two different components, using union-find to test that. Stop after n-1 edges. If fewer than n-1 edges were added, the graph is disconnected and has no spanning tree. Time O(E log E), space O(V). Edge cases: disconnected graph (no tree exists), equal weights (several valid trees but the same total), single vertex (weight 0), parallel edges.
pythonclass DSU: def __init__(self, n): self.p = list(range(n)) self.sz = [1] * n def find(self, x): while self.p[x] != x: self.p[x] = self.p[self.p[x]] x = self.p[x] return x def union(self, a, b): a, b = self.find(a), self.find(b) if a == b: return False if self.sz[a] < self.sz[b]: a, b = b, a self.p[b] = a self.sz[a] += self.sz[b] return True def kruskal(n, edges): d = DSU(n) total = used = 0 for u, v, w in sorted(edges, key=lambda e: e[2]): if d.union(u, v): total += w used += 1 return total if used == n - 1 else -1javaclass DSU { int[] p, sz; DSU(int n) { p = new int[n]; sz = new int[n]; for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1; } } int find(int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; } boolean union(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (sz[a] < sz[b]) { int t = a; a = b; b = t; } p[b] = a; sz[a] += sz[b]; return true; } } long kruskal(int n, int[][] edges) { Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2])); DSU d = new DSU(n); long total = 0; int used = 0; for (int[] e : edges) if (d.union(e[0], e[1])) { total += e[2]; used++; } return used == n - 1 ? total : -1; }2 Prim algorithm with a heap
mediumGrow the tree from vertex 0. Keep a min-heap of edges leaving the tree as (weight, vertex). Pop the cheapest; if the vertex is already in the tree skip it, otherwise add it and push its edges to vertices outside. Prim suits dense graphs, Kruskal sparse ones. Time O(E log V), space O(V + E). Edge cases: disconnected graph (tree has fewer than n vertices), skipping already visited vertices, single vertex.
pythonimport heapq def prim(n, edges): g = [[] for _ in range(n)] for u, v, w in edges: g[u].append((w, v)); g[v].append((w, u)) seen, total = [False] * n, 0 h, count = [(0, 0)], 0 while h and count < n: w, u = heapq.heappop(h) if seen[u]: continue seen[u] = True total += w count += 1 for w2, v in g[u]: if not seen[v]: heapq.heappush(h, (w2, v)) return total if count == n else -1javalong prim(int n, int[][] edges) { List<List<int[]>> g = new ArrayList<>(); for (int i = 0; i < n; i++) g.add(new ArrayList<>()); for (int[] e : edges) { g.get(e[0]).add(new int[]{e[1], e[2]}); g.get(e[1]).add(new int[]{e[0], e[2]}); } boolean[] seen = new boolean[n]; PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]); pq.add(new int[]{0, 0}); long total = 0; int count = 0; while (!pq.isEmpty() && count < n) { int[] t = pq.poll(); if (seen[t[0]]) continue; seen[t[0]] = true; total += t[1]; count++; for (int[] e : g.get(t[0])) if (!seen[e[0]]) pq.add(new int[]{e[0], e[1]}); } return count == n ? total : -1; }3 Connecting cities with minimum cost
mediumBuild a spanning tree over cities 1 to n from the list of possible connections. This is Kruskal. If fewer than n-1 connections were used the cities cannot all be connected, so return -1. Time O(E log E), space O(n). Edge cases: one-based labels, n equal to 1 (cost 0), unreachable city, duplicate connections with different costs.
pythonclass DSU: def __init__(self, n): self.p = list(range(n)) self.sz = [1] * n def find(self, x): while self.p[x] != x: self.p[x] = self.p[self.p[x]] x = self.p[x] return x def union(self, a, b): a, b = self.find(a), self.find(b) if a == b: return False if self.sz[a] < self.sz[b]: a, b = b, a self.p[b] = a self.sz[a] += self.sz[b] return True def minimum_cost(n, connections): d = DSU(n + 1) total = used = 0 for a, b, c in sorted(connections, key=lambda x: x[2]): if d.union(a, b): total += c used += 1 return total if used == n - 1 else -1javaclass DSU { int[] p, sz; DSU(int n) { p = new int[n]; sz = new int[n]; for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1; } } int find(int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; } boolean union(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (sz[a] < sz[b]) { int t = a; a = b; b = t; } p[b] = a; sz[a] += sz[b]; return true; } } int minimumCost(int n, int[][] c) { Arrays.sort(c, (a, b) -> a[2] - b[2]); DSU d = new DSU(n + 1); int total = 0, used = 0; for (int[] e : c) if (d.union(e[0], e[1])) { total += e[2]; used++; } return used == n - 1 ? total : -1; }4 Minimum cost to connect all points on a plane
mediumEvery pair of points is an edge weighted by Manhattan distance, so the graph is complete. Edge-list Kruskal costs O(n^2 log n). Prim in its array form is O(n^2): keep the best known distance from the tree to each outside point, repeatedly pick the nearest, and update the rest. Time O(n^2), space O(n). Edge cases: one point (0), duplicate points (distance 0), large coordinates needing long arithmetic if sums grow.
pythondef min_cost_connect(points): n = len(points) dist = [float('inf')] * n used = [False] * n dist[0] = 0 total = 0 for _ in range(n): u = min((i for i in range(n) if not used[i]), key=lambda i: dist[i]) used[u] = True total += dist[u] for v in range(n): if not used[v]: w = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1]) if w < dist[v]: dist[v] = w return totaljavaint minCostConnect(int[][] p) { int n = p.length; int[] dist = new int[n]; boolean[] used = new boolean[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[0] = 0; int total = 0; for (int it = 0; it < n; it++) { int u = -1; for (int i = 0; i < n; i++) if (!used[i] && (u == -1 || dist[i] < dist[u])) u = i; used[u] = true; total += dist[u]; for (int v = 0; v < n; v++) if (!used[v]) { int w = Math.abs(p[u][0] - p[v][0]) + Math.abs(p[u][1] - p[v][1]); if (w < dist[v]) dist[v] = w; } } return total; }5 Number of operations to make a network connected
mediumMoving a cable is allowed if the cable is redundant. With n computers you need at least n-1 cables, otherwise return -1. Count the connected components with union-find; connecting c components needs exactly c-1 moves, and enough redundant cables exist when the edge count is at least n-1. Time O(E * alpha(n)), space O(n). Edge cases: fewer than n-1 cables (-1), already connected (0), isolated computers each count as a component.
pythonclass DSU: def __init__(self, n): self.p = list(range(n)) self.sz = [1] * n def find(self, x): while self.p[x] != x: self.p[x] = self.p[self.p[x]] x = self.p[x] return x def union(self, a, b): a, b = self.find(a), self.find(b) if a == b: return False if self.sz[a] < self.sz[b]: a, b = b, a self.p[b] = a self.sz[a] += self.sz[b] return True def make_connected(n, connections): if len(connections) < n - 1: return -1 d = DSU(n) comps = n for a, b in connections: if d.union(a, b): comps -= 1 return comps - 1javaclass DSU { int[] p, sz; DSU(int n) { p = new int[n]; sz = new int[n]; for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1; } } int find(int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; } boolean union(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (sz[a] < sz[b]) { int t = a; a = b; b = t; } p[b] = a; sz[a] += sz[b]; return true; } } int makeConnected(int n, int[][] connections) { if (connections.length < n - 1) return -1; DSU d = new DSU(n); int comps = n; for (int[] c : connections) if (d.union(c[0], c[1])) comps--; return comps - 1; }6 Minimise the maximum edge between a source and a target
mediumThe best path minimises its largest edge, a bottleneck path, and it always lies on a minimum spanning tree. Add edges in increasing order of weight with union-find and return the weight of the edge that first puts source and target in the same set. Time O(E log E), space O(V). Edge cases: source equals target (0), no connection (-1), several edges with the same weight.
pythonclass DSU: def __init__(self, n): self.p = list(range(n)) self.sz = [1] * n def find(self, x): while self.p[x] != x: self.p[x] = self.p[self.p[x]] x = self.p[x] return x def union(self, a, b): a, b = self.find(a), self.find(b) if a == b: return False if self.sz[a] < self.sz[b]: a, b = b, a self.p[b] = a self.sz[a] += self.sz[b] return True def min_bottleneck(n, edges, s, t): d = DSU(n) if s == t: return 0 for u, v, w in sorted(edges, key=lambda e: e[2]): d.union(u, v) if d.find(s) == d.find(t): return w return -1javaclass DSU { int[] p, sz; DSU(int n) { p = new int[n]; sz = new int[n]; for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1; } } int find(int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; } boolean union(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (sz[a] < sz[b]) { int t = a; a = b; b = t; } p[b] = a; sz[a] += sz[b]; return true; } } int minBottleneck(int n, int[][] edges, int s, int t) { if (s == t) return 0; Arrays.sort(edges, (a, b) -> a[2] - b[2]); DSU d = new DSU(n); for (int[] e : edges) { d.union(e[0], e[1]); if (d.find(s) == d.find(t)) return e[2]; } return -1; }7 Optimise water distribution in villages
hardEach village can dig its own well at a cost or be connected by a pipe. Add a virtual node 0 connected to every village i with weight equal to the well cost. The minimum spanning tree of this augmented graph is the cheapest plan, since a village joined to node 0 has its own well. Time O(E log E) with E = pipes + n, space O(n). Edge cases: a village choosing a well versus a pipe (both captured by weights), zero-cost wells, pipes costing more than a well.
pythonclass DSU: def __init__(self, n): self.p = list(range(n)) self.sz = [1] * n def find(self, x): while self.p[x] != x: self.p[x] = self.p[self.p[x]] x = self.p[x] return x def union(self, a, b): a, b = self.find(a), self.find(b) if a == b: return False if self.sz[a] < self.sz[b]: a, b = b, a self.p[b] = a self.sz[a] += self.sz[b] return True def min_cost_to_supply(n, wells, pipes): edges = [(0, i + 1, w) for i, w in enumerate(wells)] + [tuple(p) for p in pipes] d = DSU(n + 1) total = 0 for u, v, w in sorted(edges, key=lambda e: e[2]): if d.union(u, v): total += w return totaljavaclass DSU { int[] p, sz; DSU(int n) { p = new int[n]; sz = new int[n]; for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1; } } int find(int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; } boolean union(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (sz[a] < sz[b]) { int t = a; a = b; b = t; } p[b] = a; sz[a] += sz[b]; return true; } } int minCostToSupply(int n, int[] wells, int[][] pipes) { List<int[]> edges = new ArrayList<>(); for (int i = 0; i < n; i++) edges.add(new int[]{0, i + 1, wells[i]}); for (int[] p : pipes) edges.add(p); edges.sort((a, b) -> a[2] - b[2]); DSU d = new DSU(n + 1); int total = 0; for (int[] e : edges) if (d.union(e[0], e[1])) total += e[2]; return total; }8 Remove the maximum number of edges while keeping the graph traversable by two people
hardEdges have types: 1 for Alice only, 2 for Bob only, 3 for both. Keep type-3 edges first, because one edge helps two people. Use two union-finds. Add each useful type-3 edge to both, then type-1 edges to Alice and type-2 to Bob. Both graphs must end connected; an edge is removable if it did not merge anything in any set. Time O(E * alpha(n)), space O(n). Edge cases: either person unable to reach every node (return -1), type-3 edges that are redundant for both, edges that are useful for one but not the other.
pythonclass DSU: def __init__(self, n): self.p = list(range(n)) self.sz = [1] * n def find(self, x): while self.p[x] != x: self.p[x] = self.p[self.p[x]] x = self.p[x] return x def union(self, a, b): a, b = self.find(a), self.find(b) if a == b: return False if self.sz[a] < self.sz[b]: a, b = b, a self.p[b] = a self.sz[a] += self.sz[b] return True def max_edges_to_remove(n, edges): a, b = DSU(n + 1), DSU(n + 1) used = 0 for t, u, v in edges: if t == 3: ra, rb = a.union(u, v), b.union(u, v) if ra or rb: used += 1 for t, u, v in edges: if t == 1 and a.union(u, v): used += 1 elif t == 2 and b.union(u, v): used += 1 ca = len({a.find(i) for i in range(1, n + 1)}) cb = len({b.find(i) for i in range(1, n + 1)}) return len(edges) - used if ca == 1 and cb == 1 else -1javaclass DSU { int[] p, sz; DSU(int n) { p = new int[n]; sz = new int[n]; for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1; } } int find(int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; } boolean union(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (sz[a] < sz[b]) { int t = a; a = b; b = t; } p[b] = a; sz[a] += sz[b]; return true; } } int maxEdgesToRemove(int n, int[][] edges) { DSU a = new DSU(n + 1), b = new DSU(n + 1); int used = 0; for (int[] e : edges) if (e[0] == 3) { boolean ra = a.union(e[1], e[2]), rb = b.union(e[1], e[2]); if (ra || rb) used++; } for (int[] e : edges) { if (e[0] == 1 && a.union(e[1], e[2])) used++; else if (e[0] == 2 && b.union(e[1], e[2])) used++; } Set<Integer> ca = new HashSet<>(), cb = new HashSet<>(); for (int i = 1; i <= n; i++) { ca.add(a.find(i)); cb.add(b.find(i)); } return ca.size() == 1 && cb.size() == 1 ? edges.length - used : -1; }9 Critical and pseudo-critical edges of an MST
hardAn edge is critical if removing it raises the MST weight or disconnects the graph. It is pseudo-critical if it can appear in some MST but not all, which holds when forcing it in still gives the minimum weight. For each edge, compute the MST without it (critical if worse) and with it forced first (pseudo-critical if equal to the best and not critical). Time O(E^2 * alpha(n)) after one sort, space O(n). Edge cases: disconnected graph after removing an edge counts as critical, several edges of equal weight forming a triangle (all pseudo-critical), a bridge edge.
pythonclass DSU: def __init__(self, n): self.p = list(range(n)) self.sz = [1] * n def find(self, x): while self.p[x] != x: self.p[x] = self.p[self.p[x]] x = self.p[x] return x def union(self, a, b): a, b = self.find(a), self.find(b) if a == b: return False if self.sz[a] < self.sz[b]: a, b = b, a self.p[b] = a self.sz[a] += self.sz[b] return True def critical_pseudo(n, edges): idx = sorted(range(len(edges)), key=lambda i: edges[i][2]) def mst(skip=-1, force=-1): d, total, used = DSU(n), 0, 0 if force >= 0: u, v, w = edges[force] d.union(u, v) total, used = w, 1 for i in idx: if i == skip: continue u, v, w = edges[i] if d.union(u, v): total += w used += 1 return total if used == n - 1 else float('inf') best = mst() crit, pseudo = [], [] for i in range(len(edges)): if mst(skip=i) > best: crit.append(i) elif mst(force=i) == best: pseudo.append(i) return [crit, pseudo]javaclass DSU { int[] p, sz; DSU(int n) { p = new int[n]; sz = new int[n]; for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1; } } int find(int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; } boolean union(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (sz[a] < sz[b]) { int t = a; a = b; b = t; } p[b] = a; sz[a] += sz[b]; return true; } } int n; int[][] edges; Integer[] idx; List<List<Integer>> criticalPseudo(int n, int[][] edges) { this.n = n; this.edges = edges; idx = new Integer[edges.length]; for (int i = 0; i < idx.length; i++) idx[i] = i; Arrays.sort(idx, (a, b) -> edges[a][2] - edges[b][2]); long best = mst(-1, -1); List<Integer> crit = new ArrayList<>(), pseudo = new ArrayList<>(); for (int i = 0; i < edges.length; i++) { if (mst(i, -1) > best) crit.add(i); else if (mst(-1, i) == best) pseudo.add(i); } return List.of(crit, pseudo); } private long mst(int skip, int force) { DSU d = new DSU(n); long total = 0; int used = 0; if (force >= 0) { d.union(edges[force][0], edges[force][1]); total = edges[force][2]; used = 1; } for (int i : idx) { if (i == skip) continue; if (d.union(edges[i][0], edges[i][1])) { total += edges[i][2]; used++; } } return used == n - 1 ? total : Long.MAX_VALUE; }10 Is the minimum spanning tree unique?
hardThe MST is unique if no two edges of equal weight could be swapped. Process edges in groups of equal weight. For each group, count how many edges connect different components before any union (candidates) and how many actually get united. If candidates exceed the unions made, a choice existed and the tree is not unique. Time O(E log E), space O(V). Edge cases: all weights distinct (always unique), a triangle with equal weights, edges that become redundant only because of an earlier equal-weight edge.
pythonclass DSU: def __init__(self, n): self.p = list(range(n)) self.sz = [1] * n def find(self, x): while self.p[x] != x: self.p[x] = self.p[self.p[x]] x = self.p[x] return x def union(self, a, b): a, b = self.find(a), self.find(b) if a == b: return False if self.sz[a] < self.sz[b]: a, b = b, a self.p[b] = a self.sz[a] += self.sz[b] return True def mst_unique(n, edges): d = DSU(n) edges = sorted(edges, key=lambda e: e[2]) i = 0 while i < len(edges): j = i while j < len(edges) and edges[j][2] == edges[i][2]: j += 1 group = edges[i:j] cand = sum(1 for u, v, w in group if d.find(u) != d.find(v)) made = sum(1 for u, v, w in group if d.union(u, v)) if cand != made: return False i = j return Truejavaclass DSU { int[] p, sz; DSU(int n) { p = new int[n]; sz = new int[n]; for (int i = 0; i < n; i++) { p[i] = i; sz[i] = 1; } } int find(int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; } boolean union(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (sz[a] < sz[b]) { int t = a; a = b; b = t; } p[b] = a; sz[a] += sz[b]; return true; } } boolean mstUnique(int n, int[][] edges) { Arrays.sort(edges, (a, b) -> a[2] - b[2]); DSU d = new DSU(n); int i = 0; while (i < edges.length) { int j = i; while (j < edges.length && edges[j][2] == edges[i][2]) j++; int cand = 0, made = 0; for (int k = i; k < j; k++) if (d.find(edges[k][0]) != d.find(edges[k][1])) cand++; for (int k = i; k < j; k++) if (d.union(edges[k][0], edges[k][1])) made++; if (cand != made) return false; i = j; } return true; }
Frequently asked questions
What is the difference between Kruskal and Prim?
Kruskal sorts edges and adds them if they join different components, which suits sparse graphs. Prim grows one tree outward with a heap, which suits dense graphs. Both produce a minimum total weight.
Is the minimum spanning tree unique?
Only when no two edges of equal weight could be swapped, which is guaranteed if all weights are distinct. Otherwise several trees can share the minimum weight.
Does an MST give the shortest path between two nodes?
No. It minimises total weight, not distance between a pair. Use Dijkstra or Bellman-Ford for shortest paths.
Are MST questions common in interviews?
They appear in graph-heavy rounds at product companies, usually as connecting-cities or points problems. The technical interview guide describes how these rounds go.
Related guides
More in DSA Interview Questions
- Monotonic stack interview questions with worked solutions
- Prefix sum interview questions with worked solutions
- Queue and deque interview questions with worked solutions
- Recursion interview questions with worked solutions
- Segment Tree Interview Questions
- Sliding window interview questions with worked solutions
- Sorting algorithm interview questions with worked solutions
- Stack interview questions with worked solutions
- String interview questions with worked solutions
- Top K elements interview questions with worked solutions
- Topological Sort Interview Questions
- Tree DP Interview Questions