LC 1361 [M] Validate Binary Tree Nodes - ALawliet/algorithms GitHub Wiki

detect a cycle/toposort with BFS

class Solution:
	def validateBinaryNodes(self, n, leftChild, rightChild):
		# find the root node, assume root is node(0) by default
		# a node without any parent would be a root node
		# note: if there are multiple root nodes => 2+ trees
		root = 0
		childrenNodes = set(leftChild + rightChild)
		for i in range(n):
			if i not in childrenNodes:
				root = i
		
		# keep track of visited nodes
		visited = set()
		# queue to keep track of in which order do we need to process nodes
		Q = deque([root])
		
		while Q:
			node = Q.popleft()
			if node in visited:
				return False
			
			# mark visited
			visited.add(node)
			
			# process node
			if leftChild[node] != -1:
				Q.append(leftChild[node])
			if rightChild[node] != -1:
				Q.append(rightChild[node])
				
		# number of visited nodes == given number of nodes
		# if len(visited) != n => some nodes are unreachable/multiple different trees
		return len(visited) == n

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        indegree = [0] * n

        for left, right in zip(leftChild, rightChild):
            if left != -1: indegree[left] += 1
            if right != -1: indegree[right] += 1
            if indegree[left] == 2 or indegree[right] == 2: return False # pointing to same node (2 parents)

        Q = deque(i for i, d in enumerate(indegree) if d == 0) # start with root

        if len(Q) == 2: return False # 2 roots

        while Q:
            node = Q.popleft()

            for child in leftChild[node], rightChild[node]:
                if child == -1: continue
                indegree[child] -= 1
                if indegree[child] == 0: Q.append(child)

        print(indegree)
        return sum(indegree) == 0