Find Duplicate Subtrees

MediumTrees · DFS · Hashing (Subtree IDs)🧩 Tree DFS LeetCode #652 ↗Updated Oct 30, 2026

Problem

Given the root of a binary tree, find every subtree that occurs at least twice — two subtrees match when they have the same shape and the same value at every position. For each group of matching subtrees, return the root node of any one of them. The answer list may be in any order.

Inputroot = [5,4,6,3,null,4,null,null,null,3]Output[[3],[4,3]]

Inputroot = [2,1,1]Output[[1]]

Inputroot = [1,2,3]Output[]

1 ≤ nodes ≤ 5000 · -200 ≤ Node.val ≤ 200

Try it yourself

Java

class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Give every distinct subtree a small integer ID, computed bottom-up from the triple (leftID, val, rightID). Equal subtrees get equal triples, so a hash map turns “are these subtrees identical?” into an O(1) lookup — report a node the moment its ID is seen for the second time.

PatternTree DFS

Instinct If the answer for a node can be built from the answers of its left and right subtrees, write one recursive function and trust it on the children.

Memory hack Ask the kids, then decide - each child reports up, the parent combines, and a global variable keeps the best "bend" seen so far.

Open the Tree DFS guide →

Approaches

Brute ForceCompare Every Pair of Subtrees

Time O(n³)Space O(n)

Collect all nodes into a list. For node i, compare its subtree structurally against every other node. Report i only if some later node matches it and no earlier node does, so each group is reported exactly once (by its first member).

Java

public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
    List<TreeNode> all = new ArrayList<>();
    collect(root, all);
    List<TreeNode> res = new ArrayList<>();
    for (int i = 0; i < all.size(); i++) {
        boolean earlierCopy = false, laterCopy = false;
        for (int j = 0; j < all.size() && !earlierCopy; j++) {
            if (j == i || !same(all.get(i), all.get(j))) continue;
            if (j < i) earlierCopy = true; // the group was already reported
            else laterCopy = true;
        }
        if (laterCopy && !earlierCopy) res.add(all.get(i));
    }
    return res;
}
private void collect(TreeNode node, List<TreeNode> all) {
    if (node == null) return;
    all.add(node);
    collect(node.left, all);
    collect(node.right, all);
}
private boolean same(TreeNode a, TreeNode b) {
    if (a == null || b == null) return a == b;
    return a.val == b.val && same(a.left, b.left) && same(a.right, b.right);
}

Obviously correct and handy as a test oracle, but n² pairs each cost up to O(n).

BetterSerialize Every Subtree into a String

Time O(n²)Space O(n²)

A post-order DFS builds a canonical string (left,val,right) for every subtree, with # for null, so two subtrees are identical exactly when their strings are equal. Count strings in a hash map and add the node when its count reaches 2.

Java

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

One traversal, but each string can be O(n) long, so building and hashing cost O(n²).

OptimalInteger IDs from (left, val, right) Triples

Time O(n)Space O(n)

Instead of the full string, a subtree is described by the IDs of its two children plus its value — a constant-size key. A map hands out a fresh ID to every new triple, and a second map counts how often each ID occurs. Every node does O(1) expected work.

Java

public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
    Map<String, Integer> idOf = new HashMap<>();
    Map<Integer, Integer> seen = new HashMap<>();
    List<TreeNode> res = new ArrayList<>();
    assignId(root, idOf, seen, res);
    return res;
}
private int assignId(TreeNode node, Map<String, Integer> idOf,
                     Map<Integer, Integer> seen, List<TreeNode> res) {
    if (node == null) return 0; // id 0 = empty tree
    int left = assignId(node.left, idOf, seen, res);
    int right = assignId(node.right, idOf, seen, res);
    String triple = left + "," + node.val + "," + right;
    Integer id = idOf.get(triple);
    if (id == null) {
        id = idOf.size() + 1;
        idOf.put(triple, id);
    }
    if (seen.merge(id, 1, Integer::sum) == 2) res.add(node);
    return id;
}

Linear expected time; the key never grows with subtree size.

Pro tip

This is “tree hashing”: the same ID trick checks subtree isomorphism or merges identical subtrees into a DAG.

At a glance

Level	Approach	Time	Space
Brute Force	Compare Every Pair of Subtrees	`O(n³)`	`O(n)`
Better	Serialize Every Subtree into a String	`O(n²)`	`O(n²)`
Optimal	Integer IDs from (left, val, right) Triples	`O(n)`	`O(n)`

Common pitfalls

Ambiguous serialization (e.g. no null markers or separators) makes different trees collide.
Adding the node on every repeat instead of only when the count hits exactly 2 → duplicates in the answer.
Pre-order strings without null markers lose shape: [1,2] and [1,null,2] look equal.

Interview tips

Start with the serialization idea, then point out the O(n²) string cost and shrink keys to IDs.
Explain why post-order is required: a node's key depends on its children's keys.
Clarify that any one representative per group is enough and order does not matter.

Pattern

Subtree serialization / hashing → when you must detect equal or repeated subtrees, or compare tree structures quickly.

My notes saved in this browser