Solution 1 - Recursive DFS

For each node in the main tree, check if the subtree rooted at that node is identical to subRoot. Two trees are identical if their root values match and their left and right subtrees are also identical. Traverse the entire main tree recursively, returning True as soon as a match is found.

TimeComplexity: O(n \cdot m)

SpaceComplexity: O(n)

""" 0572.1 - Subtree of Another Tree - Solution 1 - Recursive DFS """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional


#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """Solution Class"""

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        """Subtree of Another Tree Function"""
        if not subRoot:
            return True
        if not root:
            return False
        if self.isSameTree(root, subRoot):
            return True
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        """Check if two trees are identical"""
        if not p and not q:
            return True
        if not p or not q:
            return False
        return (p.val == q.val
                and self.isSameTree(p.left, q.left)
                and self.isSameTree(p.right, q.right))


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Example 1: root = [3,4,5,1,2], subRoot = [4,1,2] -> True
    root1 = TreeNode(3, TreeNode(4, TreeNode(1), TreeNode(2)), TreeNode(5))
    sub1 = TreeNode(4, TreeNode(1), TreeNode(2))
    print(Solution().isSubtree(root1, sub1))  # True

    # Example 2: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] -> False
    root2 = TreeNode(3, TreeNode(4, TreeNode(1), TreeNode(2, TreeNode(0))), TreeNode(5))
    sub2 = TreeNode(4, TreeNode(1), TreeNode(2))
    print(Solution().isSubtree(root2, sub2))  # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - String Serialization

Serialize both trees into strings using preorder traversal with special markers for None nodes. Then check if the serialized subRoot string is a substring of the serialized root string. Delimiters ensure no false matches from partial node values.

TimeComplexity: O(n + m)

SpaceComplexity: O(n + m)

""" 0572.2 - Subtree of Another Tree - Solution 2 - String Serialization """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional


#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """Solution Class"""

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        """Subtree of Another Tree Function"""
        def serialize(node: Optional[TreeNode]) -> str:
            if not node:
                return "#"
            return f",{node.val},{serialize(node.left)},{serialize(node.right)}"

        return serialize(subRoot) in serialize(root)


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Example 1: root = [3,4,5,1,2], subRoot = [4,1,2] -> True
    root1 = TreeNode(3, TreeNode(4, TreeNode(1), TreeNode(2)), TreeNode(5))
    sub1 = TreeNode(4, TreeNode(1), TreeNode(2))
    print(Solution().isSubtree(root1, sub1))  # True

    # Example 2: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] -> False
    root2 = TreeNode(3, TreeNode(4, TreeNode(1), TreeNode(2, TreeNode(0))), TreeNode(5))
    sub2 = TreeNode(4, TreeNode(1), TreeNode(2))
    print(Solution().isSubtree(root2, sub2))  # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0572 - Subtree of Another Tree

Solution 1 - Recursive DFS

Solution 2 - String Serialization