Subtree of Another Tree

easyTests passed 2026-11-11v1.0.0
TC: O(S * T)|SC: O(Hs)
TreesOriginal Statement (leetcode).md

1. Core Invariant / The Trick

A tree rooted at `root` contains `subRoot` iff `sameTree(root, subRoot)` or `subRoot` is in `root.left` or `root.right`. (For huge trees, serialize preorder with null sentinels + `#` delimiter and run KMP in `O(S + T)`.)

2. Complexity Bounds & Proof

Recursive `isSameTree` at candidate root nodes costs at most O(T) per node of S; Merkle hashing or preorder KMP reduces time to linear O(S + T).

3. Minimal Idiomatic Code

def isSubtree(root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
    def same(a, b):
        if not a and not b:
            return True
        if not a or not b or a.val != b.val:
            return False
        return same(a.left, b.left) and same(a.right, b.right)
    if not subRoot:
        return True
    if not root:
        return False
    return same(root, subRoot) or isSubtree(root.left, subRoot) or isSubtree(root.right, subRoot)

4. Failure Modes & Interview Follow-ups

Pitfalls:- Returning `False` when `root.val != subRoot.val` instead of recursing down `root.left` and `root.right`. - Preorder string matching without root delimiters confuses `[12]` with `[2]`.
Follow-ups:- Ask interviewer whether O(S + T) Merkle hashing or KMP serialization is preferred for scale.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Same Tree (O(min(P, Q)))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.