Binary TreesProblem 24 of 35Important
Check if a Binary Tree contains duplicate subtrees of size 2 or more [IMP]
Problem Statement
Given a binary tree, check if it contains duplicate subtrees of size 2 or more. Two subtrees are duplicates if they have the same structure and same node values.
Example 1:
1
/ \
2 3
/ / \
4 2 4
/
4
Output: true
Subtree rooted at node 2 (with child 4) appears twice
Example 2:
1
/ \
2 3
Output: false
No duplicate subtrees of size >= 2
Approach 1: Brute Force (Compare Each Pair of Subtrees)
Intuition
For every node, compare its subtree with every other node's subtree. If any two subtrees match and have size >= 2, return true.
Algorithm
- Get all nodes with subtree size >= 2
- For each pair of nodes, check if their subtrees are identical
- If any pair matches, return true
- Use helper function to check if two trees are identical
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int getSize(TreeNode root) {
if (root == null) return 0;
return 1 + getSize(root.left) + getSize(root.right);
}
private boolean areIdentical(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
return t1.val == t2.val &&
areIdentical(t1.left, t2.left) &&
areIdentical(t1.right, t2.right);
}
private void getAllNodes(TreeNode root, List<TreeNode> nodes) {
if (root == null) return;
// Only consider subtrees of size >= 2
if (getSize(root) >= 2) {
nodes.add(root);
}
getAllNodes(root.left, nodes);
getAllNodes(root.right, nodes);
}
public boolean hasDuplicateSubtreeBruteForce(TreeNode root) {
List<TreeNode> nodes = new ArrayList<>();
getAllNodes(root, nodes);
// Compare each pair of subtrees
for (int i = 0; i < nodes.size(); i++) {
for (int j = i + 1; j < nodes.size(); j++) {
if (areIdentical(nodes.get(i), nodes.get(j))) {
return true;
}
}
}
return false;
}
}Complexity Analysis
- Time Complexity: O(n^3) - O(n^2) pairs, each comparison takes O(n)
- Space Complexity: O(n^2) - Store O(n) nodes, recursion stack O(n)
Approach 2: Optimal (Serialization with HashMap)
Intuition
Serialize each subtree into a unique string representation. Store these strings in a HashMap. If a serialization is seen more than once and represents a subtree of size >= 2, we have found duplicates.
Algorithm
- Perform postorder traversal (process children first)
- Serialize each subtree: "(left)val(right)"
- Track subtree size along with serialization
- Use HashMap to detect duplicate serializations
- Return true if any size >= 2 subtree appears twice
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private Map<String, Integer> subtreeCount = new HashMap<>();
private boolean found = false;
// Returns array of {serialization, size as string}
private String[] serialize(TreeNode root) {
if (root == null) {
return new String[]{"#", "0"};
}
String[] left = serialize(root.left);
String[] right = serialize(root.right);
// Create serialization for current subtree
String serial = "(" + left[0] + ")" + root.val + "(" + right[0] + ")";
int size = 1 + Integer.parseInt(left[1]) + Integer.parseInt(right[1]);
// Check for duplicates only if size >= 2
if (size >= 2) {
int count = subtreeCount.getOrDefault(serial, 0) + 1;
subtreeCount.put(serial, count);
if (count == 2) {
found = true;
}
}
return new String[]{serial, String.valueOf(size)};
}
public boolean hasDuplicateSubtree(TreeNode root) {
subtreeCount.clear();
found = false;
serialize(root);
return found;
}
}Complexity Analysis
- Time Complexity: O(n) - Each node is visited once, HashMap operations are O(1) average
- Space Complexity: O(n) - HashMap storage for serializations
Key Takeaways
- Tree serialization uniquely represents tree structure and values
- Postorder traversal is natural for building serializations bottom-up
- HashMap for duplicate detection - classic pattern
- Size tracking is needed to filter subtrees of size >= 2
- Serialization format matters: Use delimiters to avoid ambiguity (e.g., "(left)val(right)")