This problem follows the Tree Matching pattern, commonly found in the Trees category. Recognizing this pattern is key to solving it efficiently in an interview setting.
At each node, check if it's identical to subRoot. Recurse on left and right.
Reuse the 'same tree' check at every node — it's O(m*n) but simple. For O(n), you can serialize both trees and use string matching.
def isSubtree(root, subRoot):
if not root: return false
if isSameTree(root, subRoot): return true
return isSubtree(root.left, subRoot) or isSubtree(root.right, subRoot)Practice Subtree of Another Tree and similar Trees problems with flashcards. Build pattern recognition through active recall.
Practice this problem