Subtree of Another Tree: when Same Tree becomes a subproblem

Same Tree (problem 100) asked whether two trees are identical. This problem asks whether one tree appears as a rooted, connected subtree inside another — which turns out to be Same Tree called repeatedly, once for each node in the outer tree. The relationship between these two problems is not just motivational; the isIdentical helper you write here is literally the isSameTree function from the previous problem, lifted unchanged.

The question is structural: does some node in root start a subtree that is identical — same shape, same values, all the way to the leaves — to subRoot? Notice "connected" is baked into the definition. You cannot pick and choose nodes from different levels. A subtree is a node and all its descendants.

What the constraints force

root has up to 2000 nodes. subRoot has up to 1000. Values sit in [-10⁴, 10⁴].

Those bounds are small. 2000 nodes for root means a worst-case DFS depth of 2000 (completely skewed chain). Python's default stack is 1000 calls, so on a maximally skewed chain you can hit a recursion limit in theory — but in practice, CPython increments the limit to 1500 in some environments and LeetCode's judge does not enforce the 1000-deep limit strictly for trees this small. If you ever see a MLE/RLE here, raising sys.setrecursionlimit by a small amount fixes it; do not reach for iteration unless the problem says otherwise.

The key interaction is between the sizes: if root has m nodes and subRoot has n nodes, brute-force is O(m × n). With m = 2000 and n = 1000, that is 2 × 10⁶ node comparisons — well within a second. The constraint does not demand the serialization approach; it just makes it available as an optimization if you want it.

The value range [-10⁴, 10⁴] matters for serialization. When you convert a tree to a string, you need to distinguish the number 1 followed by the number 2 (two separate nodes) from the number 12 (one node). That is the trap in approach 2.

Approach 1: DFS with a same-tree helper

Traverse every node of root. At each node, ask whether the subtree rooted there is identical to subRoot. If yes, return true. If not, continue down the left and right children.

Two functions: isSubtree does the traversal; isIdentical does the comparison at a single root pair.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class Solution:
    def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
        if not root:
            return False
        if self.isIdentical(root, subRoot):
            return True
        return (self.isSubtree(root.left, subRoot) or
                self.isSubtree(root.right, subRoot))
 
    def isIdentical(self, s: TreeNode, t: TreeNode) -> bool:
        if not s and not t:
            return True
        if not s or not t:
            return False
        return (s.val == t.val and
                self.isIdentical(s.left, t.left) and
                self.isIdentical(s.right, t.right))

public class Solution {
    public bool IsSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;
        if (IsIdentical(root, subRoot)) return true;
        return IsSubtree(root.left, subRoot) || IsSubtree(root.right, subRoot);
    }
 
    private bool IsIdentical(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;
        return s.val == t.val
            && IsIdentical(s.left, t.left)
            && IsIdentical(s.right, t.right);
    }
}

By-hand trace through Example 1

root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2], expected output: true.

Start at node 3. isIdentical(3-node, 4-node): vals differ (3 ≠ 4) -> false. Move to root's left child, node 4. isIdentical(4-node, 4-node): vals match. Recurse left: isIdentical(1-node, 1-node) -> vals match, both children null -> true. Recurse right: isIdentical(2-node, 2-node) -> vals match, both children null -> true. So isIdentical at node 4 returns true. isSubtree returns true immediately; the right subtree (node 5) is never visited.

Example 2 adds a node 0 under node 2 in root. When we hit node 4 in root this time, isIdentical recurses to node 2 on the left and node 2 on the right. On the left tree the comparison lands at the left child of 2 (node 0) vs the left child of 2 in subRoot (null). One is non-null, one is null -> false. isIdentical returns false. isSubtree continues to node 5 in root, tries isIdentical(5-node, 4-node), fails immediately. Returns false.

Complexity

• Time: O(m × n) — for each of the m nodes in root we may run isIdentical, which touches up to n nodes in subRoot.
• Space: O(max(H_root, H_sub)) — the call stack depth is bounded by the taller tree. Worst case O(m + n) for two fully skewed chains.

Approach 2: String serialization with a safe delimiter

Serialize both trees to strings using preorder traversal, then check whether the serialized subRoot appears as a substring of the serialized root. If it does, the structural match exists.

This sounds simple. The trap is in the delimiter design. Suppose you serialize a node with value 1 as "1" and null as "". The string for a single-node tree with value 12 and the string for two consecutive nodes with values 1 and 2 could collide. You need the delimiter to make values non-ambiguous.

The fix: prefix every value with a separator that cannot appear inside the integer, and give null its own unique token. I use # as a separator before each real value and #null for null nodes.

