Approach Summary
An undirected graph is a valid tree if and only if it has exactly n - 1 edges, is fully connected, and contains no cycles. Verify with DFS, BFS, or Union-Find.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: DFS Cycle Detection and Connectivity (Optimal) | O(V + E) = O(n) | O(V + E) = O(n) | Confirm edge count is n - 1, then traverse via DFS to confirm full connectivity and no cycles. |
| 2 Approach 2: Union-Find (Disjoint Set Union) | O(n · α(n)) ≈ O(n) | O(n) | Process edges with Disjoint Set Union (DSU) to detect cycles upon connecting existing components. |
Step 1: Baseline
Approach 1: DFS Cycle Detection and Connectivity (Optimal)
Time: O(V + E) = O(n)
Space: O(V + E) = O(n)
A tree with n vertices must contain exactly n - 1 edges. If edges.length != n - 1, return false immediately. Then build the undirected adjacency list. Start a DFS from node 0 passing parent = -1. When visiting neighbor, if it has already been visited and neighbor != parent, an undirected cycle exists (return true). Finally verify that all n vertices were marked visited.
Approach 1: DFS Cycle Detection and Connectivity (Optimal) Implementation
Approach 1: DFS Cycle Detection and Connectivity (Optimal)
public class Solution {
public static boolean hasCycle(int v, List<List<Integer>> adj, boolean visited[], int parent) {
visited[v] = true;
List<Integer> neighbors = adj.get(v);
for (int neighbor : neighbors) {
if (!visited[neighbor]) {
if (hasCycle(neighbor, adj, visited, v)) return true;
} else if (parent != neighbor) {
return true;
}
}
return false;
}
public static Boolean checkGraph(int[][] edges, int n, int m) {
if (m != n - 1) return false;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
boolean visited[] = new boolean[n];
if (hasCycle(0, adj, visited, -1)) return false;
for (int i = 0; i < n; i++) {
if (!visited[i]) return false;
}
return true;
}
}class Solution {
public:
bool hasCycle(int v, vector<vector<int>>& adj, vector<bool>& visited, int parent) {
visited[v] = true;
for (int neighbor : adj[v]) {
if (!visited[neighbor]) {
if (hasCycle(neighbor, adj, visited, v)) return true;
} else if (parent != neighbor) {
return true;
}
}
return false;
}
bool checkgraph(vector<vector<int>> edges, int n, int m) {
if (m != n - 1) return false;
vector<vector<int>> adj(n);
for (auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
vector<bool> visited(n, false);
if (hasCycle(0, adj, visited, -1)) return false;
for (int i = 0; i < n; i++) {
if (!visited[i]) return false;
}
return true;
}
};def valid_tree(n: int, edges: list[list[int]]) -> bool:
if len(edges) != n - 1:
return False
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
visited = [False] * n
def has_cycle(v, parent):
visited[v] = True
for neighbor in adj[v]:
if not visited[neighbor]:
if has_cycle(neighbor, v):
return True
elif neighbor != parent:
return True
return False
if has_cycle(0, -1):
return False
return all(visited)function validTree(n, edges) {
if (edges.length !== n - 1) return false;
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
}
const visited = new Array(n).fill(false);
function hasCycle(v, parent) {
visited[v] = true;
for (const neighbor of adj[v]) {
if (!visited[neighbor]) {
if (hasCycle(neighbor, v)) return true;
} else if (neighbor !== parent) {
return true;
}
}
return false;
}
if (hasCycle(0, -1)) return false;
for (let i = 0; i < n; i++) {
if (!visited[i]) return false;
}
return true;
} Step 2: Most Optimized
Approach 2: Union-Find (Disjoint Set Union)
Time: O(n · α(n)) ≈ O(n)
Space: O(n)
Initialize a parent array parent[i] = i with rank or component count = n. For each edge (u, v), find the roots of u and v. If rootU == rootV, adding this edge connects already connected vertices, introducing a cycle (return false). Otherwise, union the sets and decrement the component count. If all edges are successfully unioned and components == 1, the graph is a valid tree.
Approach 2: Union-Find (Disjoint Set Union) Implementation
Approach 2: Union-Find (Disjoint Set Union)
class Solution {
int find(int[] parent, int x) {
if (parent[x] != x) parent[x] = find(parent, parent[x]);
return parent[x];
}
public boolean validTree(int n, int[][] edges) {
if (edges.length != n - 1) return false;
int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
for (int[] edge : edges) {
int rootU = find(parent, edge[0]);
int rootV = find(parent, edge[1]);
if (rootU == rootV) return false;
parent[rootU] = rootV;
}
return true;
}
}class Solution {
public:
int findRoot(vector<int>& parent, int x) {
if (parent[x] != x) parent[x] = findRoot(parent, parent[x]);
return parent[x];
}
bool validTree(int n, vector<vector<int>>& edges) {
if ((int)edges.size() != n - 1) return false;
vector<int> parent(n);
iota(parent.begin(), parent.end(), 0);
for (const auto& edge : edges) {
int rootU = findRoot(parent, edge[0]);
int rootV = findRoot(parent, edge[1]);
if (rootU == rootV) return false;
parent[rootU] = rootV;
}
return true;
}
};def valid_tree(n: int, edges: list[list[int]]) -> bool:
if len(edges) != n - 1:
return False
parent = list(range(n))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
for u, v in edges:
root_u, root_v = find(u), find(v)
if root_u == root_v:
return False
parent[root_u] = root_v
return Truefunction validTree(n, edges) {
if (edges.length !== n - 1) return false;
const parent = Array.from({ length: n }, (_, i) => i);
function find(x) {
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
for (const [u, v] of edges) {
const rootU = find(u);
const rootV = find(v);
if (rootU === rootV) return false;
parent[rootU] = rootV;
}
return true;
}Edge Cases to Watch
- Graph with fewer or more than n - 1 edges (immediately false)
- Disconnected components with no cycles (e.g. n = 4, edges = [[0,1],[2,3]])
- Single node with 0 edges (n = 1, edges = [] is a valid tree, returns true)
- Self-loops or multiple edges between same vertices
Algorithmic Pattern
View Pattern Guide →
Master the Graphs Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Graphs pattern.
How to Recognize This Pattern
- Determine if undirected graph forms a single valid tree
- Must have n - 1 edges, full connectivity, and zero cycles
Complexity Analysis
Time Complexity
O(V + E)
Space Complexity
O(V + E)
Tags
Depth-First Search Breadth-First Search Union Find Graph
Frequently Asked Questions
What is the optimal time and space complexity for Graph Valid Tree?
The optimal solution for Graph Valid Tree achieves O(V + E) runtime complexity and requires O(V + E) auxiliary space. Checking edges.length takes O(1). Building adjacency lists and running DFS visits every node and edge once in O(V + E) = O(n) time. The visited array and recursion call stack use O(V) = O(n) auxiliary space.
How do I identify that Graph Valid Tree requires the Graphs pattern?
In technical interviews, look for key problem signals: Determine if undirected graph forms a single valid tree; Must have n - 1 edges, full connectivity, and zero cycles. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Graphs strategy.
What critical edge cases must be handled in Graph Valid Tree?
Essential edge cases to verify include: Graph with fewer or more than n - 1 edges (immediately false); Disconnected components with no cycles (e.g. n = 4, edges = [[0,1],[2,3]]); Single node with 0 edges (n = 1, edges = [] is a valid tree, returns true); Self-loops or multiple edges between same vertices. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Graph Valid Tree?
Graph Valid Tree is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Google, Facebook, Amazon, LinkedIn.