March 24
Subtree of Another Tree
How to search for a real subtree by comparing shape and values, not just roots that seem to match.
Trees Intermediate 18 min TypeScript
Given two binary trees root and subRoot, return true if there is a node in root whose subtree is exactly equal to subRoot.
Equal here means:
- same values
- same structure
Example:
Input:
root = [3,4,5,1,2]
subRoot = [4,1,2]
Output:
true
What to notice before coding
- A matching root value does not guarantee the whole subtree matches.
- The problem asks for structural equality, not just "contains these values".
- At each node in the bigger tree, you decide whether to test full equality or keep searching.
Common mistakes
- comparing only the root value and ignoring children
- forgetting that `subRoot = null` should count as a valid subtree
Step 1 - Understand what "is a subtree" really asks for
A common reading is:
- "is there a node with the same value?"
That is not the question.
The real point is:
- starting from some node in
root - the whole structure must match
subRoot
Step 2 - Write a very direct baseline
One possible baseline is:
- serialize
subRoot - serialize every subtree of
root - compare the strings
It works if you include null markers.
But it repeats too much serialization work.
Step 3 - Split the two questions
At any node in root, there are really two different questions:
- is this tree exactly equal to
subRoot? - if not here, is the answer on the left or on the right?
Once you separate those, the recursion gets clean.
Step 4 - Create a structural equality helper
The equality function must check:
- both
nullat the same time - current value
- left with left
- right with right
After that, the main search only needs to try that comparison at each candidate.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function isSubtree(root, subRoot) {
// root and subRoot are objects like { val: number, left: ..., right: ... } or null
// your solution here
return false
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n * m)
Space: O(h)
Solution 1 - Serialize every candidate and compare
Good baseline because it makes the structure requirement visible.
function serialize(node): string {
if (node === null) {
return "#"
}
return `${node.val},${serialize(node.left)},${serialize(node.right)}`
}
export function isSubtree(root, subRoot) {
if (subRoot === null) {
return true
}
const target = serialize(subRoot)
const candidates: string[] = []
function collect(node) {
if (node === null) {
return
}
candidates.push(serialize(node))
collect(node.left)
collect(node.right)
}
collect(root)
return candidates.includes(target)
}It works.
But it reserializes many full subtrees for no good reason.
Solution 2 - Structural comparison plus recursion-based DFS search
Now each node in root only becomes a real candidate when the full comparison makes sense.
function isSameTree(a, b) {
if (a === null && b === null) {
return true
}
if (a === null || b === null) {
return false
}
return (
a.val === b.val &&
isSameTree(a.left, b.left) &&
isSameTree(a.right, b.right)
)
}
export function isSubtree(root, subRoot) {
if (subRoot === null) {
return true
}
if (root === null) {
return false
}
if (isSameTree(root, subRoot)) {
return true
}
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot)
}The strong insight here is that the search is about candidates, but confirmation is always structural.
What to say in the interview
A strong short explanation would be:
I split the problem into two functions.
isSameTreeanswers whether two trees are exactly equal in values and structure.isSubtreewalks through the bigger tree looking for a place where that full comparison passes. That avoids treating a matching value as if it already proved the subtree.
That shows that you:
- understood the difference between a local value match and structural equality
- decomposed the problem into two clear responsibilities
- explained the recursion without overdoing it
When this pattern shows up again
This pattern comes back when you need to:
- compare recursive structures
- distinguish a local candidate from a global confirmation
- use a helper for tree or list equality
- recognize when “looks similar” still proves nothing
The point is not memorizing
isSubtree.
The point is learning how to separate search from structural confirmation.