You're handed a network: n nodes labelled 0 to n-1, plus a list of undirected connections between them. Some networks are trees — every node reachable from every other, with exactly one path between any two and no redundant links. Others have loops, or split into disconnected islands. Your job is to decide: do these nodes and edges form a valid tree?
A graph is a tree when it satisfies two conditions at once: it is fully connected (you can reach every node starting from any node) and it has no cycle (no path loops back on itself). An equivalent and often easier test: the graph is connected and has exactly n - 1 edges.
// n: number — count of nodes, labelled 0, 1, ..., n-1
// edges: [number, number][]
// — undirected edges; [u, v] means u and v are connected.
// [u, v] and [v, u] mean the same thing.
// returns: boolean — true if the n nodes + edges form a valid tree.
function graphIsTree(n, edges): boolean;// A valid tree: 5 nodes, 4 edges, fully connected, no cycle.
graphIsTree(5, [[0, 1], [0, 2], [0, 3], [1, 4]]); // → true// A cycle: 0-1-2-0 is a triangle. Connected, but loops back on itself.
graphIsTree(4, [[0, 1], [1, 2], [2, 0], [0, 3]]); // → false// A disconnected forest: {0,1} and {2,3} are two separate components.
graphIsTree(4, [[0, 1], [2, 3]]); // → false// A single node with no edges is the smallest tree.
graphIsTree(1, []); // → true[u, v] and [v, u] describe the same connection. If you build an adjacency list, add each edge in both directions.0 to n-1. Every integer in that range is a node, even if it appears in no edge — an isolated node makes the graph disconnected.n - 1 edges. With fewer than n - 1 edges the graph cannot be connected; with more, it must contain a cycle. The edge count is necessary but not sufficient on its own — you still have to verify connectivity.n = 1 with no edges is a tree. One node, nothing to connect, no cycle.[0, 0] is a cycle; a duplicate edge [0, 1] repeated creates a redundant link, so the graph is no longer a tree.n >= 1 — you do not need to handle n = 0.