Trees · LC #572
Subtree of Another Tree
Check if subRoot appears as a subtree anywhere in root. Combines DFS traversal of the host tree with the Same Tree check at each node - O(m*n) overall.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given the roots of two binary trees `root` and `subRoot`, return `true` if there is a subtree of `root` with the same structure and node values as `subRoot`, and `false` otherwise.
Sample I/O
Input: root=[3,4,5,1,2], subRoot=[4,1,2] Output: true Input: root=[3,4,5,1,2,null,null,null,null,0], subRoot=[4,1,2] Output: false (extra node 0 breaks the match)
Intuition
How to Think About It
Intuition
Recursion works as a two-level search: outer DFS explores every node in root; at each node, inner Same Tree check tests if the subtree rooted there matches subRoot. The two concerns are cleanly separated into two recursive functions.
Core Concept
Outer function `isSubtree(root, sub)`: null root → false; isSame(root, sub) → true; recurse left OR recurse right. Inner function `isSame(a, b)`: same as Same Tree - structural + value equality check.
When to use
Pattern matching within trees, finding repeated subtree structures, template matching in ASTs.
When NOT to use
When subRoot is much larger than root - impossible to match. For repeated queries, serialization-based (KMP or hashing) approaches give O(m+n).
Key Insights
What to Know Cold
- OR (not AND) in the outer recursion - only one matching position needed.
- Short-circuit: if isSame returns true, stop immediately.
- O(m*n) worst case: every node in root triggers full isSame traversal of subRoot.
- String serialization alternative: serialize both trees, check if sub-string - O(m+n) with KMP.
- Root null check must come before isSame call (isSame handles null internally but outer null → false).
2 examples
Worked Examples
Exact subtree match
root=[3,4,5,1,2], subRoot=[4,1,2] - node 4 in root has identical subtree.
isSubtree(3, [4,1,2]): isSame(3,[4,1,2])=false. Try left: isSubtree(4,[4,1,2]): isSame(4,[4,1,2])=true → return true.
function isSubtree(root: TreeNode|null, sub: TreeNode|null): boolean {
if (!root) return false;
if (isSame(root, sub)) return true;
return isSubtree(root.left, sub) || isSubtree(root.right, sub);
}
function isSame(a: TreeNode|null, b: TreeNode|null): boolean {
if (!a && !b) return true;
if (!a || !b || a.val !== b.val) return false;
return isSame(a.left, b.left) && isSame(a.right, b.right);
}Output: true
Demonstrates clean separation of "find location" vs "verify match" concerns.
Extra child breaks match
Same root but node 4 has extra child 0 - subRoot [4,1,2] does not match.
isSame(4,[4,1,2]): left matches (1=1), right: isSame(2,[2]) with extra child 0 under 2 → false.
Output: false
Subtree match requires exact structure - extra children invalidate match.