Problem statement

Given the root of a binary tree, return true if it contains two identical subtrees with at least two nodes each, and false otherwise.

A subtree is a node together with all of its descendants. Two subtrees are identical when they have the same shape and the same value in every corresponding position. Repeated single leaves do not count.

Example 1

Input: root = [1,2,3,4,5,null,2,null,null,null,null,4,5]
Output: true
Explanation: The subtree 2 → (4, 5) appears twice, and it has three nodes.

Example 2

Input: root = [1,2,3]
Output: false
Explanation: The only repeated shapes would be single leaves, and 2 and 3 differ anyway.

Example 3

Input: root = [1,2,2,3,null,null,3]
Output: false
Explanation: Both 2s have a child 3, but one on the left and one on the right — the subtrees differ.

Constraints

• 1 <= number of nodes <= 10^5
• 1 <= Node.val <= 10^5

Hints for Duplicate Subtree in Binary Tree

1. Hint 1

   Comparing every pair of subtrees directly is far too slow; give every subtree a canonical name instead.

2. Hint 2

   Build names bottom-up: a subtree is determined by (name of its left subtree, its value, name of its right subtree), with a fixed name for an empty child.

3. Hint 3

   Map each such triple to a small integer id. If a node that is not a leaf produces a triple already seen, a duplicate of size at least two exists.

How to solve Duplicate Subtree in Binary Tree

Two subtrees are identical exactly when their roots have equal values and identical left and right subtrees. Assigning each distinct subtree an integer id in post-order turns that recursive test into a lookup of the triple (leftId, val, rightId).

Approach

1. Give the empty subtree id 0 and keep a map from triples to ids.
2. Post-order: compute the ids of the left and right subtrees, then look up (leftId, node.val, rightId).
3. If the triple is already in the map and the node is not a leaf, a duplicate subtree of size ≥ 2 exists — answer true.
4. Otherwise store the triple with a fresh id (or reuse the existing one for a leaf) and return it.

Why it works

By induction two subtrees receive the same id exactly when they are identical: equal triples mean equal values and children with equal ids, hence identical children. A non-leaf node whose triple repeats therefore has an identical twin elsewhere with the same size, which is at least two. Leaves are the only subtrees of size one, and they are excluded.

Complexity

• Time — O(n) expected with a hash map
• Space — O(n)

Pitfalls

• Serialising with in-order alone is ambiguous — 1 with left child 2 and 2 with right child 1 read the same. Mark empty children, or use ids.
• Two equal leaves are not an answer; only subtrees of two or more nodes count.
• Building full serialisation strings costs O(n²) on a chain; integer ids keep it linear.

Reference solution

Python

from typing import Optional

def dupSub(root: Optional[TreeNode]) -> bool:
    ids = {}
    found = [False]

    def walk(node):
        if node is None:
            return 0
        key = (walk(node.left), node.val, walk(node.right))
        if key in ids:
            if node.left is not None or node.right is not None:
                found[0] = True
            return ids[key]
        ids[key] = len(ids) + 1
        return ids[key]

    walk(root)
    return found[0]

Java

public static boolean dupSub(TreeNode root) {
    Map<String, Integer> ids = new HashMap<>();
    boolean[] found = new boolean[1];
    subtreeId(root, ids, found);
    return found[0];
}

static int subtreeId(TreeNode node, Map<String, Integer> ids, boolean[] found) {
    if (node == null) return 0;
    String key = subtreeId(node.left, ids, found) + "," + node.val + "," + subtreeId(node.right, ids, found);
    Integer id = ids.get(key);
    if (id != null) {
        if (node.left != null || node.right != null) found[0] = true;
        return id;
    }
    int fresh = ids.size() + 1;
    ids.put(key, fresh);
    return fresh;
}

C++

static int subtreeId(TreeNode* node, map<tuple<int, int, int>, int>& ids, bool& found);

bool dupSub(TreeNode* root) {
    map<tuple<int, int, int>, int> ids;
    bool found = false;
    subtreeId(root, ids, found);
    return found;
}

static int subtreeId(TreeNode* node, map<tuple<int, int, int>, int>& ids, bool& found) {
    if (!node) return 0;
    int l = subtreeId(node->left, ids, found);
    int r = subtreeId(node->right, ids, found);
    auto key = make_tuple(l, node->val, r);
    auto it = ids.find(key);
    if (it != ids.end()) {
        if (node->left || node->right) found = true;
        return it->second;
    }
    int fresh = (int) ids.size() + 1;
    ids[key] = fresh;
    return fresh;
}

JavaScript

var dupSub = function(root) {
    var ids = {}, count = 0, found = false;
    var walk = function(node) {
        if (node === null) return 0;
        var key = walk(node.left) + "," + node.val + "," + walk(node.right);
        if (ids.hasOwnProperty(key)) {
            if (node.left !== null || node.right !== null) found = true;
            return ids[key];
        }
        ids[key] = ++count;
        return count;
    };
    walk(root);
    return found;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More hash table problems

• Operations on Tree Medium
• Throne Inheritance Medium
• Convert Sorted List to Binary Search Tree Medium
• Foldable Binary Tree Medium
• K-th Largest Perfect Subtree Size in Binary Tree Medium
• Sum of Nodes on the Longest Path from Root to Leaf Medium