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.
Recommended Time and Space Complexity
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)