Find Duplicate Subtrees — LC 652 Serialize-and-Hash Pattern

Problem Statement#

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

Constraints:

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

Input:  root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]
        Subtree rooted at 4 appears twice; subtree (2 -> 4) appears twice.

Input:  root = [2,1,1]
Output: [[1]]

Why This Problem Matters#

LeetCode 652 Find Duplicate Subtrees is a Medium-difficulty interview question asked at Google, Amazon, Meta, and Bloomberg. It is the canonical "tree fingerprinting" problem and tests three FAANG-favorite skills: postorder DFS, serialization, and hash-based deduplication.

The naive serialization-with-strings approach is O(n^2) due to repeated string concatenation. The polished approach uses subtree-id assignment (Aho-style hashing) to achieve O(n). Interviewers love watching candidates discover that two structurally identical subtrees deserve the same canonical id, allowing comparison in O(1).

The pattern recurs in compiler common-subexpression elimination, deduplicating ASTs, and version-control tree-diff algorithms.

The Core Insight#

For each subtree, compute a canonical signature. Two subtrees are duplicates iff their signatures match. The cheapest signature is a postorder serialization: f(node) = "node.val,f(left),f(right)" with # for null.

Postorder is required because we need children's signatures to build the parent's. As we compute each signature, look it up in a hashmap. The first time we see a signature, store the root. The second time, add it to the result. Subsequent times, do nothing (we want each duplicate group represented once).

To get O(n), replace string signatures with integer ids: every unique signature gets a fresh id; recursion returns the id, and parents compose (node.val, leftId, rightId) as the new key.

Visual Dry Run#

Tree: [1,2,3,4,null,2,4,null,null,4]

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4

Duplicates: subtree 4 and subtree 2 -> 4.

Solution (Optimal)#

class Solution:
    def findDuplicateSubtrees(self, root):
        seen = {}
        duplicates = []
        def serialize(node):
            if not node:
                return '#'
            sig = f"{node.val},{serialize(node.left)},{serialize(node.right)}"
            seen[sig] = seen.get(sig, 0) + 1
            if seen[sig] == 2:
                duplicates.append(node)
            return sig
        serialize(root)
        return duplicates

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

Time: O(n^2) with string keys (string of length up to n built per node), O(n) with id-based hashing. Space: O(n^2) string-based or O(n) id-based.

Common Mistakes#

• Forgetting null markers — 1,2 and 1,null,2 collide otherwise.
• Pushing on every occurrence rather than only the second — produces duplicates in output.
• Using preorder without delimiters — [1,2] vs [12] ambiguity.
• Returning the root multiple times when 3+ duplicates exist — gate with count == 2.
• Building strings in an outer scope and forgetting to reset between calls.

Interview Tips#

• State the serialize-and-hash pattern by name: "I'll use a postorder canonical form."
• Mention complexity tradeoff: O(n^2) with strings, O(n) with id-mapping.
• Confirm "structurally identical AND value-identical" with the interviewer.
• Draw a small tree and write the serialization for one or two subtrees on the whiteboard.
• Volunteer that this technique generalizes to AST deduplication in compilers.

Follow-up Questions#

• O(n) version? Use a (val, leftId, rightId) -> id map; ids are integers.
• Detect a single duplicate (existence)? Return early when count == 2.
• Largest duplicate subtree? Track signature length or node count alongside.
• Subtrees with the same shape (ignoring values)? Use a structural signature only.
• Memory-bound version? Replace strings with rolling hashes (with collision risk).

Key Takeaways#

• LeetCode 652 is a Medium-difficulty FAANG problem asked at Google, Amazon, and Meta.
• The pattern is postorder DFS plus hashmap-based fingerprinting of canonical signatures.
• String-based signatures yield O(n^2) time; integer-id mapping achieves O(n).
• Add a duplicate to the result only when its count reaches exactly 2.
• Null markers and delimiters are mandatory to disambiguate signatures.
• Time complexity O(n) with id-hashing, space O(n) for the hashmap.
• The pattern transfers to AST deduplication, common subexpression elimination, and tree diffing.