Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0572 - Subtree of Another Tree
    0572 - Subtree of Another Tree
    0572 - Subtree of Another Tree
    0572 - Subtree of Another Tree

    0572 - Subtree of Another Tree

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/subtree-of-another-tree/

    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⋅m)TimeComplexity: O(n \cdot m)TimeComplexity:O(n⋅m)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)

    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)TimeComplexity: O(n + m)TimeComplexity:O(n+m)
    SpaceComplexity:O(n+m)SpaceComplexity: O(n + m)SpaceComplexity:O(n+m)
    """ 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()

    """ 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()