Thinking process - BFS

When to label the node visited?

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        //list of sets
        List<HashSet<Integer>> nodeList = new ArrayList<>();

        for (int i = 0; i < n; ++i) nodeList.add(new HashSet<>());

        //build graph
        for (int i = 0; i < edges.length; ++i) {
            nodeList.get(edges[i][0]).add(edges[i][1]);
            nodeList.get(edges[i][1]).add(edges[i][0]);
        }

        //init queue
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n];
        queue.offer(0);
        visited[0] = true;

        //while queue is not empty
        while (!queue.isEmpty()) {
            Integer num = queue.poll();

            for (Integer neighbor : nodeList.get(num)) {
                if (visited[neighbor]) return false;
                visited[neighbor] = true;
                queue.offer(neighbor);
                nodeList.get(neighbor).remove(num);
            }
        }

        //check all visited
        for (int i = 0; i < visited.length; ++i) {
            if (!visited[i]) return false;
        }

        return true;
    }
}

DFS

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        //list of sets
        List<HashSet<Integer>> nodeList = new ArrayList<>();

        for (int i = 0; i < n; ++i) nodeList.add(new HashSet<>());

        //build graph
        for (int i = 0; i < edges.length; ++i) {
            nodeList.get(edges[i][0]).add(edges[i][1]);
            nodeList.get(edges[i][1]).add(edges[i][0]);
        }

        boolean[] visited = new boolean[n];

        if(!dfsHelper(visited, nodeList, 0)) return false;

        //check all visited
        for (int i = 0; i < visited.length; ++i) {
            if (!visited[i]) return false;
        }

        return true;
    }

    //return false, if visited
    //else return true
    private boolean dfsHelper(boolean[] visited, List<HashSet<Integer>> nodeList, int index) {
        if (visited[index]) return false;

        visited[index] = true;

        for (Integer neighbor : nodeList.get(index)) {
            nodeList.get(neighbor).remove(index);
            if (!dfsHelper(visited, nodeList, neighbor)) return false;
        }

        return true;
    }
}