Subtree of Another Tree

1. Problem & Core Objective

Given roots root and subRoot, return true if there is a node in root whose subtree is identical to subRoot.

    3                          4
   / \        subRoot:        / \      →  true
  4   5                      1   2
 / \
1   2

    3                          4
   / \        subRoot:        / \      →  false
  4   5                      1   2
 / \                              \
1   2                              0

Constraints: 1 <= root nodes <= 2000 · 1 <= subRoot nodes <= 1000 · -10^4 <= Node.val <= 10^4

What's actually being tested: composing question 5 with a traversal — and noticing the subtlety that a match must be a complete subtree, not merely a matching fragment. The O(n) solution via serialization is a genuinely different idea and worth knowing.

Let n = nodes in root, m = nodes in subRoot.

2. First-Principles Thought Process

"Subtree" means the whole thing

This is the trap. A subtree rooted at node x is x and every descendant — you can't stop partway down.

In the second example above, the big tree contains 4 → (1, 2) and subRoot is 4 → (1, 2 → right 0). Those are not the same subtree: subRoot has an extra node. And conversely, if subRoot were 4 → (1, 2) and the big tree's node 2 had a child, that's also a mismatch — the big tree's subtree has an extra node.

So the test at each candidate node is exact identity, which is precisely question 5.

The straightforward structure

isSubtree(root, sub) = isSame(root, sub)
                       OR isSubtree(root.left, sub)
                       OR isSubtree(root.right, sub)

Try every node of the big tree as a candidate root.

The cost

Each of the n candidates may run isSame, which is O(m). So O(n × m) — at 2000 × 1000 that's 2 × 10^6, which is comfortable.

Worth noting the worst case is rarer than it looks: isSame short-circuits on the first value mismatch, so it usually costs O(1). It only runs to O(m) when the subtrees genuinely agree for a long way — which needs many repeated values.

The linear alternative

Serialize both trees to strings with null markers, then ask whether the big tree's string contains the small tree's string. With KMP, substring search is O(n + m).

The null markers are essential — they're what make the serialization unambiguous, exactly as discussed in question 5.

But there's a second subtlety, and it's the one people miss: you also need value delimiters, or 12 matches inside 120. Both problems are solved by emitting something like ,12, for each node.

3. Solution Paths

Approach 1 — Try every node (the expected answer)

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if (subRoot == null) return true;              // an empty tree is a subtree of anything
    if (root == null)    return false;             // ran out of candidates

    if (isSameTree(root, subRoot)) return true;
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

private boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;
    if (p.val != q.val)         return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

• Time O(n × m) worst case · Space O(h) stack

Counter-questions on this approach

⭐ "Is O(n × m) really reached in practice?"

Rarely. isSameTree short-circuits at the first differing value, so at most candidate nodes it costs O(1) — the root values simply don't match.

To actually hit O(n × m) you need many nodes that agree with subRoot for a long way before diverging. The adversarial input is a tree of all-identical values, like a left chain of 2000 nodes all holding 1, with subRoot a chain of 1000 ones. Then every candidate matches for 1000 nodes before failing.

So I'd say the bound is O(n × m) but the typical cost is much closer to O(n + m).

⭐ "Why if (subRoot == null) return true before the root check?"

An empty tree is vacuously a subtree of any tree, including an empty one. Checking it first also means the later code never has to reason about a null subRoot.

Given the constraint 1 <= subRoot nodes, it can't actually happen here — but it makes the function total rather than relying on the caller.

"Why is it || rather than checking both children unconditionally?"

Short-circuit. Once a match is found anywhere on the left, there's no reason to search the right. It doesn't change the worst case but it halves the expected work on a hit.

"Can you prune the search?"

Yes, usefully. Precompute the height of subRoot, and skip any candidate whose height differs — an identical subtree must have an identical height. That requires a height annotation pass, O(n), and then most candidates are rejected in O(1). Same worst case, much better in practice.

Approach 2 — Serialize and substring search (optimal)

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    return serialize(root).contains(serialize(subRoot));
}

private String serialize(TreeNode n) {
    StringBuilder sb = new StringBuilder();
    build(n, sb);
    return sb.toString();
}

private void build(TreeNode n, StringBuilder sb) {
    if (n == null) { sb.append(",#"); return; }
    sb.append(',').append(n.val);        // the leading comma delimits values
    build(n.left, sb);
    build(n.right, sb);
}

• Time O(n × m) with String.contains, O(n + m) with KMP · Space O(n + m)

Counter-questions on this approach

⭐ "Why does each value need a leading comma?"

Without a delimiter, values run together and produce false matches. A tree holding just 12 serializes to 12##, and a tree holding just 2 serializes to 2## — and 12## contains 2##, so it reports true when the correct answer is false.

The leading comma fixes it. Every token — value or null marker — is preceded by a comma, so any alignment of the pattern into the text must begin at a token boundary. ,12,#,# no longer contains ,2,#,#, because the only comma followed by 2 would have to start a token, and there isn't one.

It also handles the prefix case: ,12 can't match inside ,120, since the character after 12 in the text is 0 rather than the comma the pattern requires next.

I verified both: without the delimiter, root = [12] with subRoot = [2] wrongly returns true; with it, false. This is the bug that makes naive serialization solutions fail on large-value test cases.

