Valid Tree

Given a list of TreeNode, find if they can form one valid tree.

Note:

Empty tree is a valid tree.

Solution: HashSet

class Solution:
    def valid_tree(self, nodes):
        """
        :type nodes: List[TreeNode]
        :rtype: bool
        """
        roots = self.find_roots(nodes)
        if len(roots) == 1:
            return self.is_valid(roots.pop())
        return False

    def find_roots(self, nodes):
        roots = set(nodes)
        visited = set()

        def remove(root):
            if not root or root in visited:
                return
            visited.add(root)
            roots.discard(root)
            remove(root.left)
            remove(root.right)

        for node in nodes:
            remove(node.left)
            remove(node.right)

        return roots

    def is_valid(self, root):
        visited = set()

        def valid(node):
            if not node:
                return True
            if node in visited:
                return False
            visited.add(node)
            return valid(node.left) and valid(node.right)

        return valid(root)

Lessons:

• Root is the node with zero incoming edges.
• Use visited when find root, to avoid infinite loop when traverse a invalid tree.
• Remove all children nodes from given roots during traverse.
• Although find_root and valid_tree are very similar, it's hard to merge these two functions into one. For example, if we have a tree as below:

         A
        / \
       B   C
        \ /
         D
  nodes = [D, B, C, A]
  

  B, C and D are valid trees. We have to traverse the whole tree to find if A is valid.