Problem statement

https://binarysearch.com/problems/Tree-Detection/

Solution

First, create graph, where we keep:

  1. G is oriented graph.
  2. E is total number of edges.
  3. in_deg are in-degrees of nodes.

We need to have the following conditions to have tree:

  1. We have root: node, with in_deg equal zero.
  2. From this root we can reach all nodes.
  3. Total number of edges is n - 1.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, L, R):
        n, E = len(L), 0
        G, in_deg = defaultdict(list), [0] * n
        for i in range(n):
            for ch in [L[i], R[i]]:
                if ch == -1: continue
                G[i] += [ch]
                in_deg[ch] += 1
                E += 1

        root = -1
        for x in range(n):
            if in_deg[x] == 0: root = x

        if root == -1: return False
        def dfs(node):
            visited[node] = 1
            for neib in G[node]:
                if visited[neib] == 0: dfs(neib)

        visited = [0]*n
        dfs(root)          
        return sum(visited) == n and E == n - 1