Leetcode Graph Valid Tree

Steps to verify if a graph is a tree.

i. check the connectivity by verifying if # of edges is equal to # of nodes - 1

ii. start from root, we can visit all nodes in the graph, so the # of visited nodes equals to n

First, build the undirected tree, then do the BFS on the tree to check if condition ii meets.

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (n-1 != edges.length) {
            return false;
        }
        
        // construct the undirected tree using a hasmap which key is the label and value is the neighbor
        HashMap<Integer, HashSet<Integer>> graph = constructGraph(n, edges);
        
        // do the BFS on the graph using a count to indicate the # of visited nodes
        // note the root of the tree 0
        int count = 0;
        Queue<Integer> queue = new LinkedList<>();
        HashSet<Integer> set = new HashSet<>();         // need a set b/c its a undirected graph
        queue.offer(0);
        set.add(0);
        
        while (!queue.isEmpty()) {
            count++;
            Integer node = queue.poll();
            for (Integer neighbor : graph.get(node)) {
                if (set.add(neighbor)) {
                    queue.offer(neighbor);
                }
            }
        }
        
        return (count == n);
    }
    
    private static HashMap<Integer, HashSet<Integer>> constructGraph(int n, int[][] edges) {
        HashMap<Integer, HashSet<Integer>> graph = new HashMap<>();
        
        // put all nodes into the graph first
        for (int i=0; i<n; i++) {
            graph.put(i, new HashSet<Integer>());
        }
        
        // fill out all neighbors for each node
        for (int i=0; i<edges.length; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        
        return graph;
    }
}