Subtree of Another Tree

Problem

Given the roots of two binary trees root and subRoot, return True if some subtree of root is identical to subRoot (same structure and same values), and False otherwise.

A subtree of root is a node in root together with all of that node’s descendants — you cannot cut branches off. The whole tree counts as a subtree of itself.

Examples

Example 1

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: True

The subtree rooted at root’s node 4 is exactly [4,1,2].

Example 2

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: False

Root’s node 4 now has an extra 0 hanging under its child 2, so its subtree is [4,1,2,null,null,0] — a match must include every descendant.

Example 3

Input: root = [1,1], subRoot = [1]
Output: True

The left child of root is a single node 1, identical to subRoot.

Constraints

• Nodes in root: [1, 2000]; nodes in subRoot: [1, 1000].
• -10^4 <= Node.val <= 10^4 (values are not distinct — several candidates may share subRoot’s root value).

Bounds are small enough that an O(n·m) solution passes, but the follow-up question is how to beat it.

Think about it first

TL;DR

Same-tree check at every node — O(n·m) time, O(h) space; serialization + string matching gets O(n+m).

Approach 1 — Brute force: try a same-tree check at every node

The direct translation of the definition: subRoot matches somewhere iff the tree rooted at some node of root is identical to it. So walk root, and at each node run the classic isSameTree lockstep comparison (see the Same Tree problem).

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        if root is None:
            return subRoot is None
        if self.isSameTree(root, subRoot):
            return True
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None and q is None:
            return True
        if p is None or q is None or p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Walkthrough on Example 2 (root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]):

1. At 3: isSameTree fails immediately (3 != 4).
2. At 4: values match, children 1 and 2 match… but subRoot’s 2 is a leaf while root’s 2 has left child 0 → one-sided None → identity fails.
3. Recurse into 1, 2, 0, 5 — none has value 4 at the right place. Answer: False.

Complexity: O(n·m) time in the worst case (an identity check from each of n nodes can cost m), O(h_root + h_sub) recursion space. With n ≤ 2000, m ≤ 1000 this passes comfortably — but the “why the constraints kill it” here is the follow-up: adversarial inputs (e.g. all-equal values) genuinely hit n·m comparisons, and larger trees demand better.

Approach 2 — Serialize both trees, then substring search

The insight: a preorder serialization that records null children uniquely encodes a tree’s structure, and every subtree of root appears as a contiguous piece of root’s serialization. So “is subRoot a subtree?” becomes “is subRoot’s string a substring of root’s string?” — solvable in linear time with KMP (Knuth–Morris–Pratt, the classic algorithm that precomputes a failure table so text scanning never backtracks). Two encoding traps: mark nulls (else shape is lost) and delimit values (else value 2 matches inside 12) — prefixing every value with ^ handles both.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def serialize(node: Optional[TreeNode]) -> str:
            if node is None:
                return "#"
            left = serialize(node.left)
            right = serialize(node.right)
            return f"^{node.val} {left} {right}"

        text, pattern = serialize(root), serialize(subRoot)
        return self.contains(text, pattern)

    def contains(self, text: str, pattern: str) -> bool:
        # KMP substring search: O(len(text) + len(pattern)).
        fail = [0] * len(pattern)
        k = 0
        for i in range(1, len(pattern)):
            while k and pattern[i] != pattern[k]:
                k = fail[k - 1]
            if pattern[i] == pattern[k]:
                k += 1
            fail[i] = k
        k = 0
        for ch in text:
            while k and ch != pattern[k]:
                k = fail[k - 1]
            if ch == pattern[k]:
                k += 1
            if k == len(pattern):
                return True
        return False

(In practice Python’s pattern in text uses an efficient search and is the idiomatic one-liner; KMP is shown because “how would you avoid worst-case quadratic matching?” is the expected interview follow-up.)

Walkthrough on Example 1 (root = [3,4,5,1,2], subRoot = [4,1,2]):

1. serialize(subRoot) = ^4 ^1 # # ^2 # #.
2. serialize(root) = ^3 ^4 ^1 # # ^2 # # ^5 # #.
3. The pattern occurs starting at root’s ^4 → True. In Example 2 the text instead contains ^2 ^0 # # # where the pattern needs ^2 # #, so the match fails.

Complexity: O(n + m) time and O(n + m) space for the strings. (A third classic variant — Merkle hashing, giving each subtree a hash of (val, hash(left), hash(right)) and comparing hashes — achieves the same bound.)

Common pitfalls

• Matching values without shape: serializing without # null markers makes [1,2] and [1,null,2] identical — shape must be encoded.
• Missing value delimiters: without the ^ prefix, subRoot [2] (“2 # #”) false-matches inside root [12] (“12 # #”).
• Committing to the first value match: in Approach 1, finding root.val == subRoot.val doesn’t mean you can stop searching elsewhere on failure — Example 2’s node 4 fails, and other candidates must still be tried (values repeat).
• Wrong null semantics: an empty subRoot is a subtree of anything, but an empty root contains only an empty subRoot. Get the base cases from that sentence, not by pattern-matching other problems.

Pattern takeaway

“Does tree B occur inside tree A?” decomposes into a cheaper primitive (tree identity) applied at every node — recognize this reduce-to-a-subroutine shape. And when a nested-loops-over-structures solution feels wasteful, serialization is the classic escape hatch: a null-marked, delimited preorder string is a faithful fingerprint of a tree, converting tree containment into substring search where linear-time tools (KMP, hashing) already exist.