Grokking Newsletter 240

class Solution {
   List<List<Integer>> graph;
   int[] colors;
   public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
       graph = new ArrayList<>();
       colors = new int[n];
       int[] numParents = new int[n];

       // build graph
       for (int i = 0; i < n; i++) {
           graph.add(new ArrayList<>());
       }
       for (int i = 0; i < n; i++) {
           if (leftChild[i] != -1) {
               graph.get(i).add(leftChild[i]);
               graph.get(leftChild[i]).add(i);
               numParents[leftChild[i]]++;
           }
           if (rightChild[i] != -1) {
               graph.get(i).add(rightChild[i]);
               graph.get(rightChild[i]).add(i);
               numParents[rightChild[i]]++;
           }
       }

       // if there is a node with multiple parents, this is not a valid tree
       for (int i = 0; i < n; i++) {
           if (numParents[i] > 1) {
               return false;
           }
       }

       // check cycle
       hasCycleDfs(0);

       // there is unvisited node, the graph is not connected, it is not a valid tree
       for (int i = 0; i < n; i++) {
           if (colors[i] != 2) {
               return false;
           }
       }

       // graph is connected and has no cycle, it's a tree
       return true;
   }

   boolean hasCycleDfs(int at) {
       if (colors[at] != 0) {
           return colors[at] == 2;
       }

       colors[at] = 1;
       for (int to : graph.get(at)) {
           if (hasCycleDfs(to)) {
               return true;
           }
       }

       colors[at] = 2;

       return false;
   }
}