You have n binary tree nodes numbered from 0 to n - 1 where node i has two children leftChild[i] and rightChild[i], return true if and only if all the given nodes form exactly one valid binary tree.

If node i has no left child then leftChild[i] will equal -1, similarly for the right child.

Note that the nodes have no values and that we only use the node numbers in this problem.

&nbsp;
Example 1:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true


Example 2:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
Output: false


Example 3:

Input: n = 2, leftChild = [1,0], rightChild = [-1,-1]
Output: false


&nbsp;
Constraints:


	n == leftChild.length == rightChild.length
	1 &lt;= n &lt;= 104
	-1 &lt;= leftChild[i], rightChild[i] &lt;= n - 1


 class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        
        left_set=set(leftChild)
        right_set=set(rightChild) 

        que=[]

        for i in range(n):
            if i not in left_set and i not in right_set:
                que.append(i)
        
        if len(que)>1 or len(que)==0:
            return False
        
        
        graph=defaultdict(list)

        for i in range(n):
            graph[i]=[]

            if leftChild[i]!=-1:
                graph[i].append(leftChild[i])

            if rightChild[i]!=-1:
                graph[i].append(rightChild[i])
        
        visited=set()
        visited.add(que[0])
        
        
        while len(que)>0:
            item=que.pop(0)
            

            children=graph[item]

            for child in children:
                if child not in visited:
                    que.append(child)
                    visited.add(child)
                else:
                    return False


        for i in range(n):
            if i not in visited:
                return False

        return True
import java.util.Arrays;

class Solution {
  static class UF {
    int[] parents;
    int size;
    UF(int n) {
      parents = new int[n];
      size = n;
      Arrays.fill(parents, -1);
    }
    
    int find(int x) {
      if (parents[x] == -1) {
        return x;
      }
      return parents[x] = find(parents[x]);
    }

    boolean union(int a, int b) {
      int pA = find(a), pB = find(b);
      if (pA == pB) {
        return false;
      }
      parents[pA] = pB;
      size--;
      return true;
    }

    boolean connected() {
      return size == 1;
    }
  }
  public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
    UF uf = new UF(n);
    int[] indeg = new int[n];
    for (int i = 0; i < n; i++) {
      int l = leftChild[i], r = rightChild[i];
      if (l != -1) {
        /**
         * i: parent node
         * l: left child node
         * if i and l are already connected or the in degree of l is already 1
         */
        if (!uf.union(i, l) || ++indeg[l] > 1) {
          return false;
        }
      }
      if (r != -1) {
        // Same thing for parent node and the right child node
        if (!uf.union(i, r) || ++indeg[r] > 1) {
          return false;
        }
      }
    }
    return uf.connected();
  }
}
class Solution {
public:
    int find_parent(vector<int>&parent,int x){
        if(parent[x]==x)
        return x;
        return parent[x]=find_parent(parent,parent[x]);
    }
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        vector<int> parent(n);
        for(int i=0;i<n;i++){
            parent[i]=i;
        }
        int cnt=0;
        for(int i=0;i<n;i++){
            int y=find_parent(parent,i);
            if(leftChild[i]!=-1){
                int x=find_parent(parent,leftChild[i]);
                if(x!=leftChild[i]||y==x)
                return false;
                parent[leftChild[i]]=y;
            }
            if(rightChild[i]!=-1){
                int x=find_parent(parent,rightChild[i]);
                if(x!=rightChild[i]||y==x)
                return false;
                parent[rightChild[i]]=y;
            }
        }
        int x=find_parent(parent,0);
        for(int i=1;i<n;i++){
            if(find_parent(parent,i)!=x)
            return false;
        }
        return true;
    }
};
var validateBinaryTreeNodes = function(n, leftChild, rightChild) {
	// find in-degree for each node
    const inDeg = new Array(n).fill(0);
    for(let i = 0; i < n; ++i) {
        if(leftChild[i] !== -1) {
            ++inDeg[leftChild[i]];    
        }
        if(rightChild[i] !== -1) {
            ++inDeg[rightChild[i]];
        }
    }
	// find the root node and check each node has only one in-degree
    let rootNodeId = -1;
    for(let i = 0; i < n; ++i) {
        if(inDeg[i] === 0) {
            rootNodeId = i;
        } else if(inDeg[i] > 1) {
            return false;
        }
    }
	// if no root node found -> invalid BT
    if(rootNodeId === -1) {
        return false;
    }
	// BFS to check that each node is visited at least and at most once
    const visited = new Set();
    const queue = [rootNodeId];
    
    while(queue.length) {
        const nodeId = queue.shift();
        
        if(visited.has(nodeId)) {
            return false;
        }
        visited.add(nodeId);
        
       const leftNode = leftChild[nodeId],
             rightNode = rightChild[nodeId];
        if(leftNode !== -1) {
            queue.push(leftNode);
        }
        if(rightNode !== -1) {
            queue.push(rightNode);
        }
    }
	// checking each node is visited at least once
    return visited.size === n;};
Validate Binary Tree Nodes