# Subtree of Another Tree

- **Canonical ID**: `subtree-of-another-tree`
- **Canonical URL**: https://dsacheatsheet.com/problems/subtree-of-another-tree
- **Difficulty**: easy
- **Patterns**: Trees
- **Version**: 1.0.0 (verified 2026-11-11T21:15:00Z)
- **Original Problem**: https://leetcode.com/problems/subtree-of-another-tree/

## 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

- **Time Complexity**: `O(S * T)`
- **Space Complexity**: `O(Hs)`
- **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

### Python
```python
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)
```

### TypeScript
```typescript
export function isSubtree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
  const same = (a: TreeNode | null, b: TreeNode | null): boolean => {
    if (!a && !b) return true;
    if (!a || !b || a.val !== b.val) return false;
    return same(a.left, b.left) && same(a.right, b.right);
  };
  if (!subRoot) return true;
  if (!root) return false;
  return same(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
```

### C++
```cpp
bool same(TreeNode* a, TreeNode* b) {
    if (!a && !b) return true;
    if (!a || !b || a->val != b->val) return false;
    return same(a->left, b->left) && same(a->right, b->right);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
    if (!subRoot) return true;
    if (!root) return false;
    return same(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
```

### Java
```java
boolean same(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;
    if (a == null || b == null || a.val != b.val) return false;
    return same(a.left, b.left) && same(a.right, b.right);
}
boolean isSubtree(TreeNode root, TreeNode subRoot) {
    if (subRoot == null) return true;
    if (root == null) return false;
    return same(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
```

### Go
```go
func isSubtree(root, subRoot *TreeNode) bool {
    if subRoot == nil { return true }
    if root == nil { return false }
    return isSameTree(root, subRoot) || isSubtree(root.Left, subRoot) || 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.