Subtree of Another Tree
Given the roots of two binary trees root and subRoot, return true if there is a node in root whose subtree is structurally identical to subRoot, including matching values.
Intuition
The trap is checking only whether values match somewhere in the tree, or stopping the search the moment you find a node whose value equals subRoot's root value. A value match by itself proves nothing about structure -- the subtree rooted there could easily branch differently or have different values further down, and it's tempting to treat that first value hit as decisive when it's really just a candidate. You need a full structural equality check, the same one used for 'Same Tree', run at every node of root as a candidate root: values must match at every corresponding position and the shapes must line up exactly, with both trees running out of nodes at the same spots. Just as important, a candidate that fails deep down does not disqualify the real match sitting somewhere else in the tree -- keep walking every node of root and trying the full comparison fresh each time, short-circuiting only once a genuine full match is found.
Two nested recursions: one walks every node of the host tree, the other checks structural equality from that node down. Keeping them separate matters — equality must compare entire trees, not just find matching values.
Approach
Write isSameTree as a helper
Build a standalone structural-equality check: two null nodes are equal, one null and one non-null are not, two non-null nodes are equal only if their values match and both their left and right subtrees are recursively equal.
Try every node of root as a candidate
Walk root with a DFS. At each node, call isSameTree(node, subRoot). If it returns true, the whole answer is true and you can stop. If it returns false, that just rules out this one candidate -- move on to the node's children and keep trying.
Don't let a value match short-circuit the search
Never treat 'the values are equal' alone as a signal to stop; only a true result from the full structural comparison ends the search. A failed comparison at one node is simply discarded, and the walk continues into both children looking for a better candidate.
Solution & live demo
Common pitfalls
Continuing to compare after a value match
if node.val == subRoot.val:
return Trueif isSameTree(node, subRoot):
return TrueA matching root value says nothing about the subtrees beneath it. The full structural comparison is the only thing that establishes a genuine subtree.
Returning false as soon as one side is null
if not a or not b:
return Falseif not a and not b:
return True
if not a or not b:
return FalseTwo null nodes are equal — that's how the comparison bottoms out successfully. Testing the or case first makes every recursion end in false and no tree ever matches itself.
Stopping the walk on the first structural mismatch
if not isSameTree(node, subRoot):
return Falsereturn walk(node.left) or walk(node.right)
A mismatch at this node says nothing about its descendants — the subtree may appear deeper. The walk must continue into both children before concluding.
Edge cases
An empty tree is conventionally considered a subtree of anything (isSameTree against null succeeds trivially at any null candidate), though most test suites don't exercise this directly -- follow the same isSameTree logic regardless.
No candidate nodes exist to try, so the walk finds nothing and returns false.
isSameTree catches this correctly since it compares structure, not just values -- a matching root value with mismatched children still returns false for that candidate.
The walk must continue past failed candidates near the top and keep checking every descendant node, since the true match may be far from the root.