Subtree of Another Tree

Difficulty: Easy
Topics: Tree, Depth-First Search, String Matching, Binary Tree, Hash Function
Link: https://leetcode.com/problems/subtree-of-another-tree/

Problem Description

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself.

Example 1:


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

Example 2:


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

Constraints:

The number of nodes in the root tree is in the range [1, 2000].
The number of nodes in the subRoot tree is in the range [1, 1000].
-104 <= root.val <= 104
-104 <= subRoot.val <= 104

Solution

1. Problem Deconstruction

Technical Definition:
Given two binary trees root and subRoot, design an algorithm to verify the existence of a node n in root such that the subtree rooted at n is structurally and functionally identical to subRoot. Structural identity requires identical node connectivity and hierarchy, while functional identity requires matching node values. The entire root tree qualifies as a subtree of itself.

Beginner Explanation:
Imagine two family trees: a large one (root) and a smaller one (subRoot). We need to check if the big tree contains any section that looks exactly like the smaller tree. This section must start from a single person and include all their descendants in the exact same arrangement. The entire big tree counts as one possible section.

Mathematical Formulation:
Let ( T ) = root and ( S ) = subRoot be rooted binary trees. Define:

( \text{identical}(A, B) = \begin{cases} \text{true} & \text{if } A = \emptyset \land B = \emptyset \ \text{false} & \text{if } A = \emptyset \oplus B = \emptyset \ A.\text{val} = B.\text{val} \land \text{identical}(A.\text{left}, B.\text{left}) \land \text{identical}(A.\text{right}, B.\text{right}) & \text{otherwise} \end{cases} )
( \text{isSubtree}(T, S) = \exists n \in T : \text{identical}(\text{subtree}(n), S) )
where ( \text{subtree}(n) ) = tree rooted at node ( n ).

Constraint Analysis:

Nodes in root: [1, 2000]
- Limits solutions to ( O(n \cdot m) ) max (2000 × 1000 = 2e6 operations acceptable).
- Implies worst-case height ( h_T \leq 2000 ) → recursion depth risks stack overflow.
Nodes in subRoot: [1, 1000]
- Worst-case subtree comparison ( O(m) ) per candidate node.
- Ensures ( h_S \leq 1000 ), but recursion in subtree checks must handle depth.
Node values: [-10⁴, 10⁴]
- No special handling beyond standard comparisons.
- Edge case: Negative values don’t affect logic but test equality rigorously.

Hidden Edge Cases:

Entire root matches subRoot → Must check root node.
subRoot is a leaf node → Single-node comparison.
Deeply nested subtree → Requires full traversal of root.
Partial structure match (e.g., Example 2) → Value match but structural mismatch at deeper levels.
Skewed trees → Recursion depth risks stack overflow; iterative traversal preferred.

2. Intuition Scaffolding

Real-World Metaphor:
Searching for a specific Lego structure within a larger Lego model. Each candidate base brick (node in root) requires checking if attaching bricks below matches the smaller design (subRoot) exactly.

Gaming Analogy:
In a skill-tree game, verifying if a player’s unlocked subtree matches a predefined skill path. Each node activation must mirror the target subtree’s connections and abilities.

Math Analogy:
Determining if a smaller graph ( S ) is isomorphic to a connected subgraph of ( G ) (tree isomorphism is tractable via DFS).

Common Pitfalls:

Root-Only Check: Assuming match must start at root’s top (negates nested subtrees).
Shallow Comparison: Only checking root values without descending into children.
Early Termination: Stopping after first mismatched node without checking other candidates.
Null Mismanagement: Failing to handle null children asymmetrically (e.g., one tree has left child, other doesn’t).
Recursion Depth: Stack overflow for degenerate trees (e.g., linked-list structure).

3. Approach Encyclopedia

Brute-Force DFS

Concept: For every node in root, check if the subtree rooted there matches subRoot via simultaneous DFS.

Pseudocode:

function isSameTree(p, q):
    if p is null AND q is null: return true
    if p is null OR q is null: return false
    return p.val == q.val AND 
           isSameTree(p.left, q.left) AND 
           isSameTree(p.right, q.right)

function isSubtree(root, subRoot):
    if root is null: return false
    if isSameTree(root, subRoot): return true
    return isSubtree(root.left, subRoot) OR 
           isSubtree(root.right, subRoot)

Complexity Proof:

Time: ( O(n \cdot m) )
- ( n ) nodes in root, each triggering subtree match of ( O(m) ) in worst-case.
- Worst-case: Every node in root is checked, and each check traverses all ( m ) nodes.
Space: ( O(\max(h_T, h_S)) )
- Recursion stack depth for isSubtree: ( O(h_T) ).
- Recursion for isSameTree: ( O(h_S) ).

Visualization:

root:      3          subRoot:   4
          / \                  / \
         4   5                1   2
        / \
       1   2

Step 1: Check root(3) vs subRoot(4) → 3 ≠ 4 → false.
Step 2: Check left(4) vs subRoot(4) → 4=4 → recurse left(1 vs 1), right(2 vs 2) → true.

