Given n nodes labeled 0 to n-1 and a list of undirected edges, determine if these edges form a valid tree.

A valid tree has exactly two properties:

  1. Connected – all nodes are reachable from any node
  2. Acyclic – no cycles

Examples

Example 1:

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

Example 2:

Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: false
Explanation: Cycle exists: 1→2→3→1

Constraints

  • 1 <= n <= 2000
  • 0 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= edges[i][0], edges[i][1] < n
  • No duplicate edges

Thinking Process

Key Observation

A graph with n nodes is a valid tree if and only if:

  1. It has exactly n - 1 edges
  2. It is connected (or equivalently, acyclic – with exactly n - 1 edges, one implies the other)

Early exit: if edges.size() != n - 1, immediately return false. Too few edges means disconnected; too many means a cycle exists.

After this check, we only need to verify one of: connected or acyclic.

Graph BFS layers S a b t BFS: expand by layers (queue)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Recursive DFS (this problem) O(n) O(h) stack Natural for trees and graphs
Iterative DFS (stack) O(n) O(n) Avoid recursion depth limits
DFS with memoization O(n) O(n) Overlapping subproblems on graphs
Backtracking DFS O(2^n) typical O(n) Enumerate choices with pruning

Solution

Union each edge. If both endpoints already share the same root, we’ve found a cycle.

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        if (edges.size() != n - 1) return false;
        parent.resize(n);
        for (int i = 0; i < n; ++i) parent[i] = i;
        for (auto& e : edges) {
            int pu = find(e[0]), pv = find(e[1]);
            if (pu == pv) return false;
            parent[pu] = pv;
        }
        return true;
    }

private:
    vector<int> parent;
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
};

Solution Explanation

Approach: Recursive DFS (this problem)

Key idea: ### Key Observation

How the code works:

  1. It has exactly n - 1 edges
  2. It is connected (or equivalently, acyclic – with exactly n - 1 edges, one implies the other) Early exit: if edges.size() != n - 1, immediately return false. Too few edges means disconnected; too many means a cycle exists.

Walkthrough — input n = 5, edges = [[0,1],[0,2],[0,3],[1,4]], expected output true:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

    Why nei != parent in DFS?

In an undirected graph, edge (u, v) appears in both adjacency lists. When DFS goes from u to v, looking back at v’s neighbors will see u again. Without the parent check, this would falsely report a cycle.

0 — 1 — 2

DFS: 0 → 1 → sees 0 (parent, skip) → 2 → sees 1 (parent, skip)
No cycle ✓

Comparison

Approach Time Space Notes
DSU O(n · α(n)) O(n) No graph construction needed
DFS O(n) O(n) Checks connectivity + acyclicity in one pass

Both are optimal. DSU is more concise; DFS is more intuitive for graph problems.

Common Mistakes

  • Forgetting the edges.size() != n - 1 early check (without it, DSU alone doesn’t catch disconnected components)
  • In DFS: not tracking parent, causing false cycle detection on undirected edges
  • Assuming the graph is connected just because there are no cycles (need n - 1 edges too)

Key Takeaways

  • Valid tree = exactly n - 1 edges + connected (or acyclic)
  • The edge count check is a powerful early exit that simplifies both DSU and DFS approaches
  • DSU naturally detects cycles during union; DFS naturally checks connectivity during traversal

References

Template Reference