261. Graph Valid Tree

Problem is here: Graph Valid Tree

Before entering the problem solving process, we need to consider some important facts about the tree:

A tree with n nodes must have exactly n - 1 edges
There is no cycle in the tree
The whole tree has to be a complete connected graph (there is always a path to go from a node a to node b)

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

here is the code

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;
    }
}

Blog

261. Graph Valid Tree

truongductri01

So here is the algorithm:

Join Our Newsletter. No Spam, Only the good stuff.

Related