Subtree of Another Tree
Mahabharata — The Sub-Formation — Is One Army Arrangement Contained Within the Larger?
बड़े वृक्ष में — छोटा वृक्ष?। हर नोड पर — isSameTree जांचो॥
*Within the larger tree — is the smaller? At every node — check isSameTree.*
The Story
Given tree `root` and tree `subRoot`, check if subRoot is a subtree of root (as a complete subtree from some node).
For `root=[3,4,5,1,2]`, `subRoot=[4,1,2]`: true. For `root=[3,4,5,1,2,null,null,null,null,0]`, `subRoot=[4,1,2]`: false (root's [4] subtree has an extra leaf 0).
**Uses isSameTree (tr-9) as helper:** ```java public boolean isSubtree(TreeNode root, TreeNode subRoot) { if (root == null) return false; // Exhausted the main tree if (isSameTree(root, subRoot)) return true; // Found matching subtree return isSubtree(root.left, subRoot) // Check left || isSubtree(root.right, subRoot); // Check right }
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); } ```
For each node in root, we check if subRoot starts there. If isSameTree returns true at any node, it's a subtree. Otherwise, recurse into left and right children.
Trace `root=[3,4,5,1,2]`, `subRoot=[4,1,2]`: - isSubtree(3, [4,1,2]): isSameTree(3,[4,1,2])? 3≠4→false. Recurse left, right. - isSubtree(4, [4,1,2]): isSameTree(4,[4,1,2])? 4==4&&same(1,1)&&same(2,2)=true! - Return true ✓
The String Serialization Approach
Serialize both trees, check if one is a substring of the other. Be careful with node boundaries (e.g., use delimiters). O(m × n) in worst case.
// Serialization approach:
String serialize(TreeNode root) {
if (root == null) return "#null";
return "#" + root.val + serialize(root.left) + serialize(root.right);
}
boolean isSubtreeSerialize(TreeNode root, TreeNode sub) {
return serialize(root).contains(serialize(sub));
}The isSameTree-at-Every-Node Wisdom
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);
}
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);
}Step-by-Step Walkthrough
root=[1,1], subRoot=[1] At root=1: isSameTree([1,1],[1])? 1==1 but [1,1] has children, [1] doesn't → false At root.left=1: isSameTree([1],[1])? 1==1&&null==null=true → return true ✅
Deep Insight
**The composition pattern:** isSubtree uses isSameTree as a building block. This composition of tree functions is elegant and common: - isSubtree = try isSameTree at every node + DFS to find all nodes
**O(m×n) complexity:** For each of m nodes in root, we call isSameTree which takes O(n) (size of subRoot). Total: O(m×n).
**Optimized with hashing (O(m+n)):** Compute a tree hash for each subtree of root. Compare with hash of subRoot. O(m+n) with O(m) space for hashes.
**Optimized with KMP (O(m+n)):** Serialize both trees with null markers. Use KMP string matching to find subRoot's serialization as substring of root's serialization.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(m × n) | O(m + n) | Serialization + string matching |
| Optimal | O(m × n) | O(m + n) | At each m nodes, O(n) isSameTree check |
Pattern Recognition
✅ Subtree check = isSameTree at every node ✅ DFS to traverse all nodes of root ✅ isSameTree is the helper ✅ O(m×n) naive; O(m+n) with hashing or KMP **LeetCode Trigger Phrases:** → "subtree of another tree" → Check if tree appears as complete subtree → Composition of isSameTree + DFS
Bhagavad Gita 15.3
अश्वत्थमेनं सुविरूढमूलमसङ्गशस्त्रेण दृढेन छित्त्वा।
Cut down this firmly rooted Ashvattha tree with the strong axe of non-attachment.
Connection: The subtree question asks: is this smaller pattern embedded within the larger tree? Every subtree is a complete miniature of the larger tree, existing as a self-contained formation within it. Like a truth repeated at multiple scales in the cosmic order, the subRoot may manifest at any node of the root tree. The algorithm searches each node with the same question: 'Is this where the pattern begins?' — a meditation on self-similarity within complexity.