The problem
Given a big tree and a small tree, decide whether the big tree contains a node whose whole subtree is identical to the small tree.
Input: big = [3, 4, 5, 1, 2], small = [4, 1, 2] Output: true
Picture it
Picture holding a stencil shaped like the small tree. We place it on each node of the big tree in turn and check (using the Same Tree test) whether everything below matches the stencil exactly, all the way down to the leaves.
How to recognise it
- You get a big tree and a small tree and must decide whether the small one appears whole inside the big one.
- "Whole" means a node in the big tree plus everything below it matches the small tree exactly, down to the leaves. A matching fragment with extra children below does not count.
- It combines two smaller problems: visit every node of the big tree, and at each one test sameness (the Same Tree check).
- Up to 2,000 nodes in the big tree and 1,000 in the small one, so even n × m ≈ 2 × 10^6 steps is affordable.
Start with brute force
Write the small tree as a list of tokens with # for empty spots. Then, at every node of the big tree, write out that node's whole subtree the same way and compare the lists.
def ser(node, out):
if not node:
out.append("#")
else:
out.append(str(node.val))
ser(node.left, out)
ser(node.right, out)
return out
def is_subtree_brute(root, sub):
target = ser(sub, [])
def visit(node):
if not node:
return False
return ser(node, []) == target or visit(node.left) or visit(node.right)
return visit(root)
Each node is written out once for every ancestor, so time is O(n · h + m), where h is the big tree's height: about 2 × 10^6 tokens for a 2,000-node chain. The waste is that a whole subtree is written down even when its very first value already differs from the small tree's root.
From brute force to the idea
- Find the waste. Writing the subtree out cannot stop early; a direct comparison can.
- Reuse Same Tree.
is_same(a, b)walks both trees in step.if not a or not b: return a is bhandles the empty cases in one line: it isTrueonly when both areNone. - Try every starting point.
is_subtreevisits the big tree depth-first (DFS: follow one branch to the bottom before trying the next). At each node it asks whether the small tree fits there; if not, it tries the left subtree, then the right. - Stop at the first fit.
orshort-circuits, so the search ends as soon as one node matches.
This is the key idea: at every node of the big tree, run the Same Tree check; most checks fail on the first value, so the usual cost is far below the worst case.
An O(n + m) method exists: serialise both trees with empty markers and separators, then run a linear-time string search such as KMP (Knuth–Morris–Pratt). It is rarely needed at these sizes.
The key idea
For every node in the big tree, run isSameTree against the small tree. O(m × n) in the worst case.
Python solution
def is_subtree(root, sub):
if not root:
return False
if is_same(root, sub): # stencil fits?
return True
return (is_subtree(root.left, sub) or
is_subtree(root.right, sub))
def is_same(a, b):
if not a or not b:
return a is b # both empty?
return (a.val == b.val
and is_same(a.left, b.left)
and is_same(a.right, b.right))In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n · h + m): each subtree written out in full, once per ancestor | O(n): the token list for the largest subtree |
| DFS + Same Tree (shown code) | O(n · m) worst case: up to m steps at each of n nodes, usually much less | O(h): recursion depth of the big tree (plus the small tree's height) |
Edge cases
- Exact copy: the big tree itself equals the small tree, so the check at the root succeeds.
- Match with extra children below (big
[3, 4, 5, 1, 2, null, null, null, null, 0], small[4, 1, 2]):False, because node 2 has a child 0 in the big tree. - Small tree is a single leaf value (big
[1, 2, 3], small[2]):True. - Empty big tree:
False. - Empty small tree: the shown code returns
False, because a leaf'sNonechildren are never tested. LeetCode guarantees at least one node, so this does not arise there. - Repeated values: fine; every node is tried, not only the first one with a matching value.
Common mistakes
- Returning
Truewhen only one side is empty inis_same, which accepts a match that has extra nodes below. - Stopping at the first node whose value equals the small root, instead of also searching its children.
- Serialising without separators or empty markers: values 2 and 12 then share text ("12" contains "2"), and different shapes give the same string.
Return how many nodes of the big tree have a subtree identical to the small tree. For big [1, 1, 1] and small [1] the answer is 2 (the two leaves; the root has children). Describe your approach, then write it if you like.
Compare with our answer
Keep the same DFS with the same is_same check, but do not stop at the first match: add up the matches in both children.
def count_matches(root, sub):
if not root:
return 0
here = 1 if is_same(root, sub) else 0
return here + count_matches(root.left, sub) + count_matches(root.right, sub)
Time O(n · m) in the worst case, space O(h).
A strong answer mentions: replacing or with a sum so every node is visited, reusing is_same unchanged, and that the root does not count when it has extra children.
1. You must check whether a big folder tree contains an exact copy of a given small folder structure. Which approach fits best?
The copy can start at any node, and it must match in full, so try a Same Tree check at every node. Name sets ignore structure, the root alone is too narrow, and the first name match may be the wrong one.
2. Why is the shown solution usually much faster than its O(n · m) worst case?
The worst case needs many near-matches (for example, almost every value equal). With varied values, a comparison usually fails at the first node, costing O(1). No sorting or caching is involved.
3. A learner writes if not a or not b: return True in is_same. Which input now gets a wrong answer?
With the bug, a missing node on either side counts as a match, so the root 1 "matches" even though it has an extra child 2, and the answer is true. The other inputs never compare a node against an empty spot in a way that changes the result.
Score 60% or more and the lesson is marked complete.