Embedded Copy
EasyTrees
Problem
Given the roots of two binary trees, root and pattern, decide whether root contains a node whose entire subtree (that node and all its descendants) is identical to pattern in shape and values.
A tree counts as a subtree of itself.
Example 1
- Input:
- root = [3, 4, 5, 1, 2], pattern = [4, 1, 2]
- Output:
- true
The subtree rooted at the 4 is exactly [4, 1, 2].
Example 2
- Input:
- root = [3, 4, 5, 1, 2, null, null, null, null, 0], pattern = [4, 1, 2]
- Output:
- false
The 4 subtree has an extra 0 under the 2, so it is not an exact copy.
Constraints
- 1 ≤ nodes in root ≤ 2000
- 1 ≤ nodes in pattern ≤ 1000
- Tree heights ≤ 500
- -10^4 ≤ node.val ≤ 10^4
Hint
Show the first hint
If you knew how to test two trees for equality, how would you use it here?
Walkthrough
How to approach it
01Clarify before coding
- Does 'subtree' mean the full set of descendants? Yes: the candidate cannot have extra nodes below, which is why example 2 is false.
- Can values repeat? Yes, so several starting points may need checking.
- Is pattern ever empty? No, it has at least one node.
02Brute force
Serialize every subtree of root to a string and compare each to the serialization of pattern.
Cost: O(n²) time and memory in the worst case, because subtree strings overlap heavily.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.