Subtree of Another Tree: DFS + Same-Tree Matching
Solve Subtree of Another Tree with a clean DFS that runs a same-tree check at every node — intuition, JavaScript code, a worked walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
You already know how to check whether two binary trees are identical. Subtree of Another Tree asks a sharper question: is one tree hiding somewhere inside another? The trick is realizing you already have the core tool — you just have to run it at the right place.
The reframe is simple once you see it: a subtree match is nothing more than an identical-tree check anchored at the correct node. So walk every node of the big tree, and at each one, ask "does the tree rooted here look exactly like the target?" That turns an intimidating problem into two small recursions stacked on top of each other.
The problem
Given the roots of two binary trees root and subRoot, return true if there is a node in root such that the subtree rooted at that node is structurally identical to subRoot (same shape, same values). Otherwise return false.
"Subtree" here means the entire descendant tree of some node — not a partial fragment. If you pick a node, you take that node plus everything beneath it, all the way to the leaves.
Input: root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2]
Output: true
3 4 <- subRoot
/ \ / \
4 5 1 2
/ \
1 2 <- the subtree rooted here matches subRoot exactlyThe node with value 4 in root has left child 1 and right child 2 — an exact copy of subRoot. So the answer is true.
The brute force baseline
There is no shortcut around visiting nodes: any of them could be the anchor of a match. The honest baseline is to visit every node and, at each, compare the subtree there against subRoot node by node.
function isSubtree(root, subRoot) {
if (!root) return false;
// collect every node, then compare each subtree to subRoot
const stack = [root];
while (stack.length) {
const node = stack.pop();
if (identical(node, subRoot)) return true;
if (node.left) stack.push(node.left);
if (node.right) stack.push(node.right);
}
return false;
}This isn't actually "slow" in the wasteful sense — it's the real algorithm. What people mean by brute force here is doing the same comparison badly: for example serializing every subtree into a string and running substring search, which is easy to get wrong (a naive contains gives false positives like 2 matching inside 12). The clean recursive version below is both simpler and correct, so we go straight to it.
The key insight
Two recursions, each with one job:
-
isSameTree(p, q)— the identical-tree check. Two trees are the same when both roots are null, or both are non-null with equal values and matching left subtrees and matching right subtrees. This is the classic Same Tree problem. -
isSubtree(root, subRoot)— the search. At each node, tryisSameTreeanchored here. If it matches, done. If not, recurse into the left and right children and try again from there.
The pattern name is DFS traversal with a per-node predicate. You're not inventing a new comparison — you're relocating a comparison you already own to every possible anchor point. Once you separate "where to try" from "how to compare," the code writes itself.
The optimal solution
This mirrors the exact algorithm the visualizer steps through — two mutually supporting recursions with the same structure:
function isSubtree(root, subRoot) {
if (!root) return false;
if (isSameTree(root, subRoot)) return true;
return isSubtree(root.left, subRoot)
|| isSubtree(root.right, subRoot);
}
function isSameTree(p, q) {
if (!p && !q) return true;
if (!p || !q) return false;
if (p.val !== q.val) return false;
return isSameTree(p.left, q.left)
&& isSameTree(p.right, q.right);
}Read isSubtree top to bottom. An empty root can't contain anything, so return false. Otherwise try an exact match right here; if it succeeds, return true immediately. If not, the answer is true iff subRoot lives somewhere in the left subtree or the right subtree — and the short-circuit || stops the moment either branch reports success.
isSameTree has three guard rails before it recurses: both null is a clean match, exactly one null is a structural mismatch, and unequal values are an immediate reject. Only when the current pair agrees does it descend into both children with &&, so any single disagreement collapses the whole check to false.
Walkthrough
Tracing root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2]. The isSubtree traversal visits nodes in pre-order; each row is one anchor attempt.
| Step | Anchor node | isSameTree(anchor, subRoot) | Detail | Result |
|---|---|---|---|---|
| 1 | 3 | fails at root | 3 !== 4, reject immediately | recurse left |
| 2 | 4 | compare 4 vs 4 | values equal → descend into children | continue |
| 3 | 4's left: 1 vs 1 | match | equal leaves, both children null → true | continue |
| 4 | 4's right: 2 vs 2 | match | equal leaves, both children null → true | match! |
| — | 4 | isSameTree returns true | full subtree at node 4 equals subRoot | return true |
Step 1 shows the fast reject: because 3 !== 4, isSameTree bails on the very first comparison without touching any children — cheap. The real work happens at node 4, where all three comparisons (4=4, 1=1, 2=2) succeed and every dangling child is null-vs-null. The instant node 4 returns true, the || chain propagates it up and node 5 is never even visited.
Complexity
Let m be the number of nodes in root and n the number in subRoot.
| Metric | Big-O | Why |
|---|---|---|
| Time | O(m · n) | each of the m anchors may run an isSameTree that walks up to n nodes |
| Space | O(m + n) | recursion stack depth, bounded by the height of each tree (up to O(m) and O(n) when skewed) |
O(m · n) is the worst case — think a long chain of identical values where every anchor's comparison runs far before failing. In practice the value guard (p.val !== q.val) rejects most anchors after one comparison, so typical runs are far closer to O(m + n). Space is the call-stack depth: balanced trees give O(log m + log n), degenerate ones give O(m + n).
Common mistakes
- Testing partial overlap instead of full identity. A subtree must match all the way down to the leaves. Node
4isn't a match ifsubRootwere[4, 1]— the missing right child2is a structural difference.isSameTree's "exactly one null → false" rule is what enforces this. - Forgetting the empty-
rootbase case. Recursing intonullchildren is normal, soisSubtreemust returnfalseon a null node rather than dereferencingroot.left. - Serializing and using naive substring search. Concatenating node values into a string and calling
indexOfgives false positives ("1,2"appearing inside"11,2") unless you insert null markers and delimiters. The recursive check sidesteps the whole trap. - Swapping
&&for||inisSameTree. A same-tree match needs both subtrees to agree;||would accept a tree that matches on only one side. Likewise,isSubtreeneeds||(found in either branch), not&&.
Where this pattern shows up next
The "DFS + per-node predicate" structure and its isSameTree engine power a whole cluster of tree problems:
- Same Tree — the identical-tree check that this solution reuses as its inner loop.
- Symmetric Tree — the same pairwise comparison, but mirrored left-against-right within one tree.
- Symmetric Tree - Iterative — the mirror check again, this time with an explicit queue instead of recursion.
- Subtree of Another Tree (Serialization) — the alternative that flattens both trees and searches strings, trading the O(m·n) worry for O(m + n) with correct delimiters.
You can also step through Subtree of Another Tree interactively to watch each anchor light up and the same-tree comparison walk node by node.
FAQ
What is the time complexity of Subtree of Another Tree?
The worst case is O(m · n), where m is the number of nodes in the main tree and n is the number in the target. Each of the m nodes can trigger a same-tree comparison that walks up to n nodes before failing. In practice the value check rejects most anchors after a single comparison, so real inputs run much closer to O(m + n).
How is this different from the Same Tree problem?
Same Tree asks whether two trees are identical from their roots. Subtree of Another Tree asks whether the target is identical to the subtree rooted at some node of the bigger tree. The solution literally reuses Same Tree as a helper — it just calls that check at every node during a DFS traversal instead of only at the top.
Why does the subtree have to reach all the way to the leaves?
A subtree is a node plus its entire set of descendants — you can't stop partway. That's why isSameTree returns false the moment one side has a node and the other has null. If matching stopped at a partial depth, a target like [4, 1] would wrongly match a node whose real subtree is [4, 1, 2], since the extra child 2 would be ignored.
Can I solve it faster than O(m · n)?
Yes. Serialize both trees into strings with explicit null markers and delimiters, then check whether subRoot's serialization is a substring of root's. With a linear-time substring algorithm like KMP, that runs in O(m + n). The catch is correctness: without careful markers you get false positives, so many people prefer the O(m · n) recursion for its simplicity in interviews.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.