Subtree of Another Tree (LC 572)

Pattern: Tree DFS + Same-Tree Check
Difficulty: Easy
Key Concept: subRoot is a subtree of root if some node x in root has identical structure and values to subRoot; verify with a helper isSame(a, b).

Problem Statement

Given the roots of two binary trees root and subRoot, return true if there is a node in root such that the subtree rooted at that node is equal to subRoot (same structure and values).

Input: root, subRoot (may be null).
Output: boolean.

Example

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

Output: true (subtree at node 4 of root matches subRoot).

---

1. Algorithm & Pseudocode

Brute force

1. Collect all nodes of root in a list (O(n)).
2. For each node x, run isSame(x, subRoot) which scans up to O(m) nodes — worst O(n × m).

This is the standard solution; “more brute” variants stringify subtrees or hash without collision handling.

Pseudocode

function isSame(a, b):
    if a == null && b == null: return true
    if a == null || b == null: return false
    return a.val == b.val && isSame(a.left, b.left) && isSame(a.right, b.right)

function isSubtree(root, subRoot):
    if root == null: return false
    return isSame(root, subRoot)
        || isSubtree(root.left, subRoot)
        || isSubtree(root.right, subRoot)

Optimal

• Same O(n × m) worst-case time is hard to beat without advanced string/KMP/Merkle techniques.
• Pruning optimal in practice: compute hash for each subtree (rolling hash) in O(n), then compare hashes with isSame only on collisions — O(n + m) average with care.

Pseudocode (hash idea)

function dfsHash(node):
    if node == null: return sentinelHash
    left = dfsHash(node.left)
    right = dfsHash(node.right)
    h = combine(node.val, left, right)
    if h == hash(subRoot): maybe check isSame
    return h

For this guide’s code section we keep the clear DFS + same as optimal baseline.

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Subtree means the entire node including all descendants must match, not just the root value.
• isSame short-circuits: first mismatch on value or structure stops.
• Why try every node in root: The alignment of subRoot could start at any position, not necessarily at root.
• Order of checks: isSame(root, sub) first handles the case where subtrees align at the current node; otherwise recurse left/right.

---

3. The Dry Run

root

    3
   / \
  4   5
 / \
1   2

subRoot

  4
 / \
1   2

Step	Current root node	isSame with subRoot?	Action
1	3	false (3≠4)	recurse to 4 and 5
2	4	true	return true

ASCII (match highlighted)

root:
    3
   / \
 [4]  5   ← start matching here
 / \
1   2

subRoot:
 [4]
 / \
1   2

---

4. Java Solution

Brute Force

Explicit list of all nodes then pairwise check.

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) { val = v; }
}

class SolutionBrute {
    // Time: O(n * m), Space: O(n) list + O(h) recursion
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        List<TreeNode> nodes = new ArrayList<>();
        collect(root, nodes);
        for (TreeNode n : nodes) {
            if (isSame(n, subRoot)) return true;
        }
        return false;
    }

    private void collect(TreeNode n, List<TreeNode> nodes) {
        if (n == null) return;
        nodes.add(n);
        collect(n.left, nodes);
        collect(n.right, nodes);
    }

    private boolean isSame(TreeNode a, TreeNode b) {
        if (a == null && b == null) return true;
        if (a == null || b == null) return false;
        return a.val == b.val && isSame(a.left, b.left) && isSame(a.right, b.right);
    }
}

Optimal

class Solution {
    // Time: O(n * m) worst, Space: O(h1 + h2)
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;
        return isSame(root, subRoot)
                || isSubtree(root.left, subRoot)
                || isSubtree(root.right, subRoot);
    }

    private boolean isSame(TreeNode a, TreeNode b) {
        if (a == null && b == null) return true;
        if (a == null || b == null) return false;
        return a.val == b.val && isSame(a.left, b.left) && isSame(a.right, b.right);
    }
}

---

5. The “Java vs. Others” Edge

• Objects.equals not needed for TreeNode references; use == for null checks.
• Common pitfall: String serialization "," + val + "," can collide (12 vs 1,2) — if using strings, add delimiters carefully or use null markers.
• Time limit failures on LeetCode sometimes push you toward hash + verify; Java’s Objects.hash per node is okay with modulo and tie-break isSame.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute (list + check)	O(n × m)	O(n)	Extra list allocation
DFS inline check	O(n × m)	O(h)	Same complexity, less overhead
Hash + verify (avg)	O(n + m)	O(n)	Must handle hash collisions with isSame