Minimum Spanning Tree Problems
3 Minimum Spanning Tree LeetCode problems · Browse tasks by difficulty and choose your next practice problem.
Learn the coding interview patterns behind these problems, including Minimum Spanning Tree interview patterns.
Connect every vertex with minimum total edge weight
A minimum spanning tree connects a weighted undirected graph using V - 1 edges with minimum total weight. Kruskal's algorithm sorts edges and accepts an edge only when it joins two different components. A disjoint-set union structure makes that cycle check efficient.
When to use it
Use an MST when all vertices must be connected and the objective is the sum of selected edge costs. It is not a shortest-path tree: minimizing the total network cost does not minimize the route from one chosen source to every vertex.
Worked example
Edges: A–B:1, B–C:2, C–D:3, A–C:4, B–D:5.
- Sort the edges by weight. Initially A, B, C, and D are separate components.
- Accept A–B and B–C, merging three vertices. Accept C–D to connect the fourth vertex.
- Stop after three accepted edges. A–C and B–D would now create cycles.
The tree has total weight 1 + 2 + 3 = 6 and connects all four vertices.
Time and space
Kruskal takes O(E log E) time for sorting, plus near-linear disjoint-set operations with path compression and union by rank or size. The disjoint-set state uses O(V) space in addition to the edges. Materializing all pairwise edges for n points already costs O(n²) space.
Mistakes to check
- A disconnected input produces a minimum spanning forest. Check the accepted-edge count before claiming a spanning tree exists.
- Equal edge weights can yield multiple valid MSTs. Critical and pseudo-critical edge questions need reasoning about alternatives, not just one arbitrary run.
- Negative weights are allowed. What matters is undirected connectivity and the objective, not an assumption that every cost is positive.
Further reading: Princeton Algorithms: minimum spanning trees
Guide reviewed .