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

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 Recursive Depth First Search Algorithm (Determine a Binary Tree)

A tree should be a connected component, with no cycles and one root. A tree is a DAG (Directed Acyclic Graph). The root is a node with zero indegree (no incoming edges), then we can start a Depth First Search (usually implemented in Recursion or via stack). We want to find out if all the nodes can be visited once from the root.

In order to compute the indegree of each node from 0 to n-1, we use a dictionary and iterate over the left/right array (edges). Then we find out the root nodes – which should be one for a valid tree.

The purpose of traversing the graph from root is to find out if we can reach all other nodes.

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

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()
        def dfs(root):
            if root in seen:
                return False
            seen.add(root)
            if left[root] != -1:
                if not dfs(left[root]):
                    return False
            if right[root] != -1:
                if not dfs(right[root]):
                    return False       
            return True 
        return dfs(root[0]) and 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()
        def dfs(root):
            if root in seen:
                return False
            seen.add(root)
            if left[root] != -1:
                if not dfs(left[root]):
                    return False
            if right[root] != -1:
                if not dfs(right[root]):
                    return False       
            return True 
        return dfs(root[0]) and len(seen) == n

The time complexity is O(N) or O(V+E) where N is the number of nodes, V is the number of vertices, and E is the number of edges (N=V). Space complexity is O(N) due to maximum N recursion depth.

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) —