261. Graph Valid Tree
Tags: leetcode
Published: 2023-05-31 19:53:06

Problem is here: [Graph Valid Tree](https://leetcode.com/problems/graph-valid-tree/description/)
<br/>
Before entering the problem solving process, we need to consider some important facts about the tree:
1. A tree with n nodes must have exactly `n - 1` edges
2. There is no cycle in the tree
3. The whole tree has to be a complete connected graph (there is always a path to go from a node `a` to node `b`)

<br/>
One more important thing is that we will utilize the concept used in Kahn's algorithm to solve this. By calculating the degrees of the nodes, we can eventually remove the nodes while maintaining the shape and checking the cycle in the graph.

So if there is a cycle in the tree, at some point, the node with the lowest degree will have the value larger than 1.

#### So here is the algorithm:
Algorithm:
- Go through the edges in the tree, increase the degree of the node
- Keep track a map of adjacent nodes to a specific nodes 
- Find the node with the smallest degree, if that node does not have a degree <= 1, return false since there is a cycle 
    - else: for each adjacent node to that node, decrease the degree of that adjacent node by 1
    - repeat the process untill all node has a degree of 0 and are all visited
- how to keep track of a set of node? store the nodes in set and see if which one can be considered


<strong>here is the code</strong>
```java
class Solution {
    public boolean validTree(int n, int[][] edges) {
        int[] degree = new int[n];
        Set<Integer> notVisited = new HashSet<>();
        Map<Integer, Set<Integer>> map = new HashMap<>();

        if (edges.length < n - 1) {
            return false;
        }

        for (int[] edge: edges) {
            int node1 = edge[0];
            int node2 = edge[1];
            degree[node1] ++;
            degree[node2]++;

            notVisited.add(node1);
            notVisited.add(node2);

            // add to the map 
            map.putIfAbsent(node1, new HashSet<>());
            map.putIfAbsent(node2, new HashSet<>());

            map.get(node1).add(node2);
            map.get(node2).add(node1);

            // union find and make sure they all have the same parents?
        }
        // System.out.println(Arrays.toString(degree));

        while (!notVisited.isEmpty()) {
            // find the node with the lowest degree 
            int nodeLowestDegree = Integer.MAX_VALUE;

            for (int node: notVisited) {
                if (nodeLowestDegree == Integer.MAX_VALUE) {
                    nodeLowestDegree = node;
                } else {
                    if (degree[node] < degree[nodeLowestDegree]) {
                        nodeLowestDegree = node;
                    }
                }
            }

            if (degree[nodeLowestDegree] > 1 || (degree[nodeLowestDegree] == 0 && notVisited.size() > 1)) {
                return false;
            }

            // remove it and adjust the adjacent nodes' degree
            notVisited.remove(nodeLowestDegree);
            
            // update adjacent nodes 
            for (int adjNode: map.get(nodeLowestDegree)) {
                degree[adjNode] --;
            }
        }

        return true;
    }
}
```