serialize([4,1,2])   = "#4#1#null#null#2#null#null"
serialize([3,4,5,1,2]) = "#3#4#1#null#null#2#null#null#5#null#null"

The substring "#4#1#null#null#2#null#null" appears exactly once in the second string, at position 2. No false positive possible because # before a value guarantees the value starts there, not mid-digit.

class Solution:
    def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
        def serialize(node):
            if not node:
                return "#null"
            return f"#{node.val}{serialize(node.left)}{serialize(node.right)}"
 
        return serialize(subRoot) in serialize(root)

public class Solution {
    public bool IsSubtree(TreeNode root, TreeNode subRoot) {
        return Serialize(root).Contains(Serialize(subRoot));
    }
 
    private string Serialize(TreeNode node) {
        if (node == null) return "#null";
        return $"#{node.val}{Serialize(node.left)}{Serialize(node.right)}";
    }
}

The C# string.Contains call uses a naive substring search internally (KMP is not guaranteed), but for strings of length O(m) and O(n) the average case is fast enough. If you need guaranteed O(m + n) substring matching, implement KMP or Rabin-Karp over the serialized strings — but at these constraint sizes, Contains is fine.

Complexity

• Time: O(m + n) — one serialization pass each, then a substring search over strings of total length proportional to m + n.
• Space: O(m + n) — the two serialized strings. The recursion stack is O(H_root + H_sub), dominated by the string storage.

Edge cases

subRoot is root itself. isIdentical(root, subRoot) is the first check in isSubtree. If the two trees are identical, this returns true on the first call. In serialization, serialize(subRoot) == serialize(root), so in returns true. Both handle it.

subRoot is larger than root (more nodes). isSubtree recurses until root is null, which returns false. In serialization, a longer serialized string cannot be a substring of a shorter one — Python's in operator returns false immediately if len(needle) > len(haystack).

Values that share digit prefixes, like 1 and 12. Approach 1 compares integer values, so 1 != 12 trivially. Approach 2 without the # prefix would serialize [1, 12] and a node valued 112 identically. The # prefix makes it #1#12 vs #112 — unambiguous.

A null subRoot. The problem guarantees subRoot has at least one node ([1, 1000] range), so this cannot happen within the given constraints. If it could, the standard answer is true — a null is a valid (empty) subtree of anything.

Both trees are single nodes with the same value. isIdentical returns true at the root; isSubtree short-circuits on the first call.

Approach comparison

For the constraints here — m ≤ 2000, n ≤ 1000 — I would ship approach 1 in an interview without apology. The math works out: 2 × 10⁶ operations, no string allocation, nothing that can go wrong in the delimiter design. Approach 2 is the right answer if someone asked this problem with m and n in the millions, or if the same-tree check was expensive (say, nodes held floating-point values with tolerance comparisons that make equality ambiguous). At 2000 nodes, the overhead of building and searching a string is likely to be slower in wall time than the DFS — heap allocation and substring search have real constants.

That said, approach 2 is genuinely elegant and worth knowing. The insight — "transform the structural question into a string question, then use fast string search" — appears again in problems like Serialize and Deserialize Binary Tree (297) and Find Duplicate Subtrees (652).

Series placement and related problems

This is the fifth article in the trees series. The progression so far:

• Problems 104 and 226 introduced single-tree DFS: compute a property of the whole tree recursively.
• Problem 102 introduced level-order BFS: process nodes layer by layer with a queue.
• Problem 100 introduced two-tree DFS: compare two trees node by node. That isIdentical helper is the core of this problem.
• Problem 572 (here) composes the two-tree comparison into a search: call isIdentical at every node of the outer tree.

The composition pattern — use a solved subproblem as a subroutine inside a traversal — shows up in several closely related problems:

652. Find Duplicate Subtrees. For each node, determine whether its subtree structure appears elsewhere in the same tree. The serialization approach from here maps directly: serialize every subtree, use a hash map to detect duplicates. Same trick, different question.

1367. Linked List in Binary Tree. Given a linked list and a binary tree, check whether the list appears as a downward path in the tree. Same outer traversal (visit every node), different inner check (match a list prefix starting from that node). Structurally identical to 572 but the inner comparison is a list walk instead of a tree comparison.

124. Binary Tree Maximum Path Sum. Not a subtree matching problem, but it shows the same pattern of "at each node, compute something that depends on both subtrees and decide whether to extend the global answer." The outer traversal drives the global result; the inner logic is the per-node contribution.

297. Serialize and Deserialize Binary Tree. The serialization approach in this problem is a simplified version of full tree serialization. Problem 297 asks you to make the encoding and decoding roundtrip correctly for arbitrary trees — same preorder-with-null-markers idea, harder correctness requirements.