Subtree of Another Tree

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 = [1,2,3,4,5], subRoot = [2,4,5]


Output: true

Example 2:

Input: root = [1,2,3,4,5,null,null,6], subRoot = [2,4,5]


Output: false

Constraints:

  • 0 <= The number of nodes in both trees <= 100.
  • -100 <= root.val, subRoot.val <= 100

You should aim for a solution as good or better than O(m * n) time and O(m + n) space, where n and m are the number of nodes in root and subRoot, respectively.

You should aim for a solution as good or better than O(m * n) time and O(m + n) space, where n and m are the number of nodes in root and subRoot, respectively.

Hint 1

A subtree of a tree is a tree rooted at a specific node. We need to check whether the given subRoot is identical to any of the subtrees of root. Can you think of a recursive way to check this? Maybe you can leverage the idea of solving a problem where two trees are given, and you need to check whether they are identical in structure and values.

Hint 2

When two trees are identical, it means that every node in both trees has the same value and structure. We can use the Depth First Search (DFS) algorithm to solve the problem. How do you implement this?

Hint 3

We traverse the given root, and at each node, we check if the subtree rooted at that node is identical to the given subRoot. We use a helper function, sameTree(root1, root2), to determine whether the two trees passed to it are identical in both structure and values.

Solution

Depth First Search (DFS)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right


def is_subtree(root: Optional[TreeNode], sub_root: Optional[TreeNode]) -> bool:
    if not sub_root:
        return True
    if not root:
        return False


    if same_tree(root, sub_root):
        return True
    return (is_subtree(root.left, sub_root) or
            is_subtree(root.right, sub_root))




def same_tree(root: Optional[TreeNode], sub_root: Optional[TreeNode]) -> bool:
    if not root and not sub_root:
        return True
    if root and sub_root and root.val == sub_root.val:
        return (same_tree(root.left, sub_root.left) and
                same_tree(root.right, sub_root.right))
    return False

Time complexity: O(m * n) Space complexity: O(m + n)

Serialization And Pattern Matching

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right


def serialize(root: Optional[TreeNode]) -> str:
    if root is None:
        return "$#"


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




def z_function(s: str) -> list:
    z = [0] * len(s)
    left, right, n = 0, 0, len(s)
    for i in range(1, n):
        if i <= right:
            z[i] = min(right - i + 1, z[i - left])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] - 1 > right:
            left, right = i, i + z[i] - 1
    return z




def is_subtree(root: Optional[TreeNode], sub_root: Optional[TreeNode]) -> bool:
    serialized_root = serialize(root)
    serialized_sub_root = serialize(sub_root)
    combined = serialized_sub_root + "|" + serialized_root


    z_values = z_function(combined)
    sub_len = len(serialized_sub_root)


    for i in range(sub_len + 1, len(combined)):
        if z_values[i] == sub_len:
            return True
    return False

Time complexity: O(m + n) Space complexity: O(m + n)