572 · Subtree of Another Tree

Composition. An ordinary traversal over the big tree whose visit action is a whole second recursion — LC 100 called at every anchor. Two recursions stacked on each other, and the O(mn) that follows is expected, not a mistake.

1 — The problem

Does root contain a subtree identical to sub? "Subtree" here means a node and everything below it — not a partial match, not a subgraph. That strictness is what makes LC 100 the right inner test, unchanged.

The structure is two nested questions:

• Outer: which node of root should we try as the anchor? Every one of them — a plain traversal.
• Inner: is the tree hanging off this anchor identical to sub? That is exactly isSameTree, already written.

Recognising a solved problem as the body of a loop is the skill being tested. Most candidates who struggle here try to fuse the two recursions into one; they do not fuse, because they answer different questions and terminate on different conditions.

2 — A traversal that calls a traversal

Watch the two phases alternate. At anchor 3 the inner check dies on its first comparison. At anchor 4 it runs to completion — three matched pairs and two matched pairs of nulls — and the outer traversal stops immediately.

Line 2's root == null returns false, and that is correct even though isSame(null, null) is true — because an empty anchor is not a node of the tree. If sub itself could be null, the problem would be ill-posed; LeetCode's constraints forbid it.

2.1 The trap: matching a prefix instead of a subtree

The single most common wrong answer stops descending as soon as sub runs out. It answers "does sub appear as the top of some subtree", which is a different and easier question:

Using isSame verbatim as the inner test makes this impossible to get wrong: its base cases already reject "one side ran out". Rewriting a "similar" comparison inline is where the bug gets introduced.

2.2 Why O(mn) is the expected answer — and what beats it

The outer traversal visits m anchors; each inner check costs up to O(n). The product is not usually reached — isSame aborts on its first mismatch, and most anchors fail on the root value alone — but the worst case is real: a left-spine of a thousand 1s against a sub of five hundred 1s does the full work.

The O(m + n) solution is a change of representation rather than a better recursion. Serialize both trees with explicit null markers — the same encoding LC 297 uses — and ask whether one string contains the other, with KMP:

private void ser(TreeNode nd, StringBuilder sb) {
    if (nd == null) { sb.append("#,"); return; }
    sb.append('^').append(nd.val).append(',');  // ^ guards 12 vs 2
    ser(nd.left, sb);
    ser(nd.right, sb);
}
// isSubtree: ser(root).contains(ser(sub)) — but use KMP for the O(m+n) bound;
// String.contains is O(mn) in the worst case on the JDK.

The ^ prefix and the trailing comma both matter. Without a delimiter, a node valued 12 serializes into the same characters as 1 followed by 2, and the substring search reports matches that do not exist.

3 — Complexity and edge cases

• Time O(m × n) worst case for the nested recursion, where m and n are the node counts. Space O(h) — the two recursions never nest more than one deep, since isSame returns before the outer traversal continues.
• Anchor is a leaf, sub is a single node: works — isSame compares the values and then two pairs of nulls.
• sub is larger than root: every inner check fails on structure. No special case needed; the base cases handle it.
• Duplicate values everywhere is the adversarial input: many anchors start matching, and each one costs real work before it fails.
• Common bug: returning isSame(root, sub) from line 3 instead of only returning true when it holds. Returning it directly makes the first failed anchor the final answer, and the traversal never happens.
• Common bug: using && instead of || on lines 4–5. The subtree only needs to appear somewhere — one branch succeeding is enough.

4 — Reference implementation

public boolean isSubtree(TreeNode root, TreeNode sub) {
    if (root == null) return false;    // ran out of anchors
    if (isSame(root, sub)) return true;
    return isSubtree(root.left, sub) || isSubtree(root.right, sub);
}

private boolean isSame(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;
    if (a == null || b == null) return false;
    return a.val == b.val
        && isSame(a.left, b.left) && isSame(a.right, b.right);
}

The second method is LC 100 copied without a character changed. That is the intended reading of this problem.