# 1361. Validate Binary Tree Nodes
from collections import defaultdict
"""
you have n binary trees nodes numbered from 0 to n - 1 where node i has two
children left_child and right_child. return true if any only if all the given
nodes from exactly one valid binary tree. if node i has no left children,
then left_child[i] will equal -1. note that the nodes have no values and that
we only use the node numbers in this problem.
"""
class Solution:
def validateBinaryTreeNodes(self, n, left_child, right_child):
graph = defaultdict(list)
in_degree = [0] * n
for node in range(n):
left, right = left_child[node], right_child[node]
if left != -1:
graph[node].append(left)
in_degree[left] += 1
if right != -1:
graph[node].append(right)
in_degree[right] += 1
root_candidates = [node for node in range(n) if in_degree[node] == 0]
if len(root_candidates) != 1:
return False
root = root_candidates[0]
queue = [root]
seen = set([root])
while queue:
node = queue.pop(0)
if node in graph:
for child in graph[node]:
if child in seen:
return False
seen.add(child)
queue.append(child)
return len(seen) == n
if __name__ == "__main__":
obj = Solution()
print(
obj.validateBinaryTreeNodes(
n=4, left_child=[1, -1, 3, -1], right_child=[2, -1, -1, -1]
)
) # expect: True
print(
obj.validateBinaryTreeNodes(
n=4, left_child=[1, -1, 3, -1], right_child=[2, 3, -1, -1]
)
) # expect: False
print(
obj.validateBinaryTreeNodes(n=2, left_child=[1, 0], right_child=[-1, -1])
) # expect: True
