Graph Valid Tree

Description

You are given n nodes labeled from 0 to n - 1 and a list of undirected edges, where each edge edges[i] = [a_i, b_i] indicates a bidirectional connection between nodes a_i and b_i.

Determine whether these edges form a valid tree.

A valid tree has two fundamental properties:

Connected: Every node must be reachable from every other node — there is a path between any pair of nodes.
Acyclic: There are no cycles — there is exactly one path between any two nodes.

An equivalent way to state this: an undirected graph with n nodes is a valid tree if and only if it is connected and has exactly n - 1 edges.

Note: No duplicate edges exist in the input, and since all edges are undirected, [0, 1] is the same as [1, 0] and will not both appear.

Two graphs side by side: a valid tree with 5 nodes and 4 edges, and an invalid graph with a cycle

Examples

Example 1

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

Output: true

Explanation: There are 5 nodes and 4 edges (which is n - 1 = 4). Starting from any node, you can reach all other nodes: 0 connects to 1, 2, and 3; node 1 also connects to 4. There is exactly one path between any two nodes. No cycle exists. This forms a valid tree.

Example 2

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

Output: false

Explanation: There are 5 nodes but 5 edges (more than n - 1 = 4). Nodes 1, 2, and 3 form a cycle: 1 → 2 → 3 → 1. Since a tree cannot contain any cycles, this graph is not a valid tree.

Example 3

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

Output: false

Explanation: There are 4 nodes and only 2 edges (fewer than n - 1 = 3). The graph has two disconnected components: {0, 1} and {2, 3}. Since a tree must be connected (all nodes reachable from one another), this is not a valid tree.

Constraints

1 ≤ n ≤ 100
0 ≤ edges.length ≤ n × (n - 1) / 2
edges[i].length == 2
0 ≤ a_i, b_i < n
a_i ≠ b_i
No duplicate edges exist

Editorial

Brute Force

Intuition

The most straightforward way to check if a graph is a valid tree is to directly verify both required properties: no cycles and full connectivity.

We can do this using a Depth-First Search (DFS) from any starting node (say node 0). As we traverse the graph, we keep track of which nodes we have visited. When exploring a node's neighbors, we skip the node we came from (the parent) to avoid falsely detecting a cycle on the reverse of the edge we just used. If we ever encounter a neighbor that is already visited and is NOT our parent, it means there is a second path to that node — which means a cycle exists.

After the DFS completes, we also check whether we visited all n nodes. If some nodes were never reached, the graph is disconnected.

As a quick optimization, we can check the edge count first: a tree with n nodes must have exactly n - 1 edges. If the count is wrong, we can return false immediately without even building the graph.

This DFS-based approach works in O(V + E) time, which is optimal for graph traversal.

Step-by-Step Explanation

Let's trace with n = 5, edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]] (the invalid tree with a cycle):

Step 1: Check edge count: 5 edges, but n - 1 = 4. Since 5 > 4, we already know a cycle must exist. Return false immediately.

Now let's trace the DFS approach on the valid tree to see it work fully: n = 5, edges = [[0, 1], [0, 2], [0, 3], [1, 4]].

Step 1: Check edge count: 4 edges = n - 1 = 4. Passes the quick check.

Step 2: Build adjacency list:

0: [1, 2, 3]
1: [0, 4]
2: [0]
3: [0]
4: [1]

Step 3: Start DFS from node 0, parent = -1. Mark 0 as visited. Visited = {0}.

Step 4: Explore neighbor 1 of node 0. Node 1 is not visited, not parent. Recurse: DFS(1, parent=0). Mark 1 as visited. Visited = {0, 1}.

Step 5: Explore neighbor 0 of node 1. Node 0 is the parent — skip it.

Step 6: Explore neighbor 4 of node 1. Node 4 is not visited. Recurse: DFS(4, parent=1). Mark 4 as visited. Visited = {0, 1, 4}.

Step 7: Node 4's only neighbor is 1 (its parent). Skip. DFS(4) returns true.

Step 8: DFS(1) finishes all neighbors. Returns true. Back to DFS(0).

Step 9: Explore neighbor 2 of node 0. Not visited. DFS(2, parent=0). Mark 2. Visited = {0, 1, 4, 2}. Node 2's only neighbor is 0 (parent). Skip. Returns true.

Step 10: Explore neighbor 3 of node 0. Not visited. DFS(3, parent=0). Mark 3. Visited = {0, 1, 4, 2, 3}. Node 3's only neighbor is 0 (parent). Skip. Returns true.

Step 11: DFS(0) complete. No cycle found. Check visited count: 5 = n. All nodes connected.

Result: true

DFS — Checking for Cycles and Connectivity — Watch how DFS traverses the graph from node 0, skipping parent edges to avoid false cycle detection, and verifies that all nodes are reachable.

