Same Tree
Decide whether two binary trees have identical structure and values.
Why does this pattern fit?
Restate the exact job
Decide whether two binary trees have identical structure and values.
Both corresponding nodes must agree before their children can agree.
O(n) time · O(h) stack
Comparing traversals alone can lose structural information.
How to solve Same 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 two binary trees have identical structure and values.
Why Trees & recursive traversal fits
Both corresponding nodes must agree before their children can agree.
State to maintain
A pair of nodes.
Transition
Both null is true; one null/value mismatch is false; recurse on both child pairs.
Time and space
O(n) time · O(h) stack
Counterexample to the tempting mistake
Comparing traversals alone can lose structural information.
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.