Find Duplicate Subtrees — Serialize + HashMap

Problem 191 · Find Duplicate Subtrees

Difficulty: Medium · Pattern: Tree Serialization + HashMap

Return all root nodes of duplicate subtrees.

Intuition

Post-order serialize each subtree to a string. Use a frequency map; when count reaches 2, add to result.

Solutions

# Python
from collections import defaultdict
def findDuplicateSubtrees(root):
    count = defaultdict(int)
    res = []
    def serial(node):
        if not node: return '#'
        s = f"{node.val},{serial(node.left)},{serial(node.right)}"
        count[s] += 1
        if count[s] == 2: res.append(node)
        return s
    serial(root)
    return res

// Java
Map<String,Integer> map = new HashMap<>();
List<TreeNode> res = new ArrayList<>();
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
    serial(root); return res;
}
String serial(TreeNode node) {
    if (node == null) return "#";
    String s = node.val + "," + serial(node.left) + "," + serial(node.right);
    map.merge(s, 1, Integer::sum);
    if (map.get(s) == 2) res.add(node);
    return s;
}

// C++
unordered_map<string,int> cnt;
vector<TreeNode*> res;
string serial(TreeNode* node) {
    if (!node) return "#";
    string s = to_string(node->val)+","+serial(node->left)+","+serial(node->right);
    if (++cnt[s] == 2) res.push_back(node);
    return s;
}
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
    serial(root); return res;
}

Complexity

Time: O(n²) worst case (string concat), O(n) with hashing optimization
Space: O(n²)