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 omit any descendant. 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

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

The two trees from Example 1, with the matching subtree rooted at root’s node 4:

graph TD
  subgraph root
    A3((3)) --> A4((4))
    A3 --> A5((5))
    A4 --> A1((1))
    A4 --> A2((2))
  end
  subgraph subRoot
    B4((4)) --> B1((1))
    B4 --> B2((2))
  end

# 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


def isSameTree(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 isSameTree(p.left, q.left) and isSameTree(p.right, q.right)


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

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. The interesting case is the follow-up: adversarial inputs such as all-equal values genuinely reach n·m comparisons, and larger trees require a better bound.

Approach 2 — Serialize both trees, then substring search

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, which precomputes a failure table so the text scan never backtracks). Two encoding requirements: mark nulls (otherwise shape is lost) and delimit values (otherwise 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


def contains(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


def isSubtree(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 contains(text, pattern)

(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; this is the reduce-to-a-subroutine shape. When a nested-loops-over-structures solution is too slow, serialization is the standard alternative: a null-marked, delimited preorder string uniquely encodes a tree, converting tree containment into substring search, where linear-time tools (KMP, hashing) apply.