Graph Valid Tree

Difficulty: Medium

Problem

You are given n nodes labeled 0 to n−1 and a list of undirected edges. Return true if these edges form a valid TREE. You spent a whole track climbing trees — now prove you know what one is: connected, and without a single cycle.

Example

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true
Explanation: Four edges hang all five nodes together with no loop anywhere — that's a tree (rooted anywhere you like).

Brute-force approach

No brute-force phase for graph problems — the insight (edge count + one flood) IS the algorithm.

Optimal approach

Key insight: Edges are a budget: connecting n nodes costs exactly n−1, and a cycle overspends. Right count + full reach = tree — no explicit cycle detection needed.

Check the edge count (must be exactly n−1), then run one BFS from node 0 and verify it reaches all n nodes.

Steps

  1. If len(edges) ≠ n − 1, return false immediately
  2. Build the adjacency list (both directions)
  3. BFS from node 0 with a visited set
  4. Return whether visited grew to all n nodes

Time complexity: O(V + E) · Space complexity: O(V + E)