Solution

You'll decide whether n nodes and a list of undirected edges form a valid tree — a graph that is fully connected and has no cycle.

The problem, in plain English

Think of the nodes as offices and the edges as the cables linking them. A tree wiring is the leanest possible network that still connects everyone: there's exactly one path between any two offices, no cable is redundant, and no office is stranded. If you can unplug any single cable and split the building into two disconnected halves, and you can't add a cable without creating a loop, you have a tree.

So a graph is a tree when two things hold at once: it is connected (start anywhere, reach everyone) and it is acyclic (no path loops back to where it started). Miss either one and it's not a tree — a loop makes it a "graph with a cycle," and a gap makes it a "forest" of separate pieces.

The mental model

The three shapes you need to tell apart look like this. Only the first is a tree.

There's a shortcut hiding in the picture. A tree on n nodes always has exactly n - 1 edges — every node except the root is attached by precisely one edge to the rest. That gives you a fast necessary check: if edges.length !== n - 1, it cannot be a tree. But the edge count alone is not enough. You also have to confirm every node is actually reachable.

A first attempt

The most common wrong answer is to check only one of the two conditions. Here's the version that checks only for cycles — it walks the graph and flags any edge that revisits an already-seen node:

function treeNaive(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    adj[u].push(v);
    adj[v].push(u);
  }
  const visited = new Set();
  // DFS that returns false the moment it finds a cycle.
  function dfs(node, parent) {
    visited.add(node);
    for (const next of adj[node]) {
      if (next === parent) continue;       // the edge we just came in on
      if (visited.has(next)) return false; // back-edge → cycle
      if (!dfs(next, node)) return false;
    }
    return true;
  }
  return dfs(0, -1); // start from node 0
}

Run this on the disconnected forest graphIsTree(4, [[0, 1], [2, 3]]). The DFS starts at node 0, visits node 1, finds no cycle, and returns true. But nodes 2 and 3 were never touched — they're a separate component, so this is not a tree, yet the naive version says true. The bug: checking "no cycle" alone passes every forest. A forest is acyclic by definition; it just isn't connected. You have to verify connectivity too — and the cheapest way to fold both checks together is union-find.

The working solution

Union-find (also called a disjoint-set) keeps each node's "group" as you process edges one at a time. Two operations: find(x) returns the representative (root) of x's group, and union(x, y) merges two groups. The insight: if you're about to union two nodes that already share a root, this edge closes a loop — a cycle. And if, after processing every edge, all nodes still sit in one group, the graph is connected.

function graphIsTree(n, edges) {
  // A tree on n nodes has exactly n - 1 edges. Fewer can't connect
  // everyone; more must create a cycle. Cheap necessary check first.
  if (edges.length !== n - 1) return false;

  // parent[i] is i's parent in the disjoint-set forest; a root points
  // to itself. Every node starts in its own one-element group.
  const parent = Array.from({ length: n }, (_, i) => i);

  // Find the root of x, compressing the path so later finds are fast.
  function find(x) {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]]; // point x at its grandparent
      x = parent[x];
    }
    return x;
  }

  for (const [u, v] of edges) {
    const rootU = find(u);
    const rootV = find(v);
    // Same root means u and v are already connected — this edge would
    // close a loop. That's a cycle, so it's not a tree. (A self-loop
    // [u, u] also lands here: find(u) === find(u).)
    if (rootU === rootV) return false;
    parent[rootU] = rootV; // merge the two groups
  }

  // We did exactly n - 1 unions with no cycle, so all n nodes are now
  // in a single group: the graph is connected. It's a tree.
  return true;
}

module.exports = { graphIsTree };

The key shift from the naive version: we no longer ask "is there a cycle?" in isolation. The edges.length !== n - 1 guard plus "no union ever found two nodes already connected" together prove both properties. With exactly n - 1 edges and zero cycles detected, the n nodes must collapse into one group — there's no way to do n - 1 merges across n singletons without connecting them all unless one merge was wasted on an already-joined pair, and that case is exactly what the rootU === rootV check rejects.

Walking through one call

Start with the cycle example from the prompt, graphIsTree(4, [[0, 1], [1, 2], [2, 0], [0, 3]]). It has 4 edges over 4 nodes:

edge count: edges.length = 4, n - 1 = 3
4 !== 3  →  return false immediately

That one never reaches the union-find loop — the count gate alone rejects it. The edge-count gate catches every non-tree whose edge count is wrong, and that's most of them: any cycle that adds an edge pushes the count above n - 1, and any disconnected graph with no redundant links sits below it. Union-find earns its keep on the one family the count can't see — exactly n - 1 edges, but arranged so one component carries a redundant link while another node is left stranded.

