LC-1361 Medium LeetCode

1361. Validate Binary Tree Nodes

Tree Depth-First Search Breadth-First Search Union Find Graph Binary Tree

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 44% Topics: Tree, Depth-First Search, Breadth-First Search, Union Find, Graph, Binary Tree

View full problem on LeetCode

Reading material

Trees & Traversals 18 min Union–Find (DSU) 12 min Graphs 16 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

class Solution(object):
    def validateBinaryTreeNodes(self, n, leftChild, rightChild):
        """
        :type n: int
        :type leftChild: List[int]
        :type rightChild: List[int]
        :rtype: bool
        """
        roots = set(range(n)) - set(leftChild) - set(rightChild)
        if len(roots) != 1:
            return False
        root, = roots
        stk = [root]
        lookup = set([root])
        while stk:
            node = stk.pop()
            for c in (leftChild[node], rightChild[node]):
                if c < 0:
                    continue
                if c in lookup:
                    return False
                lookup.add(c)
                stk.append(c)
        return len(lookup) == n

Solution from kamyu104/LeetCode-Solutions · MIT