Teaching Kids Programming – Tree Detection Algorithm via Breadth First Search (Determine a Binary Tree)

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given two lists of integers left and right, both of them the same length and representing a directed graph. left[i] is the index of node i’s left child and right[i] is the index of node i’s right child. A null child is represented by -1. Return whether left and right represents a binary tree.

Constraints
n ≤ 100,000 where n is the length of left and right
Example 1
Input

1 2	left = [1, -1, 3, -1] right = [2, -1, -1, -1]

left = [1, -1, 3, -1]
right = [2, -1, -1, -1]

Output
True

Example 2
Input

1 2	left = [0] right = [0]

left = [0]
right = [0]

Output
False
Explanation
This is a circular node.

Hints:
Is Tree a DAG (Directed Acyclic Graph)?
Tree is not disjoint.
The trick here is to find the root of the tree!
DAG with an exactly single source, no node with in-degree > 1.
What about topological Sorting?

Tree Detection Algorithm via Breadth First Search (Determine a Binary Tree)

For a graph to be a tree, it has to satisfy that: only one root, one connected component, and no cycles.

We need to find the root – which has no incoming edges aka the indegree is zero. If there are more than 1 node or zero roots, it must not be a tree.

Then, we start with the root, and do a Breadth First Search or Depth First Search traversal, and all the nodes should be visited exactly once.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def solve(self, left, right):
        n = len(left)
        data = defaultdict(int)
        for i in range(n):
            if left[i] != -1:
                data[left[i]] += 1
            if right[i] != -1:
                data[right[i]] += 1
        root = [i for i in range(n) if data[i] == 0]
        if len(root) != 1:
            return False
        seen = set()
        q = deque([next(iter(root))])
        while q:
            cur = q.popleft()
            if cur in seen:
                return False
            seen.add(cur)
            if left[cur] != -1:
                q.append(left[cur])
            if right[cur] != -1:
                q.append(right[cur])
        return len(seen) == n

class Solution:
    def solve(self, left, right):
        n = len(left)
        data = defaultdict(int)
        for i in range(n):
            if left[i] != -1:
                data[left[i]] += 1
            if right[i] != -1:
                data[right[i]] += 1
        root = [i for i in range(n) if data[i] == 0]
        if len(root) != 1:
            return False
        seen = set()
        q = deque([next(iter(root))])
        while q:
            cur = q.popleft()
            if cur in seen:
                return False
            seen.add(cur)
            if left[cur] != -1:
                q.append(left[cur])
            if right[cur] != -1:
                q.append(right[cur])
        return len(seen) == n

The time complexity is O(N) where N is the number of the nodes in the Graph/Tree. The space complexity is O(N) as we need to use a dictionary to store the indegree, and also the deque to perform the BFS traversal. Alternatively, we can say the time/space complexity is O(V+E) where V is the vertices and E is the edges.

Tree Detection Algorithms

• Teaching Kids Programming – Tree Detection Algorithm via Breadth First Search (Determine a Binary Tree)
• Algorithms to Check if a Graph is a Valid Tree by Using Disjoint Set (Union Find) and Breadth First Search
• Teaching Kids Programming – Tree Detection via Depth First Search Algorithm (Determine a Binary Tree via Recursion)
• Teaching Kids Programming – Tree Detection via Union Find + Disjoint Set (Determine a Binary Tree)

–EOF (The Ultimate Computing & Technology Blog) —