37 / 75
Easy
Subtree of Another Tree
#37treedfsstring-matchinghash
Check if subRoot is identical to any subtree of root using isSameTree helper.
Example:
Input:
root=[3,4,5,1,2], subRoot=[4,1,2]Output:
trueCommon Mistakes:
- Confusing subtree with subset (must include all descendants)
- Not checking if current node matches before checking children
- Inefficient O(n*m) solution without considering optimizations
- Forgetting that subtree can be entire tree
Notes:
Time O(n*m) worst case. Can optimize to O(n+m) using tree serialization and KMP. Space O(h).
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Check if subRoot is identical to any subtree of root using isSameTree helper.
Example:
Input:
root=[3,4,5,1,2], subRoot=[4,1,2]Output:
trueCommon Mistakes:
- Confusing subtree with subset (must include all descendants)
- Not checking if current node matches before checking children
- Inefficient O(n*m) solution without considering optimizations
- Forgetting that subtree can be entire tree
Notes:
Time O(n*m) worst case. Can optimize to O(n+m) using tree serialization and KMP. Space O(h).
37/75
Subtree of Another Tree