Introduction

In this blog post, we will explore how to solve the LeetCode problem "572" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise. A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself. Example 1: Input: root = [3,4,5,1,2], subRoot = [4,1,2] Output: true Example 2: Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] Output: false Constraints: The number of nodes in the root tree is in the range [1, 2000]. The number of nodes in the subRoot tree is in the range [1, 1000]. -104 <= root.val <= 104 -104 <= subRoot.val <= 104

Explanation

• The core idea is to traverse the main tree (root) and check if any of its nodes can be the root of a subtree that is identical to subRoot.
  • A helper function is used to recursively compare two trees for structural and value equality.
  • The traversal stops as soon as a matching subtree is found, optimizing the search.

• Time Complexity: O(mn) where n is the number of nodes in root and m is the number of nodes in subRoot. In the worst case, we might visit every node in root and potentially compare it against subRoot. *Space Complexity: O(max(h1, h2)) where h1 and h2 are the heights of the two trees root and subRoot respectively, due to the recursive call stack. In the worst-case (skewed tree), this could be O(n) or O(m).

Code

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

def isSubtree(root: TreeNode, subRoot: TreeNode) -> bool:
    """
    Checks if subRoot is a subtree of root.

    Args:
        root: The root of the main binary tree.
        subRoot: The root of the subtree to search for.

    Returns:
        True if subRoot is a subtree of root, False otherwise.
    """

    def is_identical(node1: TreeNode, node2: TreeNode) -> bool:
        """
        Recursively checks if two trees are identical in structure and value.
        """
        if not node1 and not node2:
            return True
        if not node1 or not node2 or node1.val != node2.val:
            return False
        return is_identical(node1.left, node2.left) and is_identical(node1.right, node2.right)

    def traverse(node: TreeNode, sub_root: TreeNode) -> bool:
        """
        Traverses the main tree and checks for subtree equality.
        """
        if not node:
            return False

        if is_identical(node, sub_root):
            return True

        return traverse(node.left, sub_root) or traverse(node.right, sub_root)

    return traverse(root, subRoot)