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.

Additional information

• 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].
• -10^4 <= root.val <= 10^4
• -10^4 <= subRoot.val <= 10^4

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

Explanation: The subRoot matches the 4 -> 1, 2 structure, but in root, the 2 node has an extra child 0.

Recursive Depth-First Search (Standard)

Intuition

To find if subRoot is a subtree of root, we can treat every single node in root as a potential starting point.
We can reuse the logic from the "Same Tree" problem: we write a helper function is_same_tree to check if two trees are identical. Then, we recursively traverse root. At each node, we check if the tree starting there is identical to subRoot.

Algorithm

1. Helper Function: Create is_same_tree(p, q) that returns True if tree p and tree q are identical.
2. Base Cases for Main Function:

• If subRoot is None, it is always a subtree of any tree. Return True.
• If root is None (but subRoot is not), we can't find a match. Return False.

3. Check Match: If is_same_tree(root, subRoot) returns True, we found our subtree. Return True.
4. Recurse: Otherwise, recursively check the left and right subtrees: return is_subtree(root.left, subRoot) OR is_subtree(root.right, subRoot).

def is_subtree(root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
    if not subRoot:
        return True
    if not root:
        return False
        
    if is_same_tree(root, subRoot):
        return True
        
    return is_subtree(root.left, subRoot) or is_subtree(root.right, subRoot)

def is_same_tree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    if not p and not q:
        return True
    if not p or not q or p.val != q.val:
        return False
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

Time & Space Complexity

• Time complexity: O(M * N)

• Reason: Let M be the number of nodes in root and N be the number of nodes in subRoot. In the worst case, we might call is_same_tree (which takes O(N) time) for every node in root.

• Space complexity: O(H_m)

• Reason: The space complexity is determined by the recursion stack of is_subtree, which goes as deep as the height of the root tree, H_m.

Preorder Serialization (Optimal String Matching)

Intuition

We can convert both trees into strings using a Preorder Traversal. If we include special markers for Null nodes (e.g., ^) and wrap each value with boundaries (e.g., #val#), a tree's structure and values are uniquely represented by its string.
If subRoot is a subtree of root, then subRoot's serialized string will be a perfect substring of root's serialized string.

Algorithm

1. Write a helper function serialize(node) that performs a preorder traversal.
2. If a node is None, return "^".
3. Otherwise, return "#" + str(node.val) + "#" + serialize(node.left) + serialize(node.right).
   (Note: The # boundaries prevent false positives, e.g., tree [2] matching inside tree [12]).
4. Get root_str = serialize(root) and sub_str = serialize(subRoot).
5. Return True if sub_str is in root_str, else False.

def is_subtree(root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
    def serialize(node):
        if not node:
            return "^"
        return f"#{node.val}#{serialize(node.left)}{serialize(node.right)}"
        
    root_str = serialize(root)
    sub_str = serialize(subRoot)
    
    return sub_str in root_str

Time & Space Complexity

• Time complexity: O(M + N)

• Reason: Serializing both trees takes O(M + N). String matching in Python uses optimized algorithms (like Boyer-Moore/KMP implementations) which generally run in O(M + N) time.

• Space complexity: O(M + N)

• Reason: We store the serialized strings of both trees, which takes space proportional to the number of nodes.