# Leetcode 1275 Solution

This article provides solution to leetcode question 1275 (validate-binary-tree-nodes)

https://leetcode.com/problems/validate-binary-tree-nodes

## Solution

``````class Solution {
public:
bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
std::map<int, std::vector<int>> in_map;
std::map<int, std::vector<int>> out_map;

for (int i = 0; i < n; i++)
{
int left_child_node = leftChild[i];
int right_child_node = rightChild[i];

if (left_child_node != -1)
{
in_map[left_child_node].push_back(i);
out_map[i].push_back(left_child_node);
}

if (right_child_node != -1)
{
in_map[right_child_node].push_back(i);
out_map[i].push_back(right_child_node);
}
}

int zero_in_degree_nodes = 0;
int root_node = -1;
for (int i = 0; i < n; i++)
{
int node_in_degree = in_map[i].size();

if (node_in_degree == 0)
{
zero_in_degree_nodes++;
root_node = i;
}

if (node_in_degree > 1)
return false;
}

if (zero_in_degree_nodes != 1)
return false;

std::queue<int> q;
q.push(root_node);
int connected_size = 0;

while (!q.empty())
{
int size = q.size();
for (int i = 0; i < size; i++)
{
int node = q.front();
q.pop();

connected_size++;

auto& out_nodes = out_map[node];
for (auto it = out_nodes.begin(); it != out_nodes.end(); it++)
q.push(*it);
}
}

return connected_size == n;
}
};
``````