Subtree of Another Tree — Serialize or DFS Compare
Either serialise both trees and search for the subtree pattern or perform depth-first node comparisons with early pruning.
Problem Statement
Determine if tree t is a subtree of s.
Why This Problem Matters
- Tests tree recursion and structural equality checks.
- Highlights performance differences between naive comparisons and hashing/serialization.
- Useful precursor to subtree hashing and Merkle tree discussions.
Thought Process
Compare nodes directly
For each node in s, check whether the subtree rooted there matches t via a helper function.
Short-circuit aggressively
If values differ or the node counts mismatch, return early to avoid exploring entire subtrees unnecessarily.
Optionally serialise for clarity
Preorder traversal with null markers creates a string that turns the problem into substring search.
Step-by-Step Reasoning
- Traverse s; whenever a node value equals t.val, call isSameTree to compare structures.
- isSameTree simultaneously walks both nodes, verifying value equality and identical left/right shapes.
- Return true if any comparison succeeds; otherwise false after full traversal.
Dry Run
s rooted at 3 with left subtree 4-1-2, t rooted at 4-1-2
Match found when traversal reaches node 4 inside s.
t larger than s
Helper detects null mismatch immediately and returns false.
Complexity Analysis
Time
O(m · n)
Space
O(h)
Why
Worst-case compares each node in s (n) with subtree t (m); recursion depth bounded by tree height h.
Annotated Solution
public class SubtreeOfAnotherTree {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (subRoot == null) {
return true;
}
if (root == null) {
return false;
}
if (isSameTree(root, subRoot)) {
return true;
}
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
private boolean isSameTree(TreeNode a, TreeNode b) {
if (a == null && b == null) {
return true;
}
if (a == null || b == null) {
return false;
}
if (a.val != b.val) {
return false;
}
return isSameTree(a.left, b.left) && isSameTree(a.right, b.right);
}
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) { this.val = val; }
}
}Recursive brute force remains acceptable because each comparison short-circuits upon mismatch, keeping runtime practical for interview inputs.
Common Pitfalls
- Forgetting to handle null nodes leads to NullPointerException.
- Comparing references instead of values fails when perfectly identical structures exist but with distinct objects.
- Skipping early returns increases runtime to cubic on degenerate trees.
Follow-Up Questions
- Can you improve performance with subtree hashing?
- How would you adapt this to detect isomorphic subtrees ignoring node values?