1
import java.util.Arrays;
2

3
class Solution {
4
  static class UF {
5
    int[] parents;
6
    int size;
7

8
    UF(int n) {
9
      parents = new int[n];
10
      size = n;
11
      Arrays.fill(parents, -1);
12
    }
13

14
    int find(int x) {
15
      if (parents[x] == -1) {
16
        return x;
17
      }
18
      return parents[x] = find(parents[x]);
19
    }
20

21
    boolean union(int a, int b) {
22
      int pA = find(a), pB = find(b);
23
      if (pA == pB) {
24
        return false;
25
      }
26
      parents[pA] = pB;
27
      size--;
28
      return true;
29
    }
30

31
    boolean connected() {
32
      return size == 1;
33
    }
34
  }
35

36
  public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
37
    UF uf = new UF(n);
38
    int[] indeg = new int[n];
39
    for (int i = 0; i < n; i++) {
40
      int l = leftChild[i], r = rightChild[i];
41
      if (l != -1) {
42
        /**
43
         * i: parent node l: left child node if i and l are already connected or the in degree of l
44
         * is already 1
45
         */
46
        if (!uf.union(i, l) || ++indeg[l] > 1) {
47
          return false;
48
        }
49
      }
50
      if (r != -1) {
51
        // Same thing for parent node and the right child node
52
        if (!uf.union(i, r) || ++indeg[r] > 1) {
53
          return false;
54
        }
55
      }
56
    }
57
    return uf.connected();
58
  }
59
}