Solutions

# DFS, check for every node if the tree rooted in it matches the subtree. Or serialize to string using pre-order with null markers and do string matching.
# trees

# DFS: O(n * m) time, O(n + m) space
def isSubtree(root: TreeNode, subRoot: TreeNode) -> bool:
    if root is None:
        return False
    elif isSameTree(root, subRoot):
        return True
    else:
        return isSubtree(root.left, subRoot) or \
            isSubtree(root.right, subRoot)

def isSameTree(root: TreeNode, subRoot: TreeNode) -> bool:
    if root is None and subRoot is None:
        return True
    elif root is None or subRoot is None:
        return False
    else:
        return root.val == subRoot.val \
            and isSameTree(root.left, subRoot.left) \
            and isSameTree(root.right, subRoot.right)


# Serialize the trees using the same traversal and check for substring match
# Can use KMP or z-function for string pattern matching
# O(n + m) time, O(n + m) space
def serialize(node: TreeNode):
    if node is None:
        return "$#"

    return "$" + str(node.val) + serialize(node.left) + serialize(node.right)

def isSubtree(root: TreeNode, subRoot: TreeNode) -> bool:
    serial_root = serialize(root)
    serial_subroot = serialize(subRoot)
    return serial_subroot in serial_root