# Concise JAVA solution based on DFS

• Solution1. Backtracking

The basic idea is to use DFS to check if the current node was already included in the traveling path. In this case, we need to convert graph presentation from edge list to adjacency list first, and then check if there's cycle existing in any subset. Because tree is a connected graph, we can start from any node.

As the following:

``````public boolean validTree(int n, int[][] edges) {
if (edges.length != 0) {
HashMap<Integer, HashSet<Integer>> neighbors = new HashMap<Integer, HashSet<Integer>>(); // Neighbors of each node
HashSet<Integer>curPath = new HashSet<Integer>(); // Nodes on the current path
for (int i = 0; i < edges.length; i++) {// Convert graph presentation from edge list to adjacency list
if (!neighbors.containsKey(edges[i][0])) neighbors.put(edges[i][0], new HashSet<Integer>());
if (!neighbors.containsKey(edges[i][1])) neighbors.put(edges[i][1], new HashSet<Integer>());
}
if (hasCycle(neighbors, edges[0][0], -1, curPath))// Use DFS method to check if there's cycle in any curPath
return false;
}
return edges.length == n - 1;
}

boolean hasCycle(HashMap<Integer, HashSet<Integer>> neighbors, int kid, int parent, HashSet<Integer>curPath) {
if (curPath.contains(kid)) return true;// The current node is already in the set of the current path

for (Integer neighbor : neighbors.get(kid))
if (neighbor != parent && hasCycle(neighbors, neighbor, kid, curPath))// DFS
return true;
curPath.remove(kid);
return false;
}
``````

Solution2. Union Find
Union Find is 1-Dimension memorized DFS(): travel from every node to leaf, if the leaf equals any node on the path, then there's cycle

`````` public boolean validTree(int n, int[][] edges) {
int[] leaves = new int[n];// leaves[i]: i's leaf
Arrays.fill(leaves, -1);

for (int i = 0; i < edges.length; i++) {
int src = findLeaf(leaves, edges[i][0]);
int dst = findLeaf(leaves, edges[i][1]);

if (src == dst)
return false;

//Union: Merge two sets which doesn't overlap
leaves[src] = dst;
}
return edges.length == n - 1;
}

//find i's leaf
int findLeaf(int leaves[], int i) {
if (leaves[i] == -1) return i; //-1 means reach the leaf
return findLeaf(leaves, leaves[i]);
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.