# Problem:

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Show Hint Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

# Solutions:

DFS

``````public class Solution {
public boolean validTree(int n, int[][] edges) {
HashMap<Integer, List<Integer>> adj = new HashMap<Integer, List<Integer>>();
int[] color = new int[n]; // 0 is white 1 is gray and 2 is black
if (!dfsVisit(-1, 0, adj, color)) {
return false;
}
for (int i = 0; i < color.length; i ++) {
if (color[i] == 0) {
return false;
}
}
return true;
}
private void init(HashMap<Integer, List<Integer>> adj, int[][] edges) {
for (int i = 0; i < edges.length; i ++) {
}
}
}
}
private boolean dfsVisit(int parent, int index, HashMap<Integer, List<Integer>> adj, int[] color) {
if (color[index] != 0) {
return false;
}
color[index] = 1;
if (parent != i && !dfsVisit(index, i, adj, color)) {
return false;
}
}
}
return true;
}
}
``````

BFS

``````public class Solution {
public boolean validTree(int n, int[][] edges) {
HashMap<Integer, List<Integer>> adj = new HashMap<Integer, List<Integer>>();
int[] color = new int[n]; // 0 is white 1 is gray and 2 is black
while (q.size() > 0) {
int index = q.poll();
if (color[index] != 0) {
return false;
}
if (color[i] == 0) {
}
}
}
color[index] = 1;
}
for (int i = 0; i < color.length; i ++) {
if (color[i] == 0) {
return false;
}
}
return true;
}
private void init(HashMap<Integer, List<Integer>> adj, int[][] edges) {
for (int i = 0; i < edges.length; i ++) {
}