Subtree of Another Tree
Decide whether one tree occurs as an identical subtree of another.
Why does this pattern fit?
Restate the exact job
Decide whether one tree occurs as an identical subtree of another.
Every source node is a possible root; equality is a separate recursive question.
O(nm) worst-case time · O(h) stack
Checking only matching root values ignores structure.
How to solve Subtree of Another Tree
The goal is to solve this problem from the pattern, not to memorize a finished answer. Use this as a check after your own attempt.
What the question asks
Decide whether one tree occurs as an identical subtree of another.
Why Trees & recursive traversal fits
Every source node is a possible root; equality is a separate recursive question.
State to maintain
A traversal over source nodes plus a same-tree comparison.
Transition
At each node test equality, otherwise search left or right.
Time and space
O(nm) worst-case time · O(h) stack
Counterexample to the tempting mistake
Checking only matching root values ignores structure.
Prove it again tomorrow
Close this page. Rebuild the state and transition from memory, write a test that exposes the mistake above, then solve a fresh input without looking back. A same-day reread is practice, not proof of retention.