Problem
Given n nodes labeled from0 to n - 1 and an array of undirected edges, determine whether the graph forms a valid tree.
A valid tree must have no cycles and all nodes must be connected.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
n = 5
edges = [[0,1],[0,2],[0,3],[1,4]]Graph
2
|
1 ----- 0 ----- 3
|
4
Output
trueSolution
A valid tree must satisfy two conditions: it must contain no cycles, and all n nodes must be connected.A graph with
n nodes can be a tree only if it contains exactly n - 1 edges. If the number of edges is different, the graph cannot be a valid tree.
After verifying the number of edges, we build an adjacency list and use Depth-First Search (DFS) starting from node
0. DFS visits every node connected to the starting node.
Finally, we check whether all
n nodes were visited. If they were, the graph is fully connected. Since it also contains exactly n - 1 edges, the graph must be a valid tree.
public boolean validTree(int n, int[][] edges) {
// A tree with n nodes must have exactly n - 1 edges.
if (edges.length != n - 1) {
return false;
}
List<List<Integer>> graph = new ArrayList<>();
// Create the adjacency list.
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
// Add edges in both directions.
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
boolean[] visited = new boolean[n];
dfs(0, graph, visited);
// Check that all nodes are connected.
for (boolean nodeVisited : visited) {
if (!nodeVisited) {
return false;
}
}
return true;
}
private void dfs(int node, List<List<Integer>> graph,
boolean[] visited) {
visited[node] = true;
// Visit all connected nodes.
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
dfs(neighbor, graph, visited);
}
}
}
Complexity
Building the adjacency list and traversing the graph visits each node and edge at most once, resulting inO(V + E) time complexity.
The adjacency list and visited array require
O(V + E) extra space.
BFS Approach
The graph can also be traversed using Breadth-First Search (BFS) instead of DFS.After checking that the graph contains exactly
n - 1 edges, we build the adjacency list and start BFS from node 0. A queue is used to visit connected nodes level by level, while a visited set ensures that each node is processed only once.
When BFS finishes, we check whether all
n nodes were reached. If every node was visited, the graph is fully connected. Combined with the n - 1 edge condition, this confirms that the graph is a valid tree.
public boolean validTree(int n, int[][] edges) {
// A tree with n nodes must have exactly n - 1 edges.
if (edges.length != n - 1) {
return false;
}
List<List<Integer>> graph = new ArrayList<>();
// Create the adjacency list.
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
// Add edges in both directions.
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.offer(0);
visited.add(0);
while (!queue.isEmpty()) {
int node = queue.poll();
// Visit all unvisited neighbors.
for (int neighbor : graph.get(node)) {
if (visited.contains(neighbor)) {
continue;
}
visited.add(neighbor);
queue.offer(neighbor);
}
}
// Check that all nodes are connected.
return visited.size() == n;
}
Complexity
BFS visits each vertex and edge at most once, resulting inO(V + E) time complexity. The adjacency list, queue, and visited set require O(V + E) extra space.