Find Duplicate Subtrees — Tree Serialization Plus Frequency Hashmap

Problem Statement#

Given the root of a binary tree, return all duplicate subtrees. For each duplicate kind you may return the root of any one occurrence. Two subtrees are duplicates if they have the same structure and the same node values.

Constraints:

• The number of nodes is in the range [1, 10^4].
• -200 <= Node.val <= 200

Input:  root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

Input:  root = [0,0,0,0,null,null,0,null,null,null,0]
Output: [[0]]

Why This Problem Matters#

LeetCode 652 is a high-signal hashmap interview problem at Google, Amazon, and Microsoft. It tests whether candidates can fuse tree traversal with hashing — a pattern that reappears in compiler IR deduplication, expression CSE, and on-disk Merkle structures.

The hash table FAANG signal: can you canonicalize a structured object so equality of objects becomes equality of strings? Once you can answer "yes" with a serialization scheme that includes nulls, the hashmap counts duplicates in one pass.

This problem also sets up the "memoization with structural keys" follow-up that appears in problems like "verify same tree" and "subtree of another tree."

The Core Insight#

Two subtrees are equal iff their post-order serializations are equal, provided we include null markers. Build a serialization recursively: serial(node) = val + "," + serial(left) + "," + serial(right), with a special token like "#" for null. Use a hashmap to count occurrences. When a serialization hits count 2, append the current node to the answer.

Visual Dry Run#

Tree [1,2,3,4,null,2,4,null,null,4]. Post-order serializations:

Answer: roots of subtrees with serialization 4 and 2,4.

Solution (Optimal)#

from collections import defaultdict
 
class Solution:
    def findDuplicateSubtrees(self, root):
        seen = defaultdict(int)
        result = []
 
        def serialize(node) -> str:
            if not node:
                return "#"
            key = f"{node.val},{serialize(node.left)},{serialize(node.right)}"
            seen[key] += 1
            if seen[key] == 2:
                result.append(node)
            return key
 
        serialize(root)
        return result

var findDuplicateSubtrees = function(root) {
    const seen = new Map();
    const result = [];
 
    const serialize = (node) => {
        if (!node) return "#";
        const key = node.val + "," + serialize(node.left) + "," + serialize(node.right);
        const count = (seen.get(key) || 0) + 1;
        seen.set(key, count);
        if (count === 2) result.push(node);
        return key;
    };
 
    serialize(root);
    return result;
};

Time: O(n^2) worst case — string concatenation per node can grow to O(n). Space: O(n^2) worst case — the hashmap stores up to n strings of total length O(n^2).

Common Mistakes#

• Omitting null markers, which collapses non-equal subtrees into the same string.
• Using pre-order without delimiters, which makes [1,2] and [12] collide.
• Adding the node every time the count is >= 2, producing duplicate entries in the result.
• Forgetting to memoize per node id when interviewers ask for the linear-time variant.
• Returning the serialization key instead of the node; the problem wants TreeNode references.

Interview Tips#

• State the canonicalization rule out loud: "I will serialize null as # and join with commas."
• Mention the trick of returning the result the first time the count hits exactly 2; it dedupes naturally.
• Note that strings can grow to O(n^2) in pathological trees; the linear-time version replaces them with integer ids.
• Trace one full subtree end-to-end to demonstrate edge-case handling.

Follow-up Questions#

• Can you achieve O(n) time? Hint: replace strings with auto-assigned integer ids in a hashmap of (left_id, val, right_id).
• What if values can exceed Node.val range and cause collisions in your delimiter? Hint: use a tuple key in Python or JSON-stringify in JavaScript.
• What if the tree is huge and you only need duplicates of a fixed depth? Hint: prune recursion when subtree depth exceeds the target.
• What if you need all occurrences, not just one per kind? Hint: store the list of nodes per key; emit on demand.
• Can the algorithm be parallelized? Hint: yes — serializations are independent within disjoint subtrees.

Key Takeaways#

• LeetCode 652 fuses tree DFS with hashmap interview canonicalization.
• Serialize each subtree in post-order with null markers and delimiters.
• Append the node to the answer only the first time the count reaches 2.
• Worst-case time and space are O(n^2) due to string sizes.
• The linear-time variant replaces strings with integer ids assigned by a triple-keyed hashmap.
• Recognize the pattern: "structural equality becomes string equality" via canonical serialization.
• This is a Google, Amazon, and Microsoft favorite at the senior hashmap interview level.