The cleanest example of that family is the duplicate edge: graphIsTree(4, [[0, 1], [1, 0], [2, 3]]). That's 3 edges and n - 1 = 3, so the count passes, but 0-1 is wired twice (a 2-node loop) while 2 and 3 are off on their own.

parent = [0, 1, 2, 3]                  (each node its own root)

edge [0, 1]   find(0)=0, find(1)=1   different → merge: parent[0]=1
              parent = [1, 1, 2, 3]

edge [1, 0]   find(1)=1, find(0)=1   SAME root → return false

Union-find spots the loop the instant the second edge's endpoints share a root — and it never even has to notice that node 2 and node 3 are off in their own world. One redundant edge always means some node elsewhere got starved of its connection, so detecting the cycle is enough.

Now a passing trace — the valid tree graphIsTree(5, [[0, 1], [0, 2], [0, 3], [1, 4]]):

edges.length = 4, n - 1 = 4  →  count passes
parent = [0, 1, 2, 3, 4]

edge [0, 1]   roots 0, 1 differ → parent[0] = 1   → [1, 1, 2, 3, 4]
edge [0, 2]   find(0)=1, find(2)=2 differ → parent[1] = 2 → [1, 2, 2, 3, 4]
edge [0, 3]   find(0)=2, find(3)=3 differ → parent[2] = 3 → [1, 2, 3, 3, 4]
edge [1, 4]   find(1)=3, find(4)=4 differ → parent[3] = 4 → [1, 2, 3, 4, 4]

no cycle ever found, 4 successful unions → return true

Four merges, never once finding two nodes already joined, so all five nodes ended up in one group. It's a tree.

If you'd rather verify connectivity with a traversal than with union-find, that works too: pass the edge-count gate, build an adjacency list, run one DFS or BFS from node 0, and check that the count of visited nodes equals n. With exactly n - 1 edges, "reached all n nodes" already implies "no cycle," so the two checks again collapse into one.

Gotchas

• Checking only "no cycle" passes every forest. A DFS that just looks for back-edges returns true on graphIsTree(4, [[0, 1], [2, 3]]) — two disconnected pairs, no cycle, but not a tree. Fix: also confirm connectivity (visited count === n, or a single union-find group).
• Checking only "connected" misses the count requirement. If you only run a traversal from node 0 and check you reached everyone, a graph with n edges that happens to be connected (so it has a cycle) slips through. Fix: keep the edges.length === n - 1 gate; with it, "connected" and "acyclic" become two sides of the same coin.
• n - 1 edges is necessary but not sufficient. graphIsTree(4, [[0, 1], [1, 0], [2, 3]]) has exactly 3 edges, yet the duplicate 0-1 is a cycle and 2-3 is stranded. The count passes; connectivity (or the union-find cycle check) is what rejects it.
• Self-loops are cycles. An edge [u, u] makes find(u) === find(u), so the union-find branch returns false correctly. With a DFS, guard against treating the self-loop's "parent" specially — a node is its own neighbour here, which is a one-node cycle.
• Undirected edges must go both ways in an adjacency list. If you build adj and only push adj[u].push(v), your DFS can reach v from u but never u from v, and you'll wrongly report disconnection. Push both adj[u].push(v) and adj[v].push(u). (Union-find sidesteps this — it treats each edge symmetrically by construction.)
• The DFS parent guard skips the edge you arrived on, not all repeats. In an undirected graph, every edge appears twice in the adjacency list, so a naive visited.has(next) check sees the node you just came from and false-alarms a cycle. Pass the parent down and continue past it — but only skip it once, or a genuine duplicate edge back to the parent (a real cycle) gets missed.

Going further

• Union-find with path compression and union by rank. The find above already does one-step path halving (parent[x] = parent[parent[x]]). Combine full path compression with union by rank (always attach the shorter tree under the taller one) and the amortised cost per operation drops to near-constant — the inverse Ackermann function α(n), which is ≤ 4 for any n you'll ever see. See disjoint-set data structure.
• Counting connected components. A small change turns this into "how many separate pieces?" Start a counter at n, decrement it on every successful union (one that merged two different groups). The final counter is the number of connected components — 1 means the whole graph is connected. A tree is exactly the case "components === 1 and no cycle."
• Minimum spanning tree. When edges carry weights and the graph has cycles, you often want the cheapest subset of edges that still connects everyone — a minimum spanning tree. Kruskal's algorithm sorts edges by weight and adds each one unless its endpoints already share a union-find root (which would make a cycle) — the very same cycle test you wrote here, reused as the gatekeeper for building the tree.