⭐ "Why do you need the # null markers?"

Without them, preorder is ambiguous: a node with only a left child and a node with only a right child serialize identically. The marker records where the structure terminates, which is what distinguishes them.

Concretely, 1 → left 2 and 1 → right 2 both give ,1,2 without markers, but ,1,2,#,#,# and ,1,#,2,#,# with them.

"String.contains is not KMP. So is this actually O(n + m)?"

No — Java's String.contains uses a naive scan, so it's O(n × m) in the worst case, same as approach 1. To genuinely get linear you must implement KMP or Rabin–Karp yourself.

I'd be straightforward about that: the serialization idea enables O(n + m), but only if you write the matcher. Claiming linearity while calling contains is a common overstatement.

"Does serialization use more memory?"

Yes — O(n + m) characters, versus O(h) for the recursion. At these constraints it's fine, but it's a real trade rather than a strict improvement.

"When is serialization clearly better?"

When you need to test many different subRoots against the same big tree. Serialize the big tree once, then each query is a substring search. The recursion has to restart from scratch every time.

Comparison

4. Why the Optimal Wins

Honestly, for these constraints the straightforward version wins — it's 2 × 10^6 worst case, O(h) space, and it reuses question 5 verbatim. I'd write it first.

The serialization approach is worth knowing for two reasons. It converts a tree problem into a string problem, which unlocks the whole linear-time substring-matching toolkit. And it's the right answer when you're matching many patterns against one tree, where the big tree's serialization is computed once and reused.

The framing worth keeping:

A tree serialized with null markers and value delimiters is a string, and "is this a subtree" becomes "is this a substring". Both markers are load-bearing: nulls fix the structure, delimiters fix the values.

5. Java Prerequisites

StringBuilder, not concatenation. Building a string with + inside a recursion allocates at every node and turns O(n) into O(n²):

private void build(TreeNode n, StringBuilder sb) { ... }   // pass it down

String.contains is a naive scan, not KMP. For guaranteed linear matching you need your own implementation. See 01.

Reusing isSameTree from question 5 verbatim — don't rewrite it.

Short-circuit || gives the early exit when a match is found on the left.

6. Interview Communication Guide

Clarifying questions: Must the match be a complete subtree — node plus all descendants (yes; this is the crux)? Can subRoot be null (constraints say no, but I'd handle it)? Are values bounded, and can they repeat (repeats are what create the worst case)?

The pitch

"A subtree means a node and all of its descendants — not a matching fragment. So at each candidate node the test is exact identity, which is the Same Tree routine.

So: walk the big tree, and at every node ask whether the subtree there is identical to subRoot. That's O(n × m) worst case.

But that bound is pessimistic in practice — isSame short-circuits at the first value mismatch, so most candidates cost O(1). You only reach the worst case with many repeated values, like a chain of 2000 identical nodes.

A useful pruning: precompute subRoot's height and skip candidates whose height differs, since identical subtrees must have identical heights. Same worst case, far fewer full comparisons.

The linear alternative is to serialize both trees and ask whether one string contains the other. Two things are essential there. Null markers, or preorder is ambiguous — a left-only child and a right-only child serialize the same. And value delimiters, or searching for 12 matches inside 120.

I'd note that Java's String.contains is a naive scan, so that version is only genuinely O(n + m) if I write KMP myself. The serialization approach really pays off when matching many patterns against the same tree — serialize once, then each query is a substring search."

Edge cases to volunteer:

Name [1,2] with subRoot = [1]. It's the case that defines "subtree" — node 1 in the big tree has a child, so its subtree isn't a lone node. And [12] vs [2] is the one that exposes a serialization solution without delimiters.

7. Follow-Up Questions — Modified Constraints

⭐ "Find ALL nodes where subRoot occurs, not just whether one exists."

Drop the early return and collect matches into a list. The complexity is unchanged, but the short-circuits disappear, so the typical case gets slower — you now genuinely visit every candidate. With serialization you'd use indexOf in a loop, which still benefits from KMP.

⭐ "Match a subtree shape regardless of values."

Serialize using only structure — emit a fixed token for every node and # for nulls — then substring search. Simpler than the value version, and the delimiter problem disappears since all tokens are identical.

"What if you had to check 1000 different subRoots against one big tree?"

Serialize the big tree once, O(n), then each query is a substring search: O(n + m_i) with KMP. The per-node recursion would redo the whole traversal 1000 times. This is where serialization clearly wins, and it's worth volunteering.

"Use hashing instead of string matching."

Merkle hashing: store at each node a hash of (val, leftHash, rightHash). Then "is this a subtree" is a hash lookup — O(n + m) to build, O(1) per query. Collisions need a verification pass, but this is how git and content-addressed stores compare trees, and it's the right answer if the tree is static and queried often.

"What if the trees were n-ary?"

The recursion generalizes: compare children lists pairwise. Serialization needs an explicit end-of-children marker as well as null markers, or the arity becomes ambiguous — a node with two children followed by a leaf is indistinguishable from a node with three.

"What if subRoot were larger than root?"

The answer is immediately false, and you could precompute sizes to reject in O(1). Same idea as the height pruning — cheap structural invariants that fail fast before any expensive comparison.