420. Subtree of Another Tree
You receive two binary trees, root and subRoot. Decide whether root contains a node whose subtree — that node plus every one of its descendants — is identical to subRoot in both shape and values.
Return true if such a node exists, false otherwise.
The match must be exact: no extra children may hang anywhere below the matched node, and a tree always counts as a subtree of itself, so root being identical to subRoot also returns true.
Example 1:
Input: root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2]
Output: true
Explanation: The node 4 inside root has children 1 and 2 and nothing else below it — exactly the tree subRoot describes.
Example 2:
Input: root = [3, 4, 5, 1, 2, null, null, null, null, 0], subRoot = [4, 1, 2]
Output: false
Explanation: The node 4 still has children 1 and 2, but its grandchild 0 (hanging under 2) is part of 4's subtree too — so the subtree is bigger than subRoot and the match fails.
Constraints:
- 1 ≤ number of nodes in root ≤ 2000
- 1 ≤ number of nodes in subRoot ≤ 1000
- -10⁴ ≤ node values ≤ 10⁴
Hints:
Split the problem in two: (a) are two trees identical? and (b) does any node of root anchor an identical copy? Part (a) is a clean recursion — equal values, identical left subtrees, identical right subtrees, and two nulls match.
For part (b), try the identity check anchored at every node of root. Don't stop at the first node whose value equals subRoot's root — duplicated values mean a failed anchor higher up can still succeed deeper down.
For the O(n + m) version: serialize both trees in preorder with explicit null markers and a delimiter in front of each value, then the subtree question becomes a substring search.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2]
Expected output: true