Get started

Minimum Spanning Tree Coding Problems: 1 Question with Solutions

1 minimum spanning tree coding problem — 1 medium — with solutions in 13 languages. Plus a step-by-step walkthrough and a 1-day plan.

  • Problems: 1
  • By difficulty: 1 medium
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

A minimum spanning tree connects every node of a weighted, undirected graph using the cheapest possible set of edges — n − 1 of them, with no cycle. Kruskal's algorithm sorts the edges and keeps each one that joins two parts not yet connected; Prim's algorithm grows a single tree from a start node, always adding the cheapest edge that leaves it. Laying cable between sites, joining points on a plane and clustering by distance are all spanning-tree questions. The problems here practise both algorithms and the choice between them on edge lists and on dense, implicit graphs.

How minimum spanning tree works, step by step

431245768ABCDEFsorted edgesB–C 1keptB–D 2keptA–C 3keptA–B 4cycleC–D 4cycleC–E 5keptD–F 6keptD–E 7E–F 8components: {A,B,C,D,E,F}total weight = 17
Minimum spanning tree of a weighted graph, with Kruskal's algorithm. Example: edges = A–B 4, A–C 3, B–C 1, B–D 2, C–D 4, C–E 5, D–E 7, D–F 6, E–F 8
  1. Kruskal sorts the 9 edges by weight and tries them cheapest first. Every node starts as its own component; an edge is kept only if it joins two different components, because inside one it would close a cycle.
  2. B–C (1) is the cheapest edge of all, and it joins {B} and {C}, two different components, so it is kept and they merge. Total 1.
  3. B–D (2) is the cheapest edge left and joins {B, C} to {D}, so it is kept: total 3. The lightest edge between two components is always safe to take.
  4. A–C (3) links {A} to {B, C, D}, different components again, so it is kept: total 6.
  5. A–B (4) is next, but A and B are already in one component, joined by A–C–B. Adding it would close a cycle, so it is skipped.
  6. C–D (4) is next, but C and D are already in one component, joined by C–B–D. Adding it would close a cycle, so it is skipped.
  7. C–E (5) links {A, B, C, D} to {E}, different components again, so it is kept: total 11.
  8. D–F (6) joins {A, B, C, D, E} and {F} and is kept: total 17. That is 5 edges, and a spanning tree of 6 nodes needs exactly 5, so the search can stop.
  9. The tree is complete, so D–E (7) and E–F (8) are never even looked at. The minimum spanning tree weighs 17; sorting dominates the cost, O(E log E), with union-find answering each component check.

Minimum Spanning Tree study plan

The one Minimum Spanning Tree problem (1 medium) over 1 day, about 50 min in all — the pattern first, then easiest to hardest. Then move on to Biconnected Component.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve this problem.

Next topic: Biconnected Component

Minimum Spanning Tree: the essentials

When to reach for it

"Connect all the points, cities or computers at minimum total cost", any two linkable at a known price. The answer is a tree of n − 1 links. It is not a shortest-path question: it minimises total weight, not any distance between two nodes. Edges may be listed, or implicit: every pair of points, priced by distance.

The pattern

Kruskal sorts the edges by weight and keeps each one whose ends are still in different components, tracked by Union Find, until n − 1 are kept. Prim grows one tree from any node: it keeps each outside node's cheapest link into the tree, adds the cheapest such node and updates the rest. On a complete graph, Prim with a plain array never builds the edges.

def min_cost_connect(points):           # Prim on the complete graph, O(n²)
    n, total = len(points), 0
    cost = [0] + [float("inf")] * (n - 1)   # cheapest link from each node into the tree
    done = [False] * n
    for _ in range(n):
        u = min((cost[i], i) for i in range(n) if not done[i])[1]
        done[u], total = True, total + cost[u]
        x, y = points[u]
        for v, (px, py) in enumerate(points):
            if not done[v]:
                cost[v] = min(cost[v], abs(px - x) + abs(py - y))
    return total

Cost

Kruskal is O(E log E) for the sort plus near-constant union-find work per edge. Prim with a heap is O(E log V). Prim with an array, as above, is O(V²): the better choice when every pair is an edge, since E is then about V² ÷ 2.

Common mistakes

  • Summing Dijkstra's tree: the shortest paths from one node rarely form the cheapest tree overall.
  • Adding an edge in Kruskal without checking that its ends are in different components, which closes a cycle.
  • Building and sorting all n(n − 1) ÷ 2 pairs of a dense graph, which the array version of Prim never needs.
  • Assuming connectivity: fewer than n − 1 edges taken means there is no spanning tree.

Start with

All minimum spanning tree problems

Medium (1)

Next topic: Biconnected Component