Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Return true if subRoot appears as a complete subtree somewhere in root — meaning some node of root, together with ALL its descendants, exactly equals subRoot. The interview-grade answer reuses Same Tree: walk every node of root and run isSameTree(node, subRoot) there. That's O(m·n). The brag-worthy O(m+n) answer serializes both trees with null markers and runs KMP / substring search.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can compose two ideas — a per-node DFS search over the host tree and an exact-equality (Same Tree) check — and whether you understand 'subtree' means the full subtree including all descendants.
Where candidates slip
Matching only the values along a path (not requiring all descendants), stopping at the first node with the same value instead of trying all anchors, or serializing without delimiters so values like 1,2 collide with 12.
How to stand out
State the O(m·n) composition cleanly, define 'subtree' precisely, then offer the serialization + KMP O(m+n) solution and explain why null/delimiter markers are mandatory for correctness.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewDoes subRoot appear as a full subtree?Need optimal O(m+n)?NoYesExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Same-Tree at Every Node (Expected)
1Hint 1Explore hintHide hint
You already know how to check if two trees are identical (Same Tree). How could you use that to test whether subRoot sits at one specific node of root?
2Hint 2Explore hintHide hint
Anchor the comparison: for a given node of root, isSameTree(node, subRoot) tells you if subRoot matches starting exactly there.
3Hint 3Explore hintHide hint
Now search: try that check at the root, and if it fails, recurse into the left and right children with OR. Add base cases for null sub (true) and null root (false).
A · Core idea
This problem is a search wrapped around an equality test. The equality test is exactly Same Tree; the search visits every node of root and asks 'does subRoot match here?'.
The two-function structure. Keep isSameTree(a, b) from LeetCode 100 unchanged — it returns true iff the two trees are structurally identical with equal values. Then isSubtree(root, subRoot) walks root: if the current node anchors an exact match (isSameTree(root, subRoot) is true), return true; otherwise try the left subtree OR the right subtree.
Order and short-circuit. Check the current anchor first, then OR the two recursive searches. The || / or short-circuits, so the moment any anchor matches, the whole search stops — you never explore the rest of the tree.
The base cases that matter. If subRoot is null, it's vacuously a subtree of anything → true. If root is null but subRoot isn't, there's nowhere left to match → false. Getting these right keeps the recursion from dereferencing nulls.
Why you can't stop at the first value match. With duplicate values, many nodes of root may share subRoot's root value. Matching that one value proves nothing — you must run the full Same Tree check at each candidate, because the descendants might diverge. This is also why the 'all descendants' definition bites: in the false example, the 4-1-2 shape is present but node 2 has an extra child 0, so isSameTree correctly rejects that anchor.
The cost. In the worst case (e.g. root and subRoot are long identical-looking chains), each of the n anchors triggers an O(m) comparison → O(m·n). For the given constraints (n ≤ 2000, m ≤ 1000) that's ~2 million node comparisons — perfectly fast enough, which is why this is the expected solution despite not being asymptotically optimal.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [3,4,5,1,2], subRoot = [4,1,2]How to read it:root = [3,4,5,1,2]; the subtree rooted at 4 (with children 1,2) equals subRoot [4,1,2].
trueC · Code with teaching comments
Reference implementation preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the full codeHide the full code
D · Why it works and complexityO(m·n) timeO(h) spaceOpen the invariant and proofExplore the proofHide the proof
Recognize the problem as composition: 'search every node' (a DFS) × 'exact match here' (Same Tree). Most 'find pattern X anywhere in structure Y' problems decompose this way — a traversal that tries an exact-match helper at each position. Reusing Same Tree verbatim also signals you build on known primitives instead of reinventing them.
ComplexityO(m·n) time, O(h) space — There are n candidate anchor nodes in root. At each, isSameTree compares up to m nodes of subRoot → O(m) per anchor. Worst case O(m·n) time. The recursion stack is bounded by the height of root → O(h) space.
E · Edge cases and pitfalls6root = [1,1], subRoot = [1] — isSameTree fails at the root (root has a child, subRoot doesn't), but matches at the leaf 1 → true.Explore edge casesHide edge cases
Edge cases handled
root = [1,1], subRoot = [1]isSameTree fails at the root (root has a child, subRoot doesn't), but matches at the leaf 1 → true.root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]Anchor 4 fails isSameTree because node 2 has an extra child 0 → no match anywhere → false.root == subRoot (identical trees)isSameTree succeeds at the very first anchor → true (a tree is a subtree of itself).
Pitfalls
- Stopping at the first node whose value equals subRoot's root value — duplicates make value-equality insufficient.
- Matching only along a path instead of requiring all descendants — accepts the false example.
- Getting the base cases backwards (null root vs null subRoot) — flips correctness on empty inputs.
Approach 2 of 2 · Optimal
Serialize + KMP Substring Search (Optimal)
1Hint 1Explore hintHide hint
What if you flattened each tree into a string via a traversal? Then 'is subRoot a subtree' becomes 'is one string a substring of another'.
2Hint 2Explore hintHide hint
Serialize with a consistent traversal (preorder) AND include null markers, so the structure — not just the values — is encoded.
3Hint 3Explore hintHide hint
Naïve substring search is O(m·n) again; use KMP to find subRoot's serialization inside root's serialization in O(m+n). Add delimiters so values like 1 and 2 don't fuse into 12.
A · Core idea
Turn the tree problem into a string problem. If you serialize both trees into strings that faithfully encode structure, then 'is subRoot a subtree of root' becomes 'is subRoot's string a substring of root's string' — solvable in linear time with KMP.
Serialize with structure, not just values. Do a preorder walk emitting each value, and crucially emit an explicit marker for every null child (e.g. #). Without null markers, different trees can serialize to the same value sequence and you'd get false matches. Also wrap each value in delimiters (e.g. a leading ^ or comma): otherwise a node 12 and two nodes 1,2 could produce identical characters and collide. The combination of null sentinels + value delimiters makes the serialization a faithful, collision-free encoding of the tree.
Why a naïve substring check isn't enough. Even with a correct serialization, text.contains(pattern) or a sliding-window compare is itself O(m·n) in the worst case — the same cost we're trying to beat. KMP fixes this: it preprocesses the pattern into a failure/LPS table in O(m), then scans the text once in O(n), never backtracking, for O(m + n) total.
The trade-off to state. This is asymptotically optimal but more code and more bug surface (the markers are easy to get subtly wrong). For the given constraints the O(m·n) solution already passes comfortably, so present KMP as the 'if you need it to scale' answer rather than the default. Mentioning it — and why the markers matter — is usually enough to land the bonus points without writing the entire KMP table on the whiteboard.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [1,2,3], subRoot = [2] (preorder with # for null, ^ delimiter)Interactive diagram
Picking the right approach
serialize rootThe Same-Tree-at-every-node composition is the expected O(m·n); serialize + KMP is the O(m+n) flex.
trueC · Code with teaching comments
D · Why it works and complexityO(m + n) timeO(m + n) spaceOpen the invariant and proofExplore the proofHide the proof
Reducing a tree-matching question to a string-matching question is a powerful reframing, but it lives or dies on the serialization being unambiguous. Null sentinels encode shape; delimiters prevent value runs from merging. Skip either and the reduction is silently wrong — which is exactly the subtlety interviewers probe.
ComplexityO(m + n) time, O(m + n) space — Serializing each tree is linear in its size: O(n) and O(m). KMP preprocesses the pattern in O(m) and scans the text in O(n), so the match is O(m + n). The serialized strings dominate space at O(m + n).
E · Edge cases and pitfalls6root value 12 vs subRoot values 1,2 — Without the '^' delimiter both serialize to '12...' and falsely match; with delimiters they differ ('^12' vs '^1^2') → correctly no match.Explore edge casesHide edge cases
Edge cases handled
root value 12 vs subRoot values 1,2Without the '^' delimiter both serialize to '12...' and falsely match; with delimiters they differ ('^12' vs '^1^2') → correctly no match.subRoot is a single leaf present in rootPattern '^v##' is found as a substring at that leaf's position → true.subRoot deeper than any region of rootPattern longer/mismatched → KMP scans without a full match → false.
Pitfalls
- Omitting null markers — distinct trees serialize to the same string, producing false positives.
- Omitting value delimiters — multi-digit or adjacent values collide (1,2 vs 12).
- Using naïve String.contains — that's O(m·n) again, defeating the purpose; you must use KMP (or Z-algorithm) for O(m+n).
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic boolean isSubtree(TreeNode root, TreeNode subRoot) { String text = serialize(root); String pattern = serialize(subRoot); return kmpContains(text, pattern); }Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Treating containment as path/value match
Subtree requires ALL descendants to match. Checking only that subRoot's values appear along some path accepts the false case where the matched region has extra children.
Explore the code comparisonHide the code comparison
Treating containment as path/value match
Subtree requires ALL descendants to match. Checking only that subRoot's values appear along some path accepts the false case where the matched region has extra children.
Don't write this
def isSubtree(self, root, subRoot):
if not root:
return False
if root.val == subRoot.val: # value-only match — WRONG
return True
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)Write this instead
def isSubtree(self, root, subRoot):
if not subRoot:
return True
if not root:
return False
if self.isSameTree(root, subRoot): # full exact-subtree match
return True
return (self.isSubtree(root.left, subRoot)
or self.isSubtree(root.right, subRoot))2Serialization without markers
Without null sentinels, trees of different shapes serialize to the same value sequence; without delimiters, adjacent values fuse. Both cause false subtree matches.
Explore the code comparisonHide the code comparison
Serialization without markers
Without null sentinels, trees of different shapes serialize to the same value sequence; without delimiters, adjacent values fuse. Both cause false subtree matches.
Don't write this
private void build(TreeNode node, StringBuilder sb) {
if (node == null) return; // no null marker
sb.append(node.val); // no delimiter: 1,2 -> "12"
build(node.left, sb);
build(node.right, sb);
}Write this instead
private void build(TreeNode node, StringBuilder sb) {
if (node == null) { sb.append('#'); return; } // structure preserved
sb.append('^').append(node.val); // values can't fuse
build(node.left, sb);
build(node.right, sb);
}Revise
Carry the pattern into the interview
Pattern to remember
sameTree equality check anchored at every node of the host tree
Code pattern to memorize
isSubtree(root, sub):
if sub is null: return True
if root is null: return False
if isSame(root, sub): return True
return isSubtree(root.left, sub) or isSubtree(root.right, sub)Rules to remember
- 1A subtree must include all descendants — a partial match (subRoot's shape buried but with extra children below) does NOT count.
- 2Reuse Same Tree as the helper; try it anchored at every node of
root. - 3Try the current node first, then OR the left and right recursions — short-circuit on the first hit.
- 4Empty
subRootis trivially a subtree of anything (return true); emptyrootwith non-emptysubis false. - 5For O(m+n), serialize with null sentinels and delimiters then run KMP — and use markers so 1,2 vs 12 can't collide.
Use this pattern when
- You must find whether one tree appears verbatim (with all descendants) inside another
- Any 'does pattern X occur anywhere in structure Y?' where X must match exactly
- Combining a per-node scan with an exact-match helper (search × compare)
Choose another pattern when
- Partial / value-only containment is allowed → this exact-match approach is too strict
- Both trees are BSTs → ordering can prune the search faster than scanning every node
- You only need structural similarity, not equality → relax the helper
Interview takeaway
Subtree of Another Tree is Same Tree wrapped in a search: at every node of the big tree, ask 'is the small tree exactly here?'. The naïve O(m·n) is the expected answer; knowing the serialize-plus-KMP route to O(m+n) — with proper null and delimiter markers — is the standout.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternComposition of a per-node DFS search with an exact-match helper (Same Tree). 'Find pattern X anywhere in structure Y' decomposes into 'traverse every position' × 'exact match here'. The optimal twist — serialize to strings and run KMP — recurs whenever a structural-matching problem can be flattened into substring search.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Same TreeThe exact-equality helper this problem calls at every anchor node.
- Find the Index of the First Occurrence in a StringComing soonThe pure string-matching core (KMP) behind the O(m+n) serialization approach.
- Linked List in Binary TreeComing soonSame 'match a pattern anchored at every node' idea, but the pattern is a downward path, not a full subtree.
- Serialize and Deserialize Binary TreeComing soonThe serialization technique (with null markers) generalized into a full codec.