138. Subtree of Another Tree
🔗 LeetCode Problem: 572. Subtree of Another Tree
📊 Difficulty: Easy
🏷️ Topics: Binary Trees, Recursion, DFS, Tree Comparison
Problem Statement
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]
- -10^4 <= root.val <= 10^4
- -10^4 <= subRoot.val <= 10^4
🌳 Visual Understanding - Drawing the Problem!
Example 1: Subtree Exists ✓
Tree (root):
3
/ \
4 5
/ \
1 2
SubTree (subRoot):
4
/ \
1 2
Is subRoot a subtree of root? YES! ✓
Why?
The subtree rooted at node 4 in root
is IDENTICAL to subRoot!
Visual match:
4 ←─┐ Same structure
/ \ │ Same values
1 2 ←┘ Complete match!
Example 2: Subtree Does NOT Exist ✗
Tree (root):
3
/ \
4 5
/ \
1 2
/
0
SubTree (subRoot):
4
/ \
1 2
Is subRoot a subtree of root? NO! ✗
Why?
Node 4 in root has:
4
/ \
1 2
/
0 ← Extra child!
SubRoot needs:
4
/ \
1 2 ← No child here!
Not identical → Not a subtree!
Understanding "Subtree":
Key points:
1. Must match COMPLETELY from that node down
2. Can't be partial match
3. Root itself can be a subtree of root
Valid subtree:
Original: Subtree:
1 2
/ \ /
2 3 4
/
4
Subtree starting at 2 matches!
Invalid "subtree":
Original: Not a subtree:
1 1
/ \ / \
2 3 2 3
/ / \
4 5 6
Node 3 in original has no children
But "subtree" shows 3 with children
NOT a complete match!
More Examples:
Example 3: Root equals subRoot
root: 1 subRoot: 1
/ \ / \
2 3 2 3
Result: true ✓
Entire root is identical to subRoot!
Example 4: SubRoot is single node
root: 1 subRoot: 2
/ \
2 3
Result: true ✓
Node 2 in root matches subRoot!
Example 5: SubRoot not found
root: 1 subRoot: 5
/ \
2 3
Result: false ✗
No node 5 in root!
🧠 The AHA Moment - Reusing Problem 131!
The Key Insight:
This problem = Problem 131 (Same Tree) + DFS Search!
Problem 131: isSameTree(p, q)
"Are these two trees identical?"
Problem 138: isSubtree(root, subRoot)
"Is subRoot identical to ANY subtree in root?"
How to solve:
For EACH node in root:
Check if tree at this node == subRoot
(using isSameTree from Problem 131!)
Visual Breakdown:
Tree:
3
/ \
4 5
/ \
1 2
SubRoot:
4
/ \
1 2
Process:
1. Check if tree at 3 == subRoot?
isSameTree(3, 4) → false (values differ)
2. Check if tree at 4 == subRoot?
isSameTree(4, 4) → true ✓ FOUND!
3. No need to check further (already found)
Result: true
The Recursive Strategy:
isSubtree(root, subRoot):
1. Check if current tree == subRoot
if isSameTree(root, subRoot) → return true
2. If not, search in left subtree
if isSubtree(root.left, subRoot) → return true
3. If not, search in right subtree
if isSubtree(root.right, subRoot) → return true
4. If none match
return false
It's DFS search + tree comparison!
🧠 Recursive Thinking - Building the Solution
Part 1: isSameTree (from Problem 131)
We need this helper function!
isSameTree(p, q):
if p == null and q == null:
return true
if p == null or q == null:
return false
if p.val != q.val:
return false
return isSameTree(p.left, q.left) and
isSameTree(p.right, q.right)
This checks if two trees are IDENTICAL!
Part 2: isSubtree (The Main Function)
Base Case 1: root is null
No tree, no subtree!
return false
Base Case 2: Trees are identical
if isSameTree(root, subRoot):
return true
Why? We found a match!
Recursive Case: Search in subtrees
Check left: isSubtree(root.left, subRoot)
Check right: isSubtree(root.right, subRoot)
If either returns true → we found it!
return left OR right
The Complete Logic:
isSubtree(root, subRoot):
if root is null:
return false
// Check if current position matches
if isSameTree(root, subRoot):
return true
// Search in left and right subtrees
return isSubtree(root.left, subRoot) or
isSubtree(root.right, subRoot)
🎯 Solution: Recursive DFS with Helper
Implementation:
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
// Base Case 1: No tree to search in
if (root == null) {
return false;
}
// Base Case 2: Found a match at current node
// WHY? If trees are identical here, we found the subtree!
if (isSameTree(root, subRoot)) {
return true;
}
// Recursive Case: Search in left and right subtrees
// WHY? Subtree might be rooted at any node
// Use OR: need to find it in at least ONE place
return isSubtree(root.left, subRoot) ||
isSubtree(root.right, subRoot);
}
// Helper: Check if two trees are identical (Problem 131!)
private boolean isSameTree(TreeNode p, TreeNode q) {
// Both null - identical
if (p == null && q == null) {
return true;
}
// One null, one not - different
if (p == null || q == null) {
return false;
}
// Values differ - different
if (p.val != q.val) {
return false;
}
// Check subtrees recursively
return isSameTree(p.left, q.left) &&
isSameTree(p.right, q.right);
}
}
Cleaner Version:
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) return false;
// Check current position or search in subtrees
return isSameTree(root, subRoot) ||
isSubtree(root.left, subRoot) ||
isSubtree(root.right, subRoot);
}
private boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false;
return p.val == q.val &&
isSameTree(p.left, q.left) &&
isSameTree(p.right, q.right);
}
}
🔍 Detailed Dry Run with Recursion Visualization
Tree (root):
3
/ \
4 5
/ \
1 2
SubRoot:
4
/ \
1 2
Complete Recursion Flow:
CALL STACK VISUALIZATION:
Level 0: isSubtree(3, subRoot)
│
├─ root = 3, not null ✓
├─ Check: isSameTree(3, 4)?
│ │
│ └─ 3.val ≠ 4.val → return false ✗
│
├─ Not same, search left: isSubtree(4, subRoot) ─┐
│ │
│ Level 1: isSubtree(4, subRoot) │
│ │ │
│ ├─ root = 4, not null ✓ │
│ ├─ Check: isSameTree(4, 4)? │
│ │ │ │
│ │ ├─ 4.val == 4.val ✓ │
│ │ │ │
│ │ ├─ Check left: isSameTree(1, 1) │
│ │ │ │ │
│ │ │ ├─ 1.val == 1.val ✓ │
│ │ │ ├─ Both leaves │
│ │ │ └─ return true ✓ │
│ │ │ │
│ │ ├─ Check right: isSameTree(2, 2) │
│ │ │ │ │
│ │ │ ├─ 2.val == 2.val ✓ │
│ │ │ ├─ Both leaves │
│ │ │ └─ return true ✓ │
│ │ │ │
│ │ └─ true && true → return true ✓ │
│ │ │
│ └─ Trees match! return true ✓ │
│ │
├─ Left returned true → return true ✓ │
│ No need to check right (OR short-circuit) │
│ │
└─ FINAL: return true ✓ │
Result: true (found subtree at node 4)
What Each Call Does:
isSubtree(3, subRoot):
"Is subRoot a subtree starting at 3?"
Check: Is tree at 3 same as subRoot? No
Search left (4): Found it! ✓
Return: true
isSubtree(4, subRoot):
"Is subRoot a subtree starting at 4?"
Check: Is tree at 4 same as subRoot? Yes! ✓
Return: true (no need to search further)
isSameTree calls:
- Compare nodes recursively
- Check values and structure
- Return true only if identical
🔍 Dry Run - Example 2 (Not Found)
Tree (root):
3
/ \
4 5
/ \
1 2
/
0
SubRoot:
4
/ \
1 2
Recursion Flow:
Level 0: isSubtree(3, subRoot)
│
├─ Check: isSameTree(3, 4)? → false ✗
│
├─ Search left: isSubtree(4, subRoot) ─────────┐
│ │
│ Level 1: isSubtree(4, subRoot) │
│ │ │
│ ├─ Check: isSameTree(4, 4)? │
│ │ │ │
│ │ ├─ 4.val == 4.val ✓ │
│ │ │ │
│ │ ├─ Check left: isSameTree(1, 1) │
│ │ │ └─ true ✓ │
│ │ │ │
│ │ ├─ Check right: isSameTree(2, 2) │
│ │ │ │ │
│ │ │ ├─ 2.val == 2.val ✓ │
│ │ │ │ │
│ │ │ ├─ Left: isSameTree(0, null) │
│ │ │ │ └─ One null → false ✗ │
│ │ │ │ │
│ │ │ └─ return false ✗ │
│ │ │ │
│ │ └─ true && false → return false ✗ │
│ │ │
│ ├─ Trees DON'T match → continue search │
│ │ │
│ ├─ Search left: isSubtree(1, subRoot) │
│ │ └─ isSameTree(1, 4)? → false ✗ │
│ │ No children → return false ✗ │
│ │ │
│ ├─ Search right: isSubtree(2, subRoot) │
│ │ └─ isSameTree(2, 4)? → false ✗ │
│ │ Continue searching... │
│ │ All return false ✗ │
│ │ │
│ └─ return false ✗ │
│ │
├─ Left returned false │
│ │
├─ Search right: isSubtree(5, subRoot) ────────┐
│ │ │
│ └─ isSameTree(5, 4)? → false ✗ │
│ 5 is leaf → return false ✗ │
│ │
└─ false || false → return false ✗ │
FINAL: false (subtree not found)
📊 Complexity Analysis
Time Complexity: O(m × n)
Where:
m = number of nodes in root
n = number of nodes in subRoot
Why O(m × n)?
- We visit each node in root: O(m)
- At each node, we call isSameTree: O(n) worst case
- Total: O(m × n)
Detailed breakdown:
isSubtree: O(m) - visits all nodes in root
isSameTree: O(n) - compares all nodes in subRoot
For each of m nodes in root:
Potentially compare all n nodes in subRoot
Worst case: m × n comparisons
Example:
root has 100 nodes
subRoot has 10 nodes
Worst case: 100 × 10 = 1000 operations
Space Complexity: O(h₁ + h₂)
Where:
h₁ = height of root tree
h₂ = height of subRoot tree
Why?
- isSubtree recursion: O(h₁) stack depth
- isSameTree recursion: O(h₂) stack depth
- Can be nested: h₁ + h₂ total
Best case (balanced trees): O(log m + log n)
Worst case (skewed trees): O(m + n)
Note: Both recursions can be active simultaneously
when isSameTree is called from deep in isSubtree
⚠️ Common Mistakes
Mistake 1: Forgetting the Helper Function
// ❌ WRONG - Trying to solve without isSameTree
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) return false;
// How to check if they're the same?
// Need to compare entire subtrees!
// This is Problem 131 - need that solution!
if (root.val == subRoot.val) { // Not enough!
// What about children? Need full comparison!
}
}
// ✓ CORRECT - Use helper function
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) return false;
return isSameTree(root, subRoot) || // Use helper!
isSubtree(root.left, subRoot) ||
isSubtree(root.right, subRoot);
}
Mistake 2: Only Checking Root Values
// ❌ WRONG - Only compares root values
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) return false;
if (root.val == subRoot.val) { // Not sufficient!
return true; // Missing: check entire subtree!
}
return isSubtree(root.left, subRoot) ||
isSubtree(root.right, subRoot);
}
// Tree: 1 SubRoot: 1
// / \ / \
// 2 3 4 5
// Would return true, but subtrees are different!
// ✓ CORRECT - Check entire trees
if (isSameTree(root, subRoot)) { // Full comparison!
return true;
}
Mistake 3: Wrong Base Case Handling
// ❌ WRONG - Returns true for null root
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) return true; // WRONG!
// ...
}
// Null root has no subtrees!
// Should return false
// ✓ CORRECT - Null root means no subtree possible
if (root == null) return false;
Mistake 4: Not Using OR Logic
// ❌ WRONG - Uses AND instead of OR
return isSameTree(root, subRoot) &&
isSubtree(root.left, subRoot) &&
isSubtree(root.right, subRoot);
// This requires subtree to be EVERYWHERE!
// We only need it to exist SOMEWHERE!
// ✓ CORRECT - Use OR
return isSameTree(root, subRoot) ||
isSubtree(root.left, subRoot) ||
isSubtree(root.right, subRoot);
Mistake 5: Comparing References Instead of Values
// ❌ WRONG - Compares object references
if (root == subRoot) { // Memory address comparison!
return true;
}
// Even if values are same, objects are different!
// ✓ CORRECT - Compare structure and values
if (isSameTree(root, subRoot)) { // Deep comparison!
return true;
}
🎯 Pattern Recognition - Composing Solutions
Core Pattern: Problem Composition
Problem Composition = Combining simpler solutions
This problem =
Problem 131 (Same Tree) + DFS search
Template:
function complexProblem(params):
// Use solution from simpler problem
if (simpleProblem(params)):
return result
// Search/recurse
explore other possibilities
This is a POWERFUL technique!
Related Problems:
1. Same Tree (Problem 131) - The Building Block
Base problem: Are two trees identical?
Used as helper in:
- Subtree of Another Tree (this!)
- Symmetric Tree (with mirror twist)
- Many tree comparison problems
2. Lowest Common Ancestor
Uses tree search + comparison
- Search for nodes
- Compare subtrees
- Similar DFS pattern
3. Merge Two Binary Trees
Uses tree comparison + transformation
- Compare structures
- Combine values
- Build new tree
4. Maximum Depth (Problem 133) as Helper
Many problems use depth calculation:
- Balanced Binary Tree
- Diameter calculation
- Path problems
Composing solutions!
When to Use This Pattern:
✓ Problem can be decomposed into subproblems
✓ You recognize a familiar pattern
✓ Can reuse previous solutions
✓ Combining search + comparison
✓ Need to check multiple positions
📝 Quick Revision Notes
🎯 Core Concept
Check if subRoot is identical to any subtree in root. Use two functions: (1) isSameTree from Problem 131 - checks if two trees are identical, (2) isSubtree - DFS search through root, checking each node with isSameTree. At each node: check if match OR search in left OR search in right. Use OR logic (only need one match).
⚡ Quick Implementation
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
public static TreeNode buildTree(Integer[] arr) {
if (arr == null || arr.length == 0 || arr[0] == null) {
return null;
}
TreeNode root = new TreeNode(arr[0]);
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while (!queue.isEmpty() && i < arr.length) {
TreeNode current = queue.poll();
// Process left child
if (i < arr.length) {
if (arr[i] != null) {
current.left = new TreeNode(arr[i]);
queue.offer(current.left);
}
i++;
}
// Process right child
if (i < arr.length) {
if (arr[i] != null) {
current.right = new TreeNode(arr[i]);
queue.offer(current.right);
}
i++;
}
}
return root;
}
public static void print(TreeNode root) {
if (root == null) {
System.out.println("[]");
return;
}
List<String> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node != null) {
result.add(String.valueOf(node.val));
queue.offer(node.left);
queue.offer(node.right);
} else {
result.add("null");
}
}
while (!result.isEmpty() && result.get(result.size() - 1).equals("null")) {
result.remove(result.size() - 1);
}
System.out.println(result);
}
}
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
// both root and subroot reached leaf nodes. Equal. Return true.
if(root == null && subRoot == null) {
return true;
}
// One of reached early. Not equal. Return false.
if(root == null || subRoot == null) {
return false;
}
// check for equality at current nodes
// Take child of the current node and check equality of them (left and right child) to child tree (sameTree problem).
return isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
private boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) {
return true;
}
if(p == null || q == null) {
return false;
}
return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.isSubtree(TreeNode.buildTree(new Integer[] {3,4,5,1,2}),
TreeNode.buildTree(new Integer[] {4,1,2})));
System.out.println(s.isSubtree(TreeNode.buildTree(new Integer[] {3,4,5,1,2,null,null,null,null,0}),
TreeNode.buildTree(new Integer[] {4,1,2})));
System.out.println(s.isSubtree(TreeNode.buildTree(new Integer[] {1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,null,1,2}),
TreeNode.buildTree(new Integer[] {1,null,1,null,1,null,1,null,1,null,1,2})));
}
}
🔑 Key Insights
Problem Composition:
This problem = Problem 131 + DFS search
Problem 131: isSameTree(p, q)
"Are these trees identical?"
Problem 138: isSubtree(root, subRoot)
"Is subRoot identical to ANY subtree in root?"
Solution: For each node in root,
check isSameTree(node, subRoot)
Reusing solutions is POWERFUL! 🔑
Two-Level Recursion:
Level 1: isSubtree recursion
- Traverses through root tree
- Tries each node as potential match
- O(m) nodes visited
Level 2: isSameTree recursion
- At each node, compares entire subtrees
- Checks structure and values
- O(n) comparison per node
Total: O(m × n) time complexity
OR Logic is Critical:
Why OR (||)?
We need subtree to exist SOMEWHERE:
- At current position? OR
- In left subtree? OR
- In right subtree? OR
Only ONE match needed → use OR!
Don't use AND:
Would require subtree everywhere!
🎪 Memory Aid
"Same Tree + Search = Subtree!"
"Check here OR left OR right!"
"Reuse Problem 131 solution!"
"Compose, don't reinvent!" ✨
⚠️ Don't Forget
- Use isSameTree helper (from Problem 131!)
- Check null root (no subtrees possible)
- Use OR logic (||, not &&)
- Check entire trees (not just root values)
- Two-level recursion (search + compare)
- Short-circuit with OR (stop when found)
🔗 The Composition Pattern
// Generic problem composition
boolean complexProblem(Tree data) {
// Base cases
if (baseCondition) return baseResult;
// Use simpler problem solution
if (simpleProblem(data)) {
return true;
}
// Search/explore other options
return complexProblem(data.option1) ||
complexProblem(data.option2);
}
For this problem:
simpleProblem = isSameTree (Problem 131)
complexProblem = isSubtree (search with isSameTree)
🎉 Congratulations!
You've mastered problem composition!
What You Learned:
✅ Reusing solutions - Building on Problem 131
✅ Two-level recursion - Search + comparison
✅ OR logic - Finding at least one match
✅ Problem decomposition - Breaking complex into simple
✅ Helper functions - Modular solutions
✅ DFS search pattern - Checking all positions
The Power of Composition:
Instead of solving from scratch:
❌ "How do I solve this new problem?"
Recognize patterns:
✓ "I've seen part of this before!"
✓ "I can reuse Problem 131!"
✓ "Just add a search wrapper!"
Benefits:
✓ Faster development
✓ Less error-prone
✓ Easier to understand
✓ Modular and testable
This is how senior engineers think! 🎯
Pattern Connection:
Problem 131: Same Tree
Base building block
Problem 132: Symmetric Tree
Uses mirror comparison (modified 131)
Problem 138: Subtree of Another Tree
Uses exact Same Tree (reused 131)
Pattern: Build solutions by COMPOSING simpler ones!
Next Steps:
Problems that use composition: - Lowest Common Ancestor (uses tree search + comparison) - Serialize/Deserialize (uses tree traversal patterns) - Path problems (combine depth + validation)
You're thinking like an expert! 🌳🔧✨