Definition
- Subtree check – determines whether a smaller tree appears exactly inside a larger tree with the same structure and values.
- Outer traversal – visits each node of the main tree as a candidate anchor point.
- Inner check – the standard same-tree comparison: both null is a match, one null is a mismatch, values must be equal, and both subtrees must recursively match.
- Complexity – O(n * m) for the naive approach; O(n + m) using serialization with linear-time substring matching.
- Serialization – encode both trees with explicit null markers and delimiters, then check substring containment.
Rajesh has the full National Bank of India org chart and a small team chart representing a known fraudulent approval pattern. He walks the big chart, and at every manager he checks whether the team hanging below matches the small chart exactly in shape and roles. If he finds one spot that matches completely, the pattern exists in the org.
Understanding the Concepts
What is the subtree of another tree problem?
Given two binary trees, the main tree and a candidate subtree, determine whether the candidate appears exactly as a subtree somewhere inside the main tree. The match must be exact: same structure and same values at every position.
package com.bank.model;
public class ApprovalNode {
public String role;
public ApprovalNode left;
public ApprovalNode right;
public ApprovalNode(String role) {
this.role = role;
}
}
How does the naive approach work?
The outer method visits each node of the main tree. At each node, it runs a same-tree comparison against the candidate. If any comparison succeeds, return true. Otherwise recurse into both children.
package com.bank.service;
import com.bank.model.ApprovalNode;
public class SubtreeChecker {
public static boolean isSubtree(ApprovalNode root, ApprovalNode subRoot) {
if (root == null) return false;
if (isSameTree(root, subRoot)) return true;
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
private static boolean isSameTree(ApprovalNode a, ApprovalNode b) {
if (a == null && b == null) return true;
if (a == null || b == null) return false;
return a.role.equals(b.role)
&& isSameTree(a.left, b.left)
&& isSameTree(a.right, b.right);
}
public static void main(String[] args) {
// CEO
// / \
// VP1 VP2
// / \ \
// D1 D2 D3
ApprovalNode ceo = new ApprovalNode("CEO");
ApprovalNode vp1 = new ApprovalNode("VP1");
ApprovalNode vp2 = new ApprovalNode("VP2");
ApprovalNode d1 = new ApprovalNode("D1");
ApprovalNode d2 = new ApprovalNode("D2");
ApprovalNode d3 = new ApprovalNode("D3");
ceo.left = vp1; ceo.right = vp2;
vp1.left = d1; vp1.right = d2;
vp2.right = d3;
// Pattern to find
ApprovalNode pattern = new ApprovalNode("VP1");
pattern.left = new ApprovalNode("D1");
pattern.right = new ApprovalNode("D2");
System.out.println("Is subtree: " + isSubtree(ceo, pattern));
}
}
Is subtree: true
How does the same-tree inner check work?
The inner check is the standard identical-trees comparison. Both null means match. Exactly one null means mismatch. Values must be equal. Both left and right subtrees must recursively match.
private static boolean isSameTree(ApprovalNode a, ApprovalNode b) {
if (a == null && b == null) return true; // both ended
if (a == null || b == null) return false; // one ended early
return a.role.equals(b.role) // values match
&& isSameTree(a.left, b.left) // left subtrees match
&& isSameTree(a.right, b.right); // right subtrees match
}
What is the time complexity of the naive approach?
In the worst case, every node of the main tree triggers a full comparison that scans the entire candidate. For a main tree of size n and candidate of size m, this is O(n * m). The space is O(h1 + h2) from the combined recursion depth.
| Approach | Time | Space |
|---|---|---|
| Naive (compare at each node) | O(n * m) | O(h1 + h2) |
| Serialization + KMP | O(n + m) | O(n + m) |
What is the efficient serialization approach?
Serialize both trees into strings with explicit null markers and delimiters. Then check whether the candidate's serialization is a substring of the main tree's serialization using a linear-time matcher like Knuth-Morris-Pratt.
package com.bank.service;
import com.bank.model.ApprovalNode;
public class SubtreeSerialize {
public static boolean isSubtree(ApprovalNode root, ApprovalNode sub) {
String mainStr = serialize(root);
String subStr = serialize(sub);
return mainStr.contains(subStr); // or use KMP for O(n+m)
}
private static String serialize(ApprovalNode node) {
if (node == null) return ",#"; // null marker with delimiter
return "," + node.role + serialize(node.left) + serialize(node.right);
}
public static void main(String[] args) {
ApprovalNode main = new ApprovalNode("CEO");
main.left = new ApprovalNode("VP1");
main.left.left = new ApprovalNode("D1");
main.left.right = new ApprovalNode("D2");
main.right = new ApprovalNode("VP2");
ApprovalNode sub = new ApprovalNode("VP1");
sub.left = new ApprovalNode("D1");
sub.right = new ApprovalNode("D2");
System.out.println("Serialization match: " + isSubtree(main, sub));
}
}
Serialization match: true
Why are null markers and delimiters essential?
Without explicit null markers, two different tree structures can produce the same serialization. Without delimiters, a value like 12 could be confused with adjacent values 1 and 2.
// Without null markers: different trees, same string
// Tree A: 1 Tree B: 1
// / \
// 2 2
// Both serialize to "1,2" without null markers!
// With null markers:
// Tree A: ",1,2,#,#,#" Tree B: ",1,#,2,#,#"
// Now they are different.
// Without delimiters: value "12" vs "1" followed by "2"
// With comma delimiters: ",12," vs ",1,,2," are distinguishable
What are the edge cases?
Empty candidate (always true if we consider null a subtree of any tree), candidate larger than main tree (always false), and identical trees.
package com.bank.service;
import com.bank.model.ApprovalNode;
public class SubtreeEdgeCases {
public static void main(String[] args) {
ApprovalNode main = new ApprovalNode("CEO");
main.left = new ApprovalNode("VP");
// Identical trees
ApprovalNode same = new ApprovalNode("CEO");
same.left = new ApprovalNode("VP");
System.out.println("Identical: " + SubtreeChecker.isSubtree(main, same));
// Single node match
System.out.println("Single leaf: " + SubtreeChecker.isSubtree(main, new ApprovalNode("VP")));
}
}
Identical: true
Single leaf: true
What should a senior engineer know?
Recognizing both the simple O(n * m) approach and the O(n + m) serialization approach, and knowing the pitfalls of serialization (delimiters, null sentinels, prefix confusion), is the senior-level answer. The serialization approach is faster but more error-prone; the naive approach is safer and often sufficient for small trees.
In production at National Bank of India, compliance maintains templates of known fraudulent approval patterns. The fraud-pattern detector searches for each template inside every branch's full approval hierarchy. When branches are large with many patterns to scan, the serialization approach provides linear performance.
// Fraud pattern detection in production
for (ApprovalNode pattern : knownFraudPatterns) {
if (SubtreeChecker.isSubtree(branchOrgTree, pattern)) {
alertService.flagFraudPattern(branchId, pattern);
}
}
Visual Overview
Subtree Check: Outer Traversal + Inner Same-Tree
Main Tree: Candidate:
CEO VP1
/ \ / \
VP1 VP2 D1 D2
/ \ \
D1 D2 D3
Step 1: isSameTree(CEO, VP1)? CEO != VP1 → false
Step 2: recurse left → isSameTree(VP1, VP1)?
VP1 == VP1, left D1 == D1, right D2 == D2 → true!
Found subtree at VP1.
Serialization Approach Main: ",CEO,VP1,D1,#,#,D2,#,#,VP2,#,D3,#,#" Sub: ",VP1,D1,#,#,D2,#,#" Check: is Sub a substring of Main? → Yes! (KMP gives O(n + m) time)
Key Takeaway
Subtree of Another Tree composes two ideas: traversing the main tree to pick candidate anchor points, and running a strict same-tree comparison at each anchor. The outer traversal visits every node, and at each one the inner check verifies whether the subtree rooted there is exactly identical to the candidate in both structure and values.
The naive complexity is O(n * m) because each main-tree node may trigger a full comparison. The efficient alternative serializes both trees with explicit null markers and delimiters, then checks substring containment using a linear-time matcher. The serialization must use delimiters between values and explicit null sentinels so that different tree structures are distinguishable and adjacent values cannot be confused.
The inner same-tree check must be strict: both null is a match, exactly one null is a mismatch, and values must be equal at every position. A near-match is not a subtree.
In our banking system at National Bank of India, compliance maintains templates of known fraudulent approval patterns as small trees. The detector searches for each pattern inside every branch's org hierarchy. The match must be exact in both shape and role at each position, and when branches are large with many patterns, the serialization approach provides the linear performance needed for production throughput.
Remember one sentence: traverse the main tree, run a strict same-tree check at each node, and if any check passes the candidate is a subtree.
---