Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumunion-find

Graph Valid Tree

Problem (restated)

n nodes labeled 0..n-1 and undirected edges. Return true if they form a valid tree (connected, acyclic).

Intuition

A tree on n nodes has exactly n-1 edges and is connected. Union-Find rejects any edge that merges already-united nodes (cycle).

Approaches

Union-Find + edge count

Unverified

Time O(n)Space O(n)

Idea. If edges.length != n-1 fail. Union each edge; return false on redundant link. With n-1 successful unions the graph is connected.

Walkthrough. n=5, edges=[[0,1],[0,2],[0,3],[1,4]] → true; adding [1,2] would cycle.

Trade-offs. BFS/DFS from 0 also works; UF is O(α(n)) per op.

Solution

export function validTree(n: number, edges: number[][]): boolean {
  if (edges.length !== n - 1) return false;
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]!]!;
      x = parent[x]!;
    }
    return x;
  };
  for (const e of edges) {
    const a = find(e[0]!), b = find(e[1]!);
    if (a === b) return false;
    parent[b] = a;
  }
  return true;
}

export function validTree(n: number, edges: number[][]): boolean {
  if (edges.length !== n - 1) return false;
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]!]!;
      x = parent[x]!;
    }
    return x;
  };
  for (const e of edges) {
    const a = find(e[0]!), b = find(e[1]!);
    if (a === b) return false;
    parent[b] = a;
  }
  return true;
}

Template connection

Union-Find for cycle detection + connectivity.

Reflection

n nodes and n - 1 edges are not enough on their own. The graph must also be one component. An extra edge is a cycle. Too few edges is a forest.
Return false when len(edges) != n - 1. A union onto the same root is a cycle. n - 1 successful unions are already one component.
n = 1 with no edges is a tree. Two nodes and no edge is not. A self-edge is a cycle.