Approach Summary
Traverse the main binary tree. At each node, evaluate whether the subtree rooted at that node is identical to the target subRoot using the Same Tree comparison.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Recursive Traversal with SameTree Matcher (Optimal) | O(m * n) | O(h) call stack | Traverse root; at each node, verify if the subtree rooted there is identical to subRoot. |
| 2 Approach 2: Tree Serialization with String Matching | O(m + n) | O(m + n) | Serialize both trees into unique preorder strings with delimiters and perform substring search. |
Step 1: Baseline
Approach 1: Recursive Traversal with SameTree Matcher (Optimal)
Time: O(m * n)
Space: O(h) call stack
If root is null, it cannot contain subRoot (return false). At the current root node, call `isSameTree(root, subRoot)`. If true, we found an exact match. Otherwise, recurse on `isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot)`. This modular approach combines tree traversal with synchronized node comparison.
Approach 1: Recursive Traversal with SameTree Matcher (Optimal) Implementation
Approach 1: Recursive Traversal with SameTree Matcher (Optimal)
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null || p.val != q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) return false;
if (isSameTree(root, subRoot)) return true;
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
}class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (p == NULL && q == NULL) return true;
if (p == NULL || q == NULL || p->val != q->val) return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if (root == NULL) return false;
if (isSameTree(root, subRoot)) return true;
return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
};def is_same_tree(p, q):
if not p and not q:
return True
if not p or not q or p.val != q.val:
return False
return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)
def is_subtree(root, sub_root) -> bool:
if not root:
return False
if is_same_tree(root, sub_root):
return True
return is_subtree(root.left, sub_root) or is_subtree(root.right, sub_root)function isSameTree(p, q) {
if (!p && !q) return true;
if (!p || !q || p.val !== q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
function isSubtree(root, subRoot) {
if (!root) return false;
if (isSameTree(root, subRoot)) return true;
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
} Step 2: Most Optimized
Approach 2: Tree Serialization with String Matching
Time: O(m + n)
Space: O(m + n)
Serialize both root and subRoot into preorder string representations using a distinctive marker (e.g. "^" before values and "#" for null nodes). A tree subRoot is a subtree of root if and only if the serialized string of subRoot appears as a substring of the serialized string of root. This evaluates in linear O(m + n) time, resolving the quadratic worst-case trap of repeated values.
Approach 2: Tree Serialization with String Matching Implementation
Approach 2: Tree Serialization with String Matching
class Solution {
void serialize(TreeNode node, StringBuilder sb) {
if (node == null) {
sb.append(",#");
return;
}
sb.append(",^").append(node.val);
serialize(node.left, sb);
serialize(node.right, sb);
}
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
StringBuilder s1 = new StringBuilder();
StringBuilder s2 = new StringBuilder();
serialize(root, s1);
serialize(subRoot, s2);
return s1.toString().contains(s2.toString());
}
}class Solution {
public:
void serialize(TreeNode* node, string& s) {
if (!node) {
s += ",#";
return;
}
s += ",^" + to_string(node->val);
serialize(node->left, s);
serialize(node->right, s);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
string s1, s2;
serialize(root, s1);
serialize(subRoot, s2);
return s1.find(s2) != string::npos;
}
};def is_subtree(root, sub_root) -> bool:
def serialize(node):
if not node:
return ",#"
return f",^{node.val}" + serialize(node.left) + serialize(node.right)
return serialize(sub_root) in serialize(root)function isSubtree(root, subRoot) {
function serialize(node) {
if (!node) return ",#";
return `,^${node.val}` + serialize(node.left) + serialize(node.right);
}
return serialize(root).includes(serialize(subRoot));
}Edge Cases to Watch
- subRoot is identical to the entire tree root (returns true)
- Single leaf matching subRoot val but having extra children (returns false because full subtree must match)
- Target subRoot appears multiple times in root with different children
- root is null (returns false)
Algorithmic Pattern
View Pattern Guide →
Master the Trees / DFS Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Trees / DFS pattern.
Framework: Trees / DFS • Interview Prep: Tested at FAANG •
Explore all Trees / DFS problems & invariants →
How to Recognize This Pattern
- Check if target tree is a subtree of main tree
- Combine tree traversal with identical tree verification
Complexity Analysis
Time Complexity
O(m * n)
Space Complexity
O(h)
Tags
Tree Depth-First Search String Matching Binary Tree Hash Function
Frequently Asked Questions
What is the optimal time and space complexity for Subtree of Another Tree?
The optimal solution for Subtree of Another Tree achieves O(m * n) runtime complexity and requires O(h) auxiliary space. For each node in the main tree of size m, isSameTree takes up to O(n) comparisons. Hence worst-case time is O(m * n) (e.g. repeated values like long paths of 1s). Average time on realistic trees is O(m + n). Auxiliary space is O(h) for call stack depth.
How do I identify that Subtree of Another Tree requires the Trees / DFS pattern?
In technical interviews, look for key problem signals: Check if target tree is a subtree of main tree; Combine tree traversal with identical tree verification. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Trees / DFS strategy.
What critical edge cases must be handled in Subtree of Another Tree?
Essential edge cases to verify include: subRoot is identical to the entire tree root (returns true); Single leaf matching subRoot val but having extra children (returns false because full subtree must match); Target subRoot appears multiple times in root with different children; root is null (returns false). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Subtree of Another Tree?
Subtree of Another Tree is a Easy-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Facebook, Microsoft.