Minimum Spanning Tree Kruskal's Algorithm in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the parent array for Union-Find.

DSA Typescript

const parent: number[] = new Array(n).fill(0).map((_, i) => [1]);

Drag options to blanks, or click blank then click option'

Ai

B0

Cn

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting all parents to 0 causes incorrect union-find behavior.

Using n or -1 as parent values leads to errors.

Each node is initially its own parent, so we assign parent[i] = i.

2fill in blank

medium

Complete the code to find the root parent of a node with path compression.

DSA Typescript

function findParent(parent: number[], node: number): number {
  if (parent[node] !== node) {
    parent[node] = [1];
  }
  return parent[node];
}

Drag options to blanks, or click blank then click option'

Anode + 1

Bnode

Cparent[node]

DfindParent(parent, parent[node])

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning parent[node] to node itself breaks path compression.

Using parent[node] without recursion does not find root.

Path compression sets parent[node] to the root parent found recursively.

3fill in blank

hard

Fix the error in the union function to correctly union two sets.

DSA Typescript

function union(parent: number[], a: number, b: number): void {
  const rootA = findParent(parent, a);
  const rootB = findParent(parent, b);
  if (rootA !== rootB) {
    parent[[1]] = rootB;
  }
}

Drag options to blanks, or click blank then click option'

ArootA

Bb

Ca

DrootB

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning parent of a or b instead of root parents causes incorrect unions.

Assigning parent[rootB] to rootA reverses union direction.

We set parent of rootA to rootB to union the sets correctly.

4fill in blank

hard

Fill both blanks to correctly check if two nodes belong to different sets before union.

DSA Typescript

if (findParent(parent, [1]) !== findParent(parent, [2])) {
  union(parent, u, v);
}

Drag options to blanks, or click blank then click option'

Au

Bv

Cparent[u]

Dparent[v]

Attempts:

3 left

💡 Hint

Common Mistakes

Using parent[u] or parent[v] instead of nodes causes wrong comparisons.

Comparing u and v directly without findParent misses set roots.

We compare root parents of u and v to decide if union is needed.

5fill in blank

hard

Fill all three blanks to sort edges by weight and build MST using Kruskal's algorithm.

DSA Typescript

edges.sort((a, b) => a[1]b[2]);
const mst: Edge[] = [];
for (const {u, v, weight} of edges) {
  if (findParent(parent, u) !== findParent(parent, v)) {
    union(parent, u, v);
    mst[3]({u, v, weight});
  }
}

Drag options to blanks, or click blank then click option'

A.weight -

B.weight >

C.weight <

Dpush

Attempts:

3 left

💡 Hint

Common Mistakes

Using comparison operators instead of subtraction in sort causes incorrect sorting.

Using incorrect method instead of push to add edges.

We sort edges by ascending weight using a subtraction comparator, check sets, and push edges to MST.