1
var validateBinaryTreeNodes = function (n, leftChild, rightChild) {
2
  // find in-degree for each node
3
  const inDeg = new Array(n).fill(0);
4
  for (let i = 0; i < n; ++i) {
5
    if (leftChild[i] !== -1) {
6
      ++inDeg[leftChild[i]];
7
    }
8
    if (rightChild[i] !== -1) {
9
      ++inDeg[rightChild[i]];
10
    }
11
  }
12
  // find the root node and check each node has only one in-degree
13
  let rootNodeId = -1;
14
  for (let i = 0; i < n; ++i) {
15
    if (inDeg[i] === 0) {
16
      rootNodeId = i;
17
    } else if (inDeg[i] > 1) {
18
      return false;
19
    }
20
  }
21
  // if no root node found -> invalid BT
22
  if (rootNodeId === -1) {
23
    return false;
24
  }
25
  // BFS to check that each node is visited at least and at most once
26
  const visited = new Set();
27
  const queue = [rootNodeId];
28

29
  while (queue.length) {
30
    const nodeId = queue.shift();
31

32
    if (visited.has(nodeId)) {
33
      return false;
34
    }
35
    visited.add(nodeId);
36

37
    const leftNode = leftChild[nodeId],
38
      rightNode = rightChild[nodeId];
39
    if (leftNode !== -1) {
40
      queue.push(leftNode);
41
    }
42
    if (rightNode !== -1) {
43
      queue.push(rightNode);
44
    }
45
  }
46
  // checking each node is visited at least once
47
  return visited.size === n;
48
};