Iterative DFS Optimization

Concept: Convert outer traversal to iterative DFS to avoid recursion stack overflow for tall trees. Inner subtree check uses iterative DFS.

Pseudocode:

function isSameTree(p, q):
    stack = [(p, q)]
    while stack not empty:
        (n1, n2) = stack.pop()
        if n1 and n2:
            if n1.val ≠ n2.val: return false
            push (n1.right, n2.right)
            push (n1.left, n2.left)
        else if n1 or n2:
            return false
    return true

function isSubtree(root, subRoot):
    stack = [root]
    while stack not empty:
        node = stack.pop()
        if node ≠ null:
            if isSameTree(node, subRoot): return true
            push node.right, node.left
    return false

Complexity Proof:

Time: ( O(n \cdot m) ) — Same as brute-force.
Space: ( O(n) )
- Outer stack holds up to ( O(n) ) nodes.
- Inner stack holds up to ( O(m) ) nodes, but ( m \leq 1000 ).

Visualization:

Example 2:
root:     3         subRoot:  4
         / \                 / \
        4   5               1   2
       / \
      1   2
         /
        0

Outer stack: [3] → pop 3 → check 3 vs 4 → false.
Push 5, 4 → stack=[5,4].
Pop 4 → check 4 vs 4: 
  - 4=4 → push (2,2), (1,1) to inner stack.
  - Pop (1,1): match.
  - Pop (2,2): match, but root's 2 has left child (0), subRoot's 2 has none → false.
Push root(4)'s children: 2, 1 → stack=[5,2,1].
... Continue until stack empty → return false.

4. Code Deep Dive

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:
        stack = [root]  # Outer DFS stack
        while stack:
            node = stack.pop()
            if node:
                # Check subtree match at current node
                if self.isSameTree(node, subRoot):
                    return True
                # Continue DFS traversal
                stack.append(node.right)
                stack.append(node.left)
        return False

    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        stack = [(p, q)]  # Inner DFS stack for pairwise comparison
        while stack:
            n1, n2 = stack.pop()
            if n1 and n2:
                if n1.val != n2.val:
                    return False
                # Process children: right first for LIFO left precedence
                stack.append((n1.right, n2.right))
                stack.append((n1.left, n2.left))
            elif n1 or n2:
                # One null, one non-null → mismatch
                return False
            # Both null: continue
        return True

Line-by-Line Analysis:

isSubtree:
- Line 7: Initialize stack with root → starts traversal.
- Line 8: Loop until stack exhausted → ensures full coverage.
- Line 10: Null check skips processing (defensive).
- Line 12: Calls isSameTree for current candidate → critical comparison.
- Lines 15-16: Push right before left for LIFO preorder traversal.
isSameTree:
- Line 21: Pairwise stack tracks synchronized nodes.
- Line 23: Both non-null → proceed to value check.
- Line 24: Value mismatch → immediate failure.
- Lines 26-27: Push children → right first for left precedence on pop.
- Line 28: Asymmetric nulls → structural mismatch.

Edge Case Handling:

Example 1:
- isSubtree checks root(3) → fail. Then node(4) → isSameTree matches values/children → returns true.
Example 2:
- Node(4) matched initially but isSameTree fails at node(2) due to extra child (0) → checks node(1), node(2), node(0) → all fail.
Deep Nesting:
- Iterative DFS avoids recursion overflow for root height ≤ 2000.
Leaf Match:
- Single-node subRoot matched when a leaf in root has same value.

5. Complexity War Room

Hardware-Aware Analysis:

Worst-case 2e6 operations (2000 × 1000) at 1e6 ops/sec → 2 sec (Python acceptable).
Memory: Stack holds ( O(n) ) nodes → 2000 nodes × 24 bytes/node ≈ 48KB (fits in L2/L3 cache).

Approach Comparison:

Approach	Time	Space	Readability	Interview Viability
Brute-Force DFS	(O(n \cdot m))	(O(h))	9/10	❌ (Stack overflow)
Iterative DFS	(O(n \cdot m))	(O(n))	8/10	✅ (Robust)
Merkle Hashing	(O(n + m))	(O(n))	6/10	✅ (Advanced)

6. Pro Mode Extras

Variants:

Multi-Transaction Subtree (LC 572 Extended):
- Find if subRoot appears ≥ k times in root → Track matches during traversal.
Approximate Subtree Match (k Mismatches):
- Allow ≤ k node/value differences → Modify isSameTree to count errors.
Subtree with Wildcard Nodes:
- Designate wildcard values in subRoot that match any node in root → Adjust value check.

Interview Cheat Sheet:

First Mention: Time/space complexity.
Key Insight: Every node in root is a potential subtree root.
Gotcha: Null handling in tree comparisons.
Optimization Path:
1. Brute-force DFS → intuitive but risky recursion.
2. Iterative DFS → robust for large heights.
3. Merkle hashing → (O(n + m)) with collision risk.

#572 - Subtree of Another Tree