1. Subtree of Another Tree (LeetCode)
Model answer
The task
Determine whether one binary tree occurs in another as a subtree: both the node values and the tree structure must match.
Key idea
Serialize each tree in preorder, recording a marker for every missing child. These markers preserve structure, so the smaller tree is a subtree exactly when its serialization appears contiguously in the larger tree’s serialization. Use KMP to search in linear time.
Approach
- Treat an empty candidate tree as a subtree.
- Serialize each tree in preorder, using
Noneto represent missing nodes. - Build the KMP prefix table for the candidate serialization.
- Scan the larger serialization with KMP and return whether the candidate is found.
class Solution:
def isSubtree(self, root, subRoot):
if subRoot is None:
return True
def serialize(node):
tokens = []
def visit(current):
if current is None:
tokens.append(None)
return
tokens.append(current.val)
visit(current.left)
visit(current.right)
visit(node)
return tokens
text = serialize(root)
pattern = serialize(subRoot)
# Build the KMP prefix table.
prefix = [0] * len(pattern)
matched = 0
for i in range(1, len(pattern)):
while matched and pattern[i] != pattern[matched]:
matched = prefix[matched - 1]
if pattern[i] == pattern[matched]:
matched += 1
prefix[i] = matched
# Search for the candidate serialization.
matched = 0
for token in text:
while matched and token != pattern[matched]:
matched = prefix[matched - 1]
if token == pattern[matched]:
matched += 1
if matched == len(pattern):
return True
return False
Complexity:
- Time: O(n + m), where
nandmare the numbers of nodes in the two trees. - Space: O(n + m) for the serialized tokens and KMP prefix table.
Common follow-ups
- Can this be done without serialization? Try matching the candidate at every node; the worst case is O(nm).
- What if many subtree queries use the same main tree? Cache a structural hash for each node, then verify matches to guard against collisions.
- How do you avoid recursion-depth issues on skewed trees? Serialize iteratively with an explicit stack.