Algorithm

If the number of edges is not equal to n - 1, return false immediately (a tree must have exactly n - 1 edges).
Build an adjacency list from the edges.
Run DFS starting from node 0, passing parent = -1:
- Mark the current node as visited.
- For each neighbor:
  - If the neighbor is the parent, skip it.
  - If the neighbor is already visited, a cycle exists — return false.
  - Otherwise, recurse with the current node as the parent.
After DFS, check if all n nodes were visited (ensuring connectivity).
Return true if no cycle and all nodes visited.

Code

#include <vector>
using namespace std;

class Solution {
public:
    bool validTree(int n, vector<vector<int>>& edges) {
        if (edges.size() != n - 1) return false;
        
        // Build adjacency list
        vector<vector<int>> adj(n);
        for (auto& e : edges) {
            adj[e[0]].push_back(e[1]);
            adj[e[1]].push_back(e[0]);
        }
        
        vector<bool> visited(n, false);
        
        // DFS to detect cycles
        if (!dfs(0, -1, adj, visited)) return false;
        
        // Check connectivity
        for (int i = 0; i < n; i++) {
            if (!visited[i]) return false;
        }
        return true;
    }
    
private:
    bool dfs(int node, int parent, vector<vector<int>>& adj, vector<bool>& visited) {
        visited[node] = true;
        for (int neighbor : adj[node]) {
            if (neighbor == parent) continue;
            if (visited[neighbor]) return false; // Cycle detected
            if (!dfs(neighbor, node, adj, visited)) return false;
        }
        return true;
    }
};

class Solution:
    def validTree(self, n: int, edges: list[list[int]]) -> bool:
        if len(edges) != n - 1:
            return False
        
        # Build adjacency list
        adj = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
        
        visited = set()
        
        def dfs(node, parent):
            visited.add(node)
            for neighbor in adj[node]:
                if neighbor == parent:
                    continue
                if neighbor in visited:
                    return False  # Cycle detected
                if not dfs(neighbor, node):
                    return False
            return True
        
        # Check for cycles starting from node 0
        if not dfs(0, -1):
            return False
        
        # Check connectivity
        return len(visited) == n

