aboutsummaryrefslogtreecommitdiff
path: root/validate_bst_node.py
blob: 6312f7ab838047d22399e70edd2738591ae4c22f (plain)
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
# 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