AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started

Topic

Minimum Spanning Tree coding problems

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.

New to minimum spanning tree? Read the Minimum Spanning Tree: Kruskal's and Prim's Algorithms tutorial first.

4 problems · 3 medium · 1 hard · judged by hidden tests in 13 languages

4problems

0 easy

3 medium

1 hard

Sign in to tick off what you solve.

Study plan: 4 problems · about 2 h 50 min

Start the study plan

Next up: Min Cost to Connect All Points

How it works

Minimum Spanning Tree, step by step

Minimum spanning tree of a weighted graph, with Kruskal's algorithm

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

431245768ABCDEFsorted edgesB–C 1B–D 2A–C 3A–B 4C–D 4C–E 5D–F 6D–E 7E–F 8components: {A} {B} {C} {D} {E} {F}total weight = 0

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.

0:01 / 0:29Step 1 of 9
Transcript · 9 steps

Study plan

Learn minimum spanning tree in 3 days

All 4 Minimum Spanning Tree problems (3 medium and 1 hard) over 3 days, about 2 h 50 min in all — the pattern first, then easiest to hardest. Then move on to Biconnected Component.

  1. Day 1

    about 50 min

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

  2. Day 2

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  3. Day 3

    about 50 min

    Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

    Next topic: Biconnected Component

Minimum Spanning Tree Coding Problems: 4 Questions with Solutions

4 minimum spanning tree coding problems — 3 medium · 1 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 3-day plan.

  • Problems: 4
  • By difficulty: 3 medium · 1 hard
  • 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.

New to minimum spanning tree? Read the Minimum Spanning Tree: Kruskal's and Prim's Algorithms tutorial first.

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

All 4 Minimum Spanning Tree problems (3 medium and 1 hard) over 3 days, about 2 h 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.

Day 2

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 3

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

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 (3)

Hard (1)

Companies that ask minimum spanning tree problems

  • Amazon 3 problems on minimum spanning tree
  • Directi 1 problem on minimum spanning tree
  • Flipkart 1 problem on minimum spanning tree
  • Google 1 problem on minimum spanning tree
  • Samsung 1 problem on minimum spanning tree

Next topic: Biconnected Component