Find Duplicate Subtrees

Problem

Return the roots of all duplicate subtrees. Two subtrees are duplicates if they have the same structure and node values.

Key insight: Serialize each subtree (postorder), store in map. If count reaches 2, add root to result.

Solutions

// C — Use string hash map (complex in C; shown conceptually)

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

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

// JavaScript
function findDuplicateSubtrees(root) {
    const count = new Map();
    const result = [];
    function dfs(node) {
        if (!node) return '#';
        const key = `${node.val},${dfs(node.left)},${dfs(node.right)}`;
        count.set(key, (count.get(key) || 0) + 1);
        if (count.get(key) === 2) result.push(node);
        return key;
    }
    dfs(root);
    return result;
}

# Python
from collections import defaultdict

def findDuplicateSubtrees(root):
    count = defaultdict(int)
    result = []
    def dfs(node):
        if not node:
            return '#'
        key = f'{node.val},{dfs(node.left)},{dfs(node.right)}'
        count[key] += 1
        if count[key] == 2:
            result.append(node)
        return key
    dfs(root)
    return result

Complexity

Time: O(n²) naively due to string concat; O(n) with hashing
Space: O(n²)

Key Insight

Postorder serialization uniquely identifies subtree structure. Add to result exactly when count hits 2.