Typorithm · medium

Graph Valid Tree

graph-valid-treeunion-findedge-countno-cycleconnectivity

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Graph Valid Tree

Union-Find

A graph is a tree iff it has exactly n-1 edges and every union succeeds — together these force connected and acyclic.

A valid tree is connected and has no cycle.

First check there are exactly n-1 edges; fewer or more cannot be a tree.

Then union every edge: if any union fails, a cycle exists; with n-1 edges and no cycle, the graph must be fully connected.

A tree has exactly n-1 edges.

Any failed union = a cycle.

n-1 edges + no cycle = connected.

function validTree(n, edges) {
  if (edges.length !== n - 1) {
    return false;
  }

  const uf = new UnionFind(n);
  for (const [a, b] of edges) {
    if (!uf.union(a, b)) {
      return false;
    }
  }

  return true;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Exactly n-1 edges

A tree on n nodes has precisely n-1 edges.

if (edges.length !== n - 1) {
    return false;
  }

2. Union must succeed

A failed union means the edge closes a cycle.

if (!uf.union(a, b)) {
      return false;
    }

3. Connected & acyclic

n-1 edges with no cycle force a single connected tree.

return true

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.