import java.util.*;

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        
        // Build adjacency list
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        
        boolean[] visited = new boolean[n];
        
        // DFS to detect cycles
        if (!dfs(0, -1, adj, visited)) return false;
        
        // Check connectivity
        for (int i = 0; i < n; i++) {
            if (!visited[i]) return false;
        }
        return true;
    }
    
    private boolean dfs(int node, int parent, List<List<Integer>> adj, boolean[] visited) {
        visited[node] = true;
        for (int neighbor : adj.get(node)) {
            if (neighbor == parent) continue;
            if (visited[neighbor]) return false;
            if (!dfs(neighbor, node, adj, visited)) return false;
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(V + E)

Building the adjacency list takes O(E). The DFS visits each node once and examines each edge twice (once from each endpoint), giving O(V + E). The connectivity check is O(V). Total: O(V + E).

Space Complexity: O(V + E)

The adjacency list stores 2E entries across all lists, taking O(E) space. The visited set/array takes O(V). The recursion stack can go up to O(V) deep in the worst case (a path graph). Total: O(V + E).

Why This Approach Is Not Efficient

The DFS approach is actually efficient at O(V + E), so in terms of time complexity it is hard to improve. However, it has some practical drawbacks:

Recursion overhead: DFS uses the call stack, which can cause stack overflow for very deep graphs (though with n ≤ 100 here, this isn't a concern).
Two-phase verification: We first build the entire adjacency list, then traverse it. The cycle detection and connectivity checks are interleaved with the DFS but conceptually we're doing two things.
Parent tracking complexity: In an undirected graph, we must carefully track the parent to avoid false cycle detection. This adds cognitive complexity.

An alternative approach using Union-Find (Disjoint Set Union) elegantly combines cycle detection and connectivity checking into a single pass through the edges — no adjacency list needed, no recursion, and the logic is simpler. Union-Find processes edges one at a time: if two nodes already belong to the same set, adding an edge between them creates a cycle. After processing all edges, we check that exactly one connected component remains.

Optimal Approach - Union-Find (Disjoint Set Union)

Intuition

Imagine each of the n nodes starts as its own isolated group (or "island"). An edge between two nodes is like building a bridge between their islands, merging them into a single connected landmass.

Now, what happens if you try to build a bridge between two nodes that are already on the same island? It means there was already a path connecting them, and this new bridge creates a shortcut — in graph terms, a cycle. A tree cannot have cycles, so this immediately tells us the graph is invalid.

Union-Find (also called Disjoint Set Union or DSU) is a data structure designed exactly for this scenario. It supports two operations:

Find(x): Determine which group node x belongs to (its root representative).
Union(x, y): Merge the groups of x and y into one.

The algorithm processes edges one by one. For each edge [a, b]:

Find the root of a and the root of b.
If they share the same root → they're already connected → adding this edge creates a cycle → return false.
If they have different roots → merge their groups (union them) → the number of connected components decreases by 1.

After processing all edges, if exactly 1 connected component remains, the graph is fully connected. Combined with the no-cycle guarantee, we have a valid tree.

With path compression (making nodes point directly to their root during find) and union by rank/size, each operation takes nearly O(1) amortized time.

Step-by-Step Explanation

Let's trace with n = 5, edges = [[0, 1], [0, 2], [0, 3], [1, 4]]:

Step 1: Quick check: 4 edges = n - 1 = 4. Passes.

Step 2: Initialize parent array: parent = [0, 1, 2, 3, 4]. Each node is its own parent. Components = 5.

Step 3: Process edge [0, 1]. Find root of 0 → 0. Find root of 1 → 1. Roots differ (0 ≠ 1), no cycle. Union: set parent[0] = 1. Components = 4.

Step 4: Process edge [0, 2]. Find root of 0 → parent[0]=1 → 1. Find root of 2 → 2. Roots differ (1 ≠ 2), no cycle. Union: set parent[1] = 2. Components = 3.

Step 5: Process edge [0, 3]. Find root of 0 → parent[0]=1 → parent[1]=2 → 2 (with path compression, parent[0] also becomes 2). Find root of 3 → 3. Roots differ (2 ≠ 3), no cycle. Union: set parent[2] = 3. Components = 2.

Step 6: Process edge [1, 4]. Find root of 1 → parent[1]=2 → parent[2]=3 → 3. Find root of 4 → 4. Roots differ (3 ≠ 4), no cycle. Union: set parent[3] = 4. Components = 1.

Step 7: All edges processed. Components = 1. The graph is connected and has no cycles.

Result: true

Union-Find — Merging Components Edge by Edge — Watch how Union-Find processes each edge, detecting whether it would create a cycle and merging components. The component count decreases with each valid union until one remains.

Algorithm

If the number of edges ≠ n - 1, return false (quick rejection).
Initialize a parent array where parent[i] = i for all nodes.
Implement a find(x) function with path compression:
- If parent[x] ≠ x, recursively set parent[x] = find(parent[x]).
- Return parent[x].
For each edge [a, b]:
- Find the root of a and the root of b.
- If they have the same root, a cycle exists — return false.
- Otherwise, union them: set parent[root_a] = root_b.
- Decrement the component count.
After all edges, return true if components == 1 (all nodes connected).

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> parent;
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }
    
    bool validTree(int n, vector<vector<int>>& edges) {
        if ((int)edges.size() != n - 1) return false;
        
        parent.resize(n);
        for (int i = 0; i < n; i++) parent[i] = i;
        
        int components = n;
        
        for (auto& e : edges) {
            int rootA = find(e[0]);
            int rootB = find(e[1]);
            
            if (rootA == rootB) return false; // Cycle detected
            
            parent[rootA] = rootB; // Union
            components--;
        }
        
        return components == 1;
    }
};

class Solution:
    def validTree(self, n: int, edges: list[list[int]]) -> bool:
        if len(edges) != n - 1:
            return False
        
        parent = list(range(n))
        
        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])  # Path compression
            return parent[x]
        
        components = n
        
        for a, b in edges:
            root_a = find(a)
            root_b = find(b)
            
            if root_a == root_b:
                return False  # Cycle detected
            
            parent[root_a] = root_b  # Union
            components -= 1
        
        return components == 1

class Solution {
    private int[] parent;
    
    private int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }
    
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        
        int components = n;
        
        for (int[] e : edges) {
            int rootA = find(e[0]);
            int rootB = find(e[1]);
            
            if (rootA == rootB) return false; // Cycle detected
            
            parent[rootA] = rootB; // Union
            components--;
        }
        
        return components == 1;
    }
}

Complexity Analysis

Time Complexity: O(E × α(n)) ≈ O(E)

We process each of the E edges once. For each edge, we perform two find operations and one union. With path compression, each find takes amortized O(α(n)) time, where α is the inverse Ackermann function — a function that grows so slowly it is effectively constant (≤ 4) for all practical input sizes. Since E = n - 1 for a valid tree, the total time is O(n × α(n)) ≈ O(n).

Space Complexity: O(n)

We store the parent array of size n. The recursion stack for find with path compression has depth at most O(log n) in the worst case, but path compression flattens the tree quickly. No adjacency list is needed — a significant space advantage over the